Insert sort of sort

Catalog

Preface

One 、 About direct insertion sorting

Two 、 Specific code implementation

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

summary

---

---

Preface

        We often encounter some problems with arrays , Let's deal with various sequence problems , Often, when it comes to sorting , I feel like I can't do it , Mainly because it is too strange to sort （ The unknown is the most terrifying ）, The so-called sorting is to make a series of numbers use various methods to order , Whether ascending or descending , So I sort out some sort based on comparison , Quick sort , Heap sort , Bubble sort , Shell Sort …… Today's protagonist is direct insertion sorting .

---

One 、 About direct insertion sorting

    Direct insert sort is insert , It's like jumping in line , And if you want to insert, first you have to have something to insert , So you can take out one element in order , Then compare it with other elements , Just make it orderly .

Two 、 Specific code implementation

public class Insert {
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int j = i - 1;
            int tmp = array[i];
            for (; j >= 0; j--) {
                if(array[j] > tmp){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = tmp;//j Back to less than 0 The place of 
        }
    }
}

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

The space complexity is O(1)： No more use of extra space

The time complexity is O(N^2)： In the worst case, change it every time, that is N*N The best case is when it is orderly O(N)（ So the data                                       More orderly , Faster ）

stability ： Stable （ If when judging array[j] > tmp When you add an equal sign, it becomes unstable , A stable sort can                   To become unstable, but an unstable sort cannot become stable ）

---

summary

        Insert sort is one of the few stable sorts in common sort , But the insertion sorting time is too complicated , Insert sort is not often used, but the more ordered the insert sort is, the faster it will be. Therefore, it can be used in the optimization of other sorts , And direct insertion sorting is also relatively simple , After learning, you can prepare for other sorting learning ！