Introduction to the

Insert sort, also commonly known as direct insert sort. It is an efficient algorithm for sorting a small number of elements. Insertion sort is one of the simplest sorting methods. Its basic idea is to insert a record into an ordered list that has been ordered, thus forming an ordered list. In its implementation process, the use of double-layer loop, the outer loop except for the first element of all elements, the inner loop to the current element in front of the ordered table to insert location search, and move.

Time complexity

O(n^2)

Thought analysis

Order: From smallest to largest

  1. There are two tables, one of which contains the sorted (ordered) element, and the default is the first element in the array. Let’s put the unsorted elements in the other table B
  2. Each time the first element in table B is placed in the appropriate position in table A, all data in table B is retrieved and sorted.

See the code comments for details.

Code implementation

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {9.2.5.3.1};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertSort(int[] arr) {
        // Order from smallest to largest
        // 1. There are two tables, and one table contains the sorted (ordered) element, by default, the first element of the array. Let's put the unsorted elements in the other table B
        // 1. Select * from B and place the first element in A.

        for (int k = 1; k < arr.length; k++) {
            // The index of the last element in table A before the while loop executes
            int aIndex = k - 1;
            // select * from B
            int bVal = arr[k];

            while (
                    // Exit the loop after comparing all the data in table A
                    aIndex > -1
                    // select * from table B and select * from table A
                    // If the element in table B is smaller than the element in table A, then the element in table A is moved one bit later, and the first bit is reserved for bVal
                    && bVal < arr[aIndex]
            ) {
                // This is just a process of moving the element, moving the current element to a later position, because the current position is reserved for the element taken from B
                // The following example is a simulation of the exchange process, not the actual order, to understand the exchange logic.
                // int[] arr = {9, 2, 5, 3, 1};
                // Assume aIndex = 2
                // arr[3] = arr[2] => {9, 2, 5, 5, 1}
                // aIndex--;
                // Next loop aIndex = 1
                // arr[2] = arr[1] => {9, 2, 2, 5, 1}
                // aIndex--;
                // Next loop aIndex = 0
                // arr[1] = arr[0] => {9, 9, 2, 5, 1}
                arr[aIndex + 1] = arr[aIndex];
                aIndex--;
            }
			// If the current index changes, it means that there is a value greater than bVal in the ordered list.
            // this means that there is no value greater than bVal in table A. (Optimization effect)
            if (aIndex + 1! = k) { arr[aIndex +1] = bVal; }}}}Copy the code

Run output:

[1, 2, 3, 5, 9]

conclusion

The core of the algorithm is to compare the first element in table B with table A one by one, and compare the last element in table A to find the appropriate place to put it in. When the elements in table B are finished, the sorting is completed.