Detailed interpretation of hill sorting algorithm and related Java code implementation

Hill sort (Shell 's sort) is a very "magical" sorting algorithm. It's "magical" because no one can say exactly what its performance will be. The hill ranking got its name from the introduction of DL. Shell in 1959. Since C.A.R.Hoare proposed quicksort in 1962, it has generally been used because it is simpler. However, many mathematicians have worked tirelessly to find the optimal complexity of hill's sorting. As ordinary programmers, we can learn from hill's ideas.
By the way, before hill sorting, there was a widespread belief in computing that sorting algorithms could not break through O (n2). The advent of hill sort broke the spell, and soon algorithms such as quicksort came along. In this sense, hill sort leads us to a new era.

Algorithm overview/ideas
Hill's ranking is mainly based on the following two points:
1. The insertion sort algorithm can approximate the complexity of O(n) when the array is basically in order, which is extremely efficient.
2. But insertion sort can only move the data one bit at a time, and its performance deteriorates rapidly when the array is large and basically out of order.

Based on this, we can use a grouping insertion sort method :(take an array of 16 elements as an example)
1. Select an increment delta, which is greater than 1, and select a subarray from the array according to this increment for direct insertion sorting once. For example, if you choose an increment of 5, you sort the elements with a subscript of 0,5,10,15.
2. Keep the increment delta and move the first element in turn for direct insertion sort until round 1 is complete. For the above example, sort the arrays [1,6,11], [2,7,12], [3,8,13], [4,9,14] in turn.
3. Reduce the increment and repeat the process until the increment is reduced to 1. Obviously, the last time is direct insertion sort.
4. Sorting is complete.
As you can see from the above, the increments are decreasing, so the hill sort is also known as "shrink delta sort".

Code implementation

package sort; 
 
public class ShellSortTest { 
  public static int count = 0; 
 
  public static void main(String[] args) { 
 
    int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; 
    print(data); 
    shellSort(data); 
    print(data); 
 
  } 
 
  public static void shellSort(int[] data) { 
    //  So let's figure out the largest h value  
    int h = 1; 
    while (h <= data.length / 3) { 
      h = h * 3 + 1; 
    } 
    while (h > 0) { 
      for (int i = h; i < data.length; i += h) { 
        if (data[i] < data[i - h]) { 
          int tmp = data[i]; 
          int j = i - h; 
          while (j >= 0 && data[j] > tmp) { 
            data[j + h] = data[j]; 
            j -= h; 
          } 
          data[j + h] = tmp; 
          print(data); 
        } 
      } 
      //  To calculate the 1 a h value  
      h = (h - 1) / 3; 
    } 
  } 
 
  public static void print(int[] data) { 
    for (int i = 0; i < data.length; i++) { 
      System.out.print(data[i] + "\t"); 
    } 
    System.out.println(); 
  } 
 
} 

Operation results:

5  3  6  2  1  9  4  8  7   
1  3  6  2  5  9  4  8  7   
1  2  3  6  5  9  4  8  7   
1  2  3  5  6  9  4  8  7   
1  2  3  4  5  6  9  8  7   
1  2  3  4  5  6  8  9  7   
1  2  3  4  5  6  7  8  9   
1  2  3  4  5  6  7  8  9 

Algorithm performance/complexity
The incremental sequence of hill sort can be arbitrary, only 1 is required if the last 1 is 1 (because the order of 1 is guaranteed). However, the performance of the algorithm is greatly affected by the selection of different sequences. The code above demonstrates two deltas.
Remember: it is best not to have a common factor other than 1 for every two elements in the incremental sequence! (obviously, it doesn't make much sense to sort by 4 and then by 2).
Here are some common increments.
The first increment is the one originally proposed by Donald Shell, which is to reduce by half to 1. According to the research, the time complexity of using hill increment is still O(n2).
Increment Hibbard: {1, 3,... , 2 ^ k - 1}. The time complexity of this incremental sequence is approximately O(n^1.5).
Third increment Sedgewick increment :(1, 5, 19, 41, 109...) So it's either 9 times 4 to the i minus 9 times 2 to the i plus 1 or 4 to the i minus 3 times 2 to the i plus 1.

Algorithm stability
We all know that insertion sort is a stable algorithm. However, Shell sort is a multiple-insert process. In one insert, we can ensure that we do not move the order of the same elements, but in multiple inserts, the same elements may be moved in different insert rounds, and the stability will be destroyed finally. Therefore, Shell sorting is not a stable algorithm.

Algorithm applicable scenario
Although Shell sort is fast, it is still insertion sort, and its order of magnitude is not as fast as the upstart, quicksort O(n, n). Shell sorting is not a good algorithm for large amounts of data. However, small - and medium-sized data can be used.