preface

The concept is introduced

• Hill sort is a more efficient and improved version of the insertion sort algorithm.
• It groups the records in increments by subscript, and sorts each group by direct insertion sort algorithm. As the increments decrease, each group contains fewer and fewer keywords, and when the increments decrease to 1, the entire file is grouped exactly into a group. At this point the algorithm terminates.

The principle of interpretation

Taking the sequence [41 24 34 2 19 17] as an example, the realization principle of Hill sorting algorithm is illustrated

1. The traversal has not started, and the effect is shown below
   

   

2. As can be seen from the above array, the length of the array is 6, and the artificial selection increment is gap=6/2=3. Therefore, the whole array is divided into 3 subarrays (with the same color as a group), which are [41 2], [24 19], [34 17] respectively. The effect is shown below.
   

   

3. In the first traversal (increment of 3), we insert sort the three subarrays respectively. After insertion sort, the three subarrays become [2 41], [19 24], [17 34]. The effect is shown below.
   

   

4. In the second iteration (increment of 1), we insert sort the entire array [2 19 17 41 24 34], and the effect after insertion sort is shown in the figure below
   

   

5. At this point, hill’s sorting principle is explained.

Time complexity

From the process of Hill sorting, we can see that the time complexity of the algorithm is closely related to the increment. If the increment is 1, then Hill sort is insertion sort; If the increment is Hibbard increment, hill sort algorithm is obviously different from insertion sort.

So according to the concept of time complexity, when the increment is 1, the time complexity of Hill sorting algorithm is O(N^2); The time complexity of Hill sorting is O(N^3/2) for Hibbard increments.

Spatial complexity

• Space complexity is a measure of the amount of storage space temporarily occupied by an algorithm during its running.
• Since the size of the space occupied by Hill sorting algorithm remains unchanged, the spatial complexity of the algorithm is O(1) according to the meaning of space complexity.

Advantages and disadvantages of the algorithm

• Advantages: fast speed; Less movement
• Disadvantages: unstable; Incremental selection is variable and can only be selected empirically based on the amount of data

Results show

Download the source code

• Please reply “algorithm source code” in the public number to get the top ten classic sorting algorithm source code

For more algorithm learning, please pay attention to my public number