Introduction
Hill sorting (reducing incremental method) belongs to the insertion class sorting. It is proposed by Shell. Hill sorting has made simple improvements to direct insertion sorting: it increases the interval between elements in insertion sorting and inserts into these interval elements, so that the data items move across a large span. After these data items are sorted one time, the Hill sorting algorithm reduces the interval of data items and then sorts it, and proceeds in turn. The interval between the data items when these sorting is called increments, and the letter h is used to represent this increment.
The commonly used h sequence is proposed by Knuth. This sequence starts from 1 and is generated by the following formula:
h = 3 * h +1
The program in turn needs to calculate the h sequence in reverse, and should be used
h=(h-1)/3
Code implementation
Implementation code 1:
public static void shellSort(int[] arr){ int temp; for (int delta = arr.length/2; delta>=1; delta/=2){ //Sort each increment once for (int i=delta; i<arr.length; i++){ for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ //Note that the increment and difference are delta temp = arr[j-delta]; arr[j-delta] = arr[j]; arr[j] = temp; } }//loop i }//loop delta}Implementation code 2:
public static void shellSort2(int[] arr){ int delta = 1; while (delta < arr.length/3){//generate delta delta=delta*3+1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ... } int temp; for (; delta>=1; delta/=3){ for (int i=delta; i<arr.length; i++){ for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ temp = arr[j-delta]; arr[j-delta] = arr[j]; arr[j] = temp; } }//loop i }//loop delta} When the above program compares it with the direct insertion method, you will find that the difference between it and the direct insertion sort is that the h in the direct insertion sort will be replaced by 1.
Shell sorting is unstable, its space overhead is also O(1), and the time overhead is estimated to be between O(N3/2) and O(N7/6).