Introduction to the

Insert sort is when the elements to be sorted are inserted into the sorted array to form a new sorted array.

This algorithm is called insertion sort.

Example of insertion sort

Similarly, if we have an array: 29,10,14,37,20,25,44,15, how do we insert sort it?

Let’s look at an insert sort animation to get a sense of it:

Let’s analyze the sorting process.

Eight numbers. We split them into seven rounds.

In the first round, assuming 29 is the sorted array, starting with the second element, insert new elements into the sorted array. That is, insert 10 into array [29]. Get [10].

In the second round, when [10,29] is sorted, select the third element in the array, 14, and insert the sorted array [10,29].

First compare 29 and 14 and find that 29 is greater than 14, move 29 one bit to the right [10,,29], then compare 10 and 14 and find that 10 is less than 14, insert 14 after 10 [10,14,29], and so on.

Insert sort Java program

Let’s look at the Java program:

public class InsertionSort {

    public void doInsertSort(int[] array){
        log.info("The array before sorting is :{}",array);
        int n = array.length;
        // Insert from the second element
        for (int i = 1; i < n; ++i) {
            int key = array[i];
            int j = i - 1;
            //j represents the sorted array before the elements are inserted
            // The sorted array is compared from back to front with the data to be inserted. If it is larger than the data to be inserted, move it one bit to the right
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                    j = j - 1;
            }
            // The last j+1 position is where the new element needs to be inserted
            array[j + 1] = key;
            log.info("The array sorted by {} round is :{}", i+1, array); }}public static void main(String[] args) {
        int[] array= {29.10.14.37.20.25.44.15};
        InsertionSort insertionSort=newInsertionSort(); insertionSort.doInsertSort(array); }}Copy the code

Running results:

Time complexity of insert sort

As you can see from the code, insert sort has a for loop, and within the for loop there is a while loop.

So the time of insertion sort is order n ^ 2.

The code address of this article:

learn-algorithm

This article has been included in www.flydean.com/algorithm-i…

The most popular interpretation, the most profound dry goods, the most concise tutorial, many tips you didn’t know waiting for you to discover!

Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!