For hill sort see baidu Encyclopedia definition
Let’s look at the implementation of the C code
#define EXCHANGE(num1, num2) { num1 = num1 ^ num2; num2 = num1 ^ num2; num1 = num1 ^ num2; } void shellSort( int num[], int count ) { int gap, i, j; for( gap = count / 2; gap >0; Gap = gap / 2) // Split the whole sequence, the element spacing gap(i.e. increment) {for(I = gap; i < count; I ++) // Direct insertion sort {for(j = i-gap; j >= 0 && num[j] > num[j + gap]; j = j - gap ) { EXCHANGE( num[j], num[j + gap] ); }}}}Copy the code
Let’s take a look at the code execution
This is the first time the original array, values for half the number of array element spacing gap, gap = 5, compare num [0] and num is the size of the [5], 0 < 3 don’t need to exchange, down to compare num [1] and num [6], the size of the 8 > 7 exchange position of two Numbers
I’m going to go down and compare 1 and 9, I don’t have to switch, I’m going to go down 5 and 2 and I’m going to switch the two numbers if 5 goes above 2
I’m going to compare 4 and 6, I don’t need to switch places, I’m done comparing the array, I’m going to go down to half the gap, gap=5, half of it is 2.5 but it’s an integer, so the gap is going to be 2.
Down to compare num [0] and num [2], 0 < 1, do not need to exchange position, continue to compare 7 and 2, 7 > 2 need to swap places.
Come down and compare 1 and 4, you don’t have to switch places. To continue comparing 7 and 3, we need to switch places.
So we’re going to go down and we’re going to swap 8 and 5
Nine and six switch places
After switching places between 9 and 6, we’re at the end of the array, but we’re not done yet, because the data at the front of the array has changed, so we’re going to compare it forward,
The spacing between the elements is 2, so 6 needs to be compared with the 7 before it by one digit. The number before it is larger than the number after it needs to switch positions once, so 6 and 7 switch positions once.
And then the six is compared to the three, so there’s no swap, there’s no swap between the four and the one, there’s no swap between the three and the two, there’s no swap between the one and the zero. The trip is now complete.
Next, the distance between elements is reduced to half of the original, half of 2 is 1, so the gap becomes 1, and the two adjacent elements are compared.
You don’t swap 0 and 2, you swap 2 and 1.
The 5 and the 6 need to be swapped
After swapping positions nine times, the array sort is complete.
Let’s test the number of swaps we need in the worst case
In the worst case, 13 swaps are required.
Let’s go down and see how many times we need to switch in the best case.
The best case is zero.
Let’s test the number of times and execution time required to randomly generate 10000 data.
Here is a GIF to illustrate the sorting process
