A list,

Hill sort, also known as the descending incremental sort algorithm, is a more efficient and improved version of insertion sort.

Hill sort is an improved method based on the following two properties of insertion sort: 2. Insertion sort is slow for large arrays of random numbers because it swaps only adjacent elements, so elements can only be moved from one end of the array to the other bit by bit.

Hill sort simply improves on insertion sort, swapping non-contiguous elements to sort parts of an array, and eventually using insertion sort to sort locally ordered arrays. (First, the whole large array is basically ordered, and then the large array to insert sort)

Idea: Make any element in an array with h spacing ordered. Such arrays are called h-ordered arrays. When sorting, if H is large, we can move elements far away, making it easier to order smaller h.

Second, the steps

Take d1, an integer less than n, as the first increment, and group all the records in the file. All records whose distances are multiples of D1 are placed in the same group. Direct insertion sequencing was performed in each group. Then, take the second increment d2

Third, the sample

Assuming we have a set of numbers [13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10], we can better describe the algorithm by placing the list in a table with five columns, so that they should look like this:

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
Copy the code

Then we sort each column:

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
Copy the code

[10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45] Now 10 has moved to the correct position, and then we sort it in step 3:

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
Copy the code

After sorting, it becomes:

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
Copy the code

Finally sort by 1 step (this is a simple insertion sort).

Four, code implementation

template<typename T> // You can use integers or floating-point numbers as elements. If you use a class as an element, you need to overload the greater than (>) operator.
void sort(T arr[], int len) {
	int gap, i, j;
	T temp;
	for (gap = len >> 1; gap > 0; gap >>= 1)	// gap is the increment at that time
		/* Do a gap sequence */
		for (i = gap; i < len; i++) {			
			temp = arr[i];		// Save the record Ri to be inserted
                        int j = 0; // The index of the element to be compared in the ordered region. Initially, the comparison starts from the last element in the ordered region
			/* Press the gap to find the insertion point */ 
			for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)	// Sort groups of elements whose step size is gap
				arr[j + gap] = arr[j];	// Big record moves back
			arr[j + gap] = temp;	// Insert record Ri}}int main(a)
{
	int a[10] = { 3.2.5.21.9.10.7.16.8.20 };
	sort(a,10);
	for (int i = 0; i < 10; i++) {
		cout << a[i] << ""; }}Copy the code

Five, the evaluation of

Stability: unstable. We know that a single insertion sort is stable, but in different insertion sorts, the same element may move in its own insertion sort, and finally its stability will be disturbed, that is, the equal data in hill sort may swap places.

Time performance: The average time complexity of Hill sort is O(nlog2n)

Scope of application: Medium size scales perform well, sorting is not optimal for very large data. Not suitable for chain construction

Vi. Reference materials

Sort: Direct insert + Hill sort hill sort sort: Insert sort of Hill sort (reduced incremental sort) plain Classical algorithm series three Hill sort implementation of Chinese MOOC university – Programming fundamentals -6. Problem solving and algorithm fundamentals 3