Hill sorting graphic explanation + code implementation

Hill sort is also an insert sort , It is Direct insert sort An improved one More efficient Version of , Also known as Reduced delta sort .

nature ：1、 Time complexity ：O(nlogn) 2、 Spatial complexity ：O(1)

Let's first introduce direct insertion sorting , Understand the direct insertion sort , Hill sort is easy to understand , The implementation code is also improved by the code of direct insertion sorting .

1、 Direct insert sort

1.1、 Algorithm steps

First, think of the first element as an ordered sequence , Think of the second element to the last as an unsorted sequence .
Scan the unordered sequence in turn , Insert each element scanned into the appropriate location in the ordered sequence .（ Ordered sequence length after each insertion +1, Unsorted sequence length -1）

1.2、 Code implementation ：

/** *  Direct insert sort  */
public class InsertSort {
    
    public int[] sort(int[] arr) {
    
        for (int i = 1; i < arr.length; i++) {
    
            int temp = arr[i];
            int j = i - 1;
            for (; j >= 0 && arr[j] > temp; j--) {
    
                arr[j + 1] = arr[j];
            }
            arr[++j] = temp;
        }
        return arr;
    }
} 

2、 Shell Sort

2.1、 Algorithm steps

The basic idea of Hill's ranking is ： First, the whole record sequence to be sorted is divided into several subsequences according to a certain increment for direct insertion sorting . To be recorded throughout the sequence " The basic order " when , Then directly insert and sort all records （ Increment of 1 when ）.
Usually, the increment is in the order of N/2、N/2/2、…、N/2^i、…、1.

For example, there are the following arrays ,N=10

The first round ：
The incremental gap=N/2=5, The entire array is divided into 5 Subsequence , Namely [8,3]、[9,5]、[1,4]、[7,6]、[2,0], Direct insertion sorting is carried out respectively .

After sorting the subsequences respectively, they are

The second round ：
The incremental gap=N/2/2=2, The entire array is divided into 2 Subsequence , Namely [3,1,0,9,7]、[5,6,8,4,2], Direct insertion sorting is carried out respectively .

After sorting the subsequences respectively, they are

The third round ：
The incremental gap=N/2/2/2=1, The entire array is divided into 1 Subsequence . At this point, it can be regarded as no grouping , Instead, all records are directly inserted and sorted .

After the first two rounds of sorting , At this point, the array is basically in order , So the efficiency of direct insertion sorting is very high , You don't need to move a lot of array elements to complete the sorting of the entire array .

2.2、 Code implementation

It can be improved based on the code of direct insertion sorting

/** *  Shell Sort  *  Hill sort is an improvement on insert sort , According to a certain gap value , Continuously insert and sort the array  */
public class ShellSort {
    
    public int[] sort(int[] arr) {
    
        // The classic Hill algorithm gap The value is N/2, N/4, ......  until gap The value is 1
        for (int gap = arr.length / 2; gap >= 1; gap = gap / 2) {
    
            //gap What's the value , How many subarrays will there be , And the beginning of each sub array is the front of the original array gap Elements 
            // Insert and sort each sub array 
            for (int n = 0; n < gap; n++) {
    
                // Insert and sort each sub array , Note, however, that the spacing between each element of the subarray is gap
                for (int i = n + gap; i < arr.length; i = i + gap) {
    
                    int temp = arr[i];
                    int j = i - gap;
                    for (; j >= 0 && arr[j] > temp; j = j - gap) {
    
                        arr[j + gap] = arr[j];
                    }
                    j = j + gap;
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
}

3、 Operating efficiency comparison

Hill sort is an improved version of direct insert sort , More efficient execution .

Randomly generate a size of 100000 Array of , Use direct insert sort , Calculate execution time

    public static void main(String[] args) {
    
        // Define a length of 100000 Array of 
        int[] arr = new int[100000];
        Random random = new Random();
        // Random generation int Insert... Into the array in turn 
        for (int i = 0; i < arr.length; i++) {
    
            arr[i] = random.nextInt(1000000);
        }

        // Instantiate the self - written direct insertion sorting class 
        InsertSort insertSort = new InsertSort();
        long start = new Date().getTime();
        // Sort the array 
        int[] sort = insertSort.sort(arr);
        long end = new Date().getTime();
        System.out.println(" Time consuming " + (end - start) + " millisecond ");

        // Verify order 
        boolean flag = true;
        for (int i = 0; i < sort.length - 1; i++) {
    
            if (sort[i] > sort[i + 1]) {
    
                flag = false;
                break;
            }
        }
        System.out.println(" Is it orderly ？" + (flag ? " yes " : " no "));
    }

The execution result is

 Time consuming 746 millisecond 
 Is it orderly ？ yes 

Use Direct insert sort consumes 746ms Time for

Next, use Hill sort , The execution result is ：

 Time consuming 14 millisecond 
 Is it orderly ？ yes 

You can see that the same pair has a size of 100000 To sort a random array of , Hill sort only uses 14ms, The efficiency is greatly improved