Direct insertion sort of seven sorts

Catalog

1、 The basic idea

2、 Code explanation and Implementation

3、 Feature summary

3.1 Time complexity ：

3.2 Spatial complexity ：

3.3 Suitable for the scene ：

---

Time complexity ：  ~  

Spatial complexity ：

stability ：  Stable       

1、 The basic idea

        Direct insertion sort is a simple insertion sort method , The idea is to insert the numbers to be sorted into an ordered sequence one by one according to their size , Until all the records are inserted .

In the actual , We are playing cards , It is the same as using the idea of insertion sorting .

2、 Code explanation and Implementation

        When inserting the i(i>=1) Element time , Ahead array[0]、array[1].....array[i-1] It's in order .

First step ： Define a j Variable and assign to i-1, At the same time define a val Variable storage array[i] Value .

The second step ： Give Way array[j] And val Compare

         If array[j] Greater than val , Just put array[j] Take a step forward , That is to say array[j+1] = array[j].

         If array[j] Less than or equal to val, Just put val Put it in array[j+1] in .

j must Greater than or equal to 0 , Otherwise it will cross the border .

    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int j = i-1;
            int val = array[i];
            for(; j >= 0 ; j--){
                if(array[j] > val){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1]= val;
        }
    }

3、 Feature summary

3.1 Time complexity ：

When the data is in order , Direct insertion sorting takes the least time , by  

When the data is in order , The outer loop traverses each element , Than before i-1 Both elements are big , Inner loop is equivalent to not executing . The total time is the time to traverse the array .

When the data is in reverse order , It takes the most time , by  

Data in reverse order , Every time you insert the second i Elements , The inner loop must be traversed i-1 Time . When n The number is sorted , It's traversal   Time

 3.2 Spatial complexity ：

        Because direct insertion sort is an internal sort , So the space complexity is zero  

3.3 Suitable for the scene ：

        When the data is basically orderly , Use direct insert sort