Shell Sort

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

Hill sort is an improved method based on the following two properties of insertion sort:

  • Insertion sort has high efficiency when it operates on almost ordered data, that is, it can achieve the efficiency of linear sort.
  • But insert sort is generally inefficient because it can only move data one bit at a time;

The basic idea of Hill sorting is that the whole sequence of records to be sorted is divided into several sub-sequences for direct insertion sorting respectively. When the records in the whole sequence are “basically ordered”, the whole records are directly inserted in sequence.

Algorithm description
  1. Select a delta sequence T1, T2… , where Ti >tj, tk=1;
  2. Sort the sequence k times according to the number of incremental sequences k;
  3. In each sort, the sequence to be sorted is divided into several sub-sequences of length M according to the corresponding increment TI, and each sub-table is sorted by direct insertion. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.
example
Array:8  9  1  7  2  3  5  4  6  0Narrow the increment: gap = length/2 = 5Grouping:8.3]  [9.5]  [1.4]  [7.6]  [2.0[First time:3  5  1  6  0  8  9  4  7  2Narrow the increment: gap = gap/2 = 5/2 = 2Grouping:3.1.0.9.7]  [5.6.8.4.2[Second time:0  2  1  4  3  5  7  6  9  8Narrow the increment: gap = gap/2 = 2/2 = 1The third time:0  1  2  3  4  5  6  7  8  9The end of theCopy the code

It’s basically insertion sort plus incremental grouping to sort.

Algorithm complexity

Space complexity: O(1)

Time complexity:


O ( n squared ) The worst result Order n ^ 2, worst case

O ( n 1.3 ) The average results O(n^{1.3}) average results

O ( n ) The best results Order n is the best result

Sorting is unstable, and two previously equal parameters may be ranked first.

Code implementation
 public static void shellSort(int[] arr) {
        int len = arr.length;
        for (int gap =len / 2; gap > 0; gap = gap / 2) {
            for (int i = gap; i < len; i++) {
                int j = i;
                int current = arr[i];
                while (j - gap >= 0&& current < arr[j - gap]) { arr[j] = arr[j - gap]; j = j - gap; } arr[j] = current; } System.out.println(Arrays.toString(arr)); }}Copy the code

The results

Input array:int[] arr = {8.9.1.7.2.3.5.4.6.0};
[3.5.1.6.0.8.9.4.7.2]
[0.2.1.4.3.5.7.6.9.8]
[0.1.2.3.4.5.6.7.8.9]
Copy the code

But following the steps above, at this point we can see that the results are consistent.