Hill sort of sorting

Catalog

Preface

One 、 What is Hill sort

Two 、 Specific code implementation

3、 ... and 、 Spatial complexity , Time complexity and stability

summary

---

---

Preface

      Previously, we learned about direct insertion sorting , Direct insertion sorting is used when the data is in reverse order , Time complexity will reach O(N^2), This is a high time complexity for a sort , So today we will optimize the direct insertion sort , The more ordered the data, the faster the speed of direct insertion sorting is used to optimize it .

---

One 、 What is Hill sort

        Hill's ranking method is also called reducing increment method . The basic idea of Hill's ranking is ： Divide all the records in the file to be sorted into groups （ The specific grouping is a complex problem , This function changes with the data , It's an unsolved problem , So far, there is no good incremental sequence to solve , It can be said that this incremental sequence can be taken in various ways , However, it should be noted that the value in the incremental sequence should not be divided 1 The common factor outside is to try to be prime , And the last increment value must be taken 1 To end the overall sorting , All the previous sorts are pre sort , The last increment sequence is 1 Time is the real sort ）, All records with the distance of this group number are divided into the same group , And sort the records in each group . Then repeat the above grouping and sorting . When the number of groups reaches 1 when , The sorting of the overall number of groups can be completed by arranging all data records in a unified group . The specific sorting method still uses direct insertion sorting, but as the whole sequence becomes more and more orderly, the speed will be faster , Therefore, Hill sort is the optimization of direct insertion sort .

 

 

Two 、 Specific code implementation

     /**
     *  In fact, it is a direct insertion sort 
     * @param array  Sequence to be sorted 
     * @param gap  Group number 
     */
    public static void shell(int[] array,int gap) {
        for (int i = gap + 1; i < array.length; i++) {
            int j = i - gap;
            int tmp = array[i];
            for (; j >= 0; j -= gap) {
                if(tmp < array[j]){
                    array[j + gap] = array[j];
                }else{
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            shell(array,gap);// Sort by changing the number of groups each time 
            gap /= 2;
        }
        shell(array,1);// Make sure the end is 1 Group 
    }

3、 ... and 、 Spatial complexity , Time complexity and stability

 Time complexity ：（ Increment related ）O(n ^ 1.3 - n ^ 1.5)
 Spatial complexity ： O(1)( No more variables are used ) 
 stability ： unstable （ If there is a jump change in the sorting process, it is unstable ）

---

summary

        Hill sort is an optimization of direct sort , In fact, we can divide the specific groups randomly, but in the end, we must press 1 To distribute , Then it is to sort the whole , This also optimizes the insertion sort , But Hill sort is rarely used , But we must know how to do this ！