Detailed interpretation of Hill sorting algorithm and related Java code implementation

Hill sort (Shell's sort) is a very "magical" sorting algorithm. It is called "magical" because no one can clearly explain what its performance is. Hill sorting due to DL. Shell was named after it was proposed in 1959. Since C. A. R. Hoare proposed quick sort in 1962, quick sort is generally used because it is simpler. However, many mathematicians are still working tirelessly to find the optimal complexity of Hill sorting. As ordinary programmers, we can learn from Hill's ideas.
By the way, before the emergence of Hill sorting, there was a common view in the computer industry that "sorting algorithms cannot break through O(n2)". The emergence of Hill sorting broke this curse, and soon, algorithms such as quick sort came out one after another. In this sense, Hill sorting leads us into a new era.

Algorithm overview/ideas
The proposal of Hill sorting is mainly based on the following two points:
1. The insertion sort algorithm can approximately reach O(n) complexity when the array is basically ordered. degree, extremely efficient.
2. However, insertion sort can only move data one bit at a time, and the performance will deteriorate rapidly when the array is large and basically disordered.

Based on this, we can use a grouped insertion sort method. The specific method is: (take a 16-element array as an example)
1. Select an increment delta, which is greater than 1. Select the subarray from the array according to this increment for a direct insertion sort. For example, if the selected increment is 5, the elements with indexes 0, 5, 10, and 15 will be sorted.
2. Keep the incremental delta and move the first element in sequence for direct insertion sorting until one round is completed. For the above example, the arrays [1, 6, 11], [2, 7, 12], [3, 8, 13], [4, 9, 14] are sorted in sequence.
3. Reduce the increment and repeat the above process until the increment is reduced to 1. Obviously, the last time is direct insertion sorting.
4. Sorting completed.
As can be seen from the above, the increment is constantly decreasing, so Hill sorting is also called "shrinking increment sorting".

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) { 
    // 计算出最大的h值 
    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); 
        } 
      } 
      // 计算出下一个h值 
      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(); 
  } 
  
}

Running 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 sorting can be chosen arbitrarily, and the only condition required is the last One must be 1 (because it must be ordered by 1). However, different sequence selections will have a great impact on the performance of the algorithm. The code above demonstrates two increments.
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 a sequence ordered by 4 and then by 2).
The following are some common increment sequences.
The first increment is the increment originally proposed by Donald Shell, which is reduced by half until 1. According to research, using Hill increment, the time complexity is still O(n2).
The second increment Hibbard: {1, 3, ..., 2^k-1}. The time complexity of this incremental sequence is approximately O(n^1.5).
The third increment Sedgewick increment: (1, 5, 19, 41, 109,...), the generated sequence is either 9*4^i - 9*2^i + 1 or 4^ i - 3*2^i + 1.

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

Applicable scenarios of the algorithm
Although Shell sorting is fast, it is insertion sorting after all, and its order of magnitude is not as fast as the rising star-quick sorting O(n㏒n). Shell sorting is not a good algorithm in the face of large amounts of data. However, it is perfectly fine for small to medium sized data.

For more detailed explanations of the Hill sorting algorithm and related Java code implementation related articles, please pay attention to the PHP Chinese website!