How to implement Hill sorting in C #

This article mainly explains "how C#implements Hill sorting". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let Xiaobian take you to learn "C#How to Realize Hill Sorting"!

For large, out-of-order arrays, insertion sort is slow because it only swaps adjacent elements, so elements can only be moved from one end of the array to the other. Hill sort improves insertion sort by swapping non-adjacent elements to sort arrays locally, and finally sorting locally ordered arrays with insertion sort.

The idea behind Hill sorting is to make any element of an array spaced apart by h ordered. Such an array is called an h ordered array. In other words, an h ordered array is an array of h independent ordered arrays.

When sorting, starting with a large h, you can move elements far away, creating convenience for smaller h ordering. Decrement of h to 1 corresponds to insertion sort. This is Hill sort. The following code h decreases from N/3, h = h * 3 + 1:

public class Shell: BaseSort { public static long usedTimes = 0; public Shell() { } public static void Sort(IComparable[] a) { Stopwatch timer = new Stopwatch(); timer.Start(); int n = a.Length; int h = 1; while (h

< n / 3) h = h * 3 + 1; /* * 每次循环生成 h有序数组（h 个有序数组） 即 （h 0）, （h+1 1）, （h+2 2）, .... * 如果右边的值小于左边的值时，交换； * 并退回到左边的位置，重新排序，循环比较（j>

=h）。 * Because swapping may cause the original ordered array to be out of order, you need to go back and recompare * When h is decremented to 1, it is equivalent to inserting a partially ordered array. * */ while (h >= 1) { //Console.WriteLine(h); for (int i = h; i

< n; i++) { //Console.WriteLine(i+","+(i - h)); for (int j = i; j >

= h && Less(a[j], a[j - h]); j -= h) { Exch(a,j,j-h); //Console.WriteLine("J:" + (j- h)); } } h = h / 3; } timer.Stop(); usedTimes = timer.ElapsedMilliseconds; } }

Looking at Hill sort from another angle, insertion sort is moving each element larger than it one to the right, and Hill sort is moving the distance from 1 to h before swapping to an element larger than it.

Hill sorting is more efficient because it reduces inversion by turning arrays into multiple partially ordered arrays. At the beginning of the sort, each subarray is very short, and after sorting, the subarrays are partially ordered, which is very suitable for insertion sort. The degree to which the subarray is partially ordered depends on the choice of incremental sequences. (How to choose?)

In contrast to selection sort and insertion sort, Hill sort can also be used for large arrays, and even random number sort is much faster. The larger the array size, the more obvious the contrast.

The performance analysis of Hill sorting is difficult. Its running time is less than square, and its worst case comparison times are proportional to N ^ 3/2.

If a medium-sized array can be sorted using Hill, it is less code intensive and requires no extra memory space.

The sorting time of the million level does not exceed ten seconds:

count:10000 shell use Milliseconds:6

count:100000 shell use Milliseconds:180

count:1000000 shell use Milliseconds:3226

At this point, I believe everyone has a deeper understanding of "how to achieve Hill sorting in C#," so let's actually operate it! Here is the website, more related content can enter the relevant channels for inquiry, pay attention to us, continue to learn!