当前位置：网站首页>Hill sort of seven sorts

Hill sort of seven sorts

2022-07-27 22:29:00 【Weiweiqin】

Catalog

1、 The basic idea

2、 Code explanation and Implementation

① grouping

② In group sorting

3、 Feature summary

Time complexity ： $O(n^{1.25})$ ~ $O(1.6n^{1.25})$
Spatial complexity ：
stability ： unstable

1、 The basic idea

Hill sort is a kind of insertion sort , Also known as the reduced increment method . The idea is to choose an integer first gap , Divide the array to be sorted into gap The number of is divided into a group , And insert and sort the numbers in each group . then , take , Repeat the above grouping and sorting . When gap = 1 when , All numbers are arranged in the same group .

2、 Code explanation and Implementation

Hill sort implementation can be divided into two steps ：
1： grouping
2： In group sorting

① grouping

We must first give gap Value , Usually The length of the array will be assigned to gap, And then to gap Sort the steps in groups . next gap Divide 2, Then carry out the above operations .

Last We must sort the array as a whole , Because each group is likely to drop a few numbers , So finally gap Be sure to assign a value of 1.

② In group sorting

The intra group sort is roughly the same as the insert sort , In insert sort, the outer loop is from 1 Subscript starts inserting , And in Hill sort gap It's changing , So the external circulation should start from gap Start with the subscript , Every time ++, Try to traverse each group to .

Inner loop j from i - gap Start , Subtract... Every time gap, The elements in such a group tend to be in order .

    // Insert sort into group 
    private static void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for(; j >= 0; j -= gap){
                if(array[j] > tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    // grouping 
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);// Sort the array as a whole

3、 Feature summary

1. Hill sort is an optimization of direct insert sort .

2. When gap > 1 It's all pre sorted , The purpose is to make the array closer to order . When gap == 1 when , The array is nearly ordered , This will soon . So on the whole , Can achieve the effect of optimization .

3. The time complexity of hill sorting is not easy to calculate , because gap There are many ways to get the value of , Makes it difficult to calculate , Therefore, the time complexity of hill sorting given in many books is not fixed . We can temporarily follow $O(n^{1.25})$ ~ $O(1.6n^{1.25})$ To calculate .