[eight sorts ①] insert sort (direct insert sort, Hill sort)

Catalog

Said in the previous

One 、 Direct insert sort （Straight Insertion Sort）

• The algorithm idea of direct insertion sorting
• When writing code  

【 Summary of the features of direct insertion sort 】 

• Complexity analysis of direct insertion sorting
• Stability analysis of direct insertion sorting
• Directly insert the usage scenario of sorting

Two 、 Shell Sort （Shell Sort）

• The basic idea of Hill ranking method
•   A summary of the characteristics of Hill sort ：
• Code implementation

【 A summary of the characteristics of Hill sort 】

• The complexity of hill sorting  
• Stability of Hill sort

Said in the previous

About the order , I believe you must be familiar with , We have seen many sorts in life , For example, when searching shopping websites , There are orders according to price 、 Sort according to the praise 、 Sort by sales , We make the content have a certain order according to keywords , This is sorting .

Sort ： So called sorting , Is to make a string of records , According to the size of one or some of the keywords , An operation arranged in ascending or descending order .
 

Stability of sequencing ： Assume in the sequence of records to be sorted , There are multiple records with the same keyword , If sorted , The relative order of these records remains the same , In the original sequence ,r[i]=r[j], And r[i] stay r[j] Before , In the sorted sequence ,r[i] Still in r[j] Before , We call this sort algorithm stable ; Otherwise it is called unstable .
 

Inner sort and outer sort

• Internal order ： Throughout the sorting process , All records to be sorted are placed in memory .
• External sorting ： Because there are too many records to sort , Cannot be placed in memory at the same time , The whole sorting process needs to exchange data between internal and external storage for many times

The order is mainly Sort based on comparison and Sort without comparison

  The image above 7 Sorting in is based on comparison

One 、 Direct insert sort （Straight Insertion Sort）

Insert the records to be sorted into an ordered sequence one by one according to their key values , Until all the records are inserted , We get a new ordered sequence . In fact, when we play cards , We use the idea of insertion sort .

The algorithm idea of direct insertion sorting

When inserting the i(i>=1) Element time , Ahead array[0],array[1],…,array[i-1] It's in order , Use at this time array[i] The sort code of and array[i-1],array[i-2],… Compare the sort code order of , Find the insertion position array[i] Insert , The elements in the original position move backward in order

Let's use a graph to appreciate the idea of direct insertion sorting algorithm

When writing code  

Let's define a i and j, Sort the array in ascending order , Now let's look at the code with the diagram

As shown in the figure, it is the approximate execution process   

/**
     *  Direct insert sort 
     *  Time complexity  O(n)
     *  Use scenarios ： When the amount of data is small , And has become more orderly 
     * @param array
     */
    public static void insertSort(int[] array){
        for(int i = 1;i< array.length;i++){
            int tmp = array[i];
            int j = i-1;
            for(; j >= 0; j--){
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

【 Summary of the features of direct insertion sort 】 

Complexity analysis of direct insertion sorting

• Time complexity ：O(n^2)

1. The best situation ： The table to be sorted is itself ordered , Complexity O(n)
2. The worst ： The table to be sorted is in reverse order , Complexity O(n^2)

• Spatial complexity ：O(1)

Stability analysis of direct insertion sorting

It is stable.

We found that

  If this is >= , Then it's unstable

Why is its essence stable ？

If it is a stable sort , We can implement it as an unstable sort

But if it is not a stable sort , Then it is impossible to become a stable sort

Directly insert the usage scenario of sorting

When the amount of data is small , And has become more orderly  

Two 、 Shell Sort （Shell Sort）

introduction ： We know , The first condition of an excellent sorting algorithm is Speed , People think of many ways to improve the speed of sorting , For a long time , People found that although there are many kinds of sorting algorithms , But the complexity of time is O(n^2), But finally one day hill sort was born , Hill's order is D.L.Shell On 1959 A sort algorithm proposed in , It's a breakthrough O(n^2) This time complexity is one of the first algorithms

Hill sort also called Reduction increment method .

The basic idea of Hill ranking method

• Choose an integer first , Divide all records in the file to be sorted into gap A set of
• All distances are gap The records are grouped in the same group , And directly insert and sort the records in each group .
• then , Take another new one gap, Repeat the above work of grouping and sorting .
• When they arrive in gap=1 when , All records are arranged in a unified group

  How can we implement it through code , I need to define a i and j  

• i = gap;
• j = i - gap; 

  A summary of the characteristics of Hill sort ：

1. Hill sort is an optimization of direct insert sort .
2. When gap > 1 All the time Pre sort , The goal is to make arrays more ordered . When gap == 1 when , The array is nearly ordered , This will soon . So on the whole , Can achieve the effect of optimization . We can compare the performance test after implementation .
3. The time complexity of Hill sort 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 trees is not fixed

Code implementation

 public 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;
        }
    }
    public static void shellSort(int[] array){
        int gap = array.length;
        while (gap > 1){
            shell(array,gap);
            gap/=2;
        }
        shell(array,1);
    }

【 A summary of the characteristics of Hill sort 】

The complexity of hill sorting  

• Time complexity  

    because gap There are many ways to take , So the time complexity of hill sorting is not certain , first Shell Propose to take gap=n/2,gap =gap/2, until gop =1, later Knuth Propose to take gap =(gop/3)+1. Others have suggested that it is better to take odd numbers , It was also suggested that gap Mutual quality is better . Neither claim has been proved

  So far no one has found the best incremental sequence , It should be noted that , The last increment value of the increment sequence must be equal to 1 Talent  

  Because of our gap Is in accordance with the Knuth The proposed method is , and Knuth A large number of experiments and statistics have been carried out , For the time being, we'll follow

  To calculate the time complexity

• Spatial complexity ：O(1)

Stability of Hill sort

It's not stable