Insertion Sort just like we Sort cards (left to right, smallest to largest). We start with the left hand empty, then we pick up a card from the table and insert it into the correct position in the left hand. To find this position, we compare this card with every card in the left hand from right to left until we find the back of a smaller or equal card.

The principle of insertion sort is similar to sorting cards: the data in the array is divided into two sections, sorted and unsorted. Initial sorted range is only one element, is the first element of the array, and then take the unsorted interval of elements in the array of the second element), in a sorted range to find the right insert location will be inserted, and ensure the data sorted interval has been orderly, and repeat the process, until the unsorted range element is empty.

Again, the requirements from the previous article:

Before sorting: 4, 6, 3, 5, 2, 1

Sorted: 1, 2, 3, 4, 5, 6

Algorithm process:

1. Starting with the first element, the element can be considered sorted;

2. Take out the next element and traverse in reverse order in the sorted interval;

3. If the sorted element is larger than the new element, move the sorted element to the next position;

4. Repeat the previous step until the sorted element is found to be less than or equal to the new element. Insert the new element after the sorted element.

5. Repeat steps 2-4.

So let me draw a picture for you to understand

The complete code is as follows for reference only

public class InsertionSort {

    public void sort(int[] arr) {
        int len = arr.length;
        if(len <= 1) {
            return;
        }

        for(int i = 1; i < len; i++) { // Unsorted interval
            int item = arr[i]; // Elements to be sorted

            int j = i-1;
            for(; j >=0; j--) { // Sorted interval
                if(arr[j] <= item) {
                    break;
                } else {
                    arr[j+1] = arr[j]; // Sorted interval elements move backwards}}// The position of the element to be sorted
            arr[j+1] = item; }}}Copy the code
conclusion

1. What is the time complexity of insert sort?

If the data to be sorted is already in order, and if we are looking through the sorted interval in reverse order, we only need to compare one data at a time to determine the insertion position. So in this case, the best time complexity is O(n) (note that this is backwards traversal).

If the data to be sorted is exactly the opposite, each insert is equivalent to inserting new data in the first position of the array, and a large amount of data needs to be moved, so the worst time complexity is O(n^2).

2. What is the spatial complexity of insertion sort?

As can be seen from the above implementation process, insert sort has no additional storage space, so its space complexity is O(1). This is a sort in place algorithm.

3. Is insertion sort a stable sorting algorithm?

In insertion sort, for elements with the same value, we can insert the new element after the sorted interval elements, so that the original order can remain unchanged, so the insertion sort is a stable sorting algorithm.

“More exciting content please pay attention to the public number geekyMV, like please share to more friends oh”