Easy to win insert sort

1、 Insertion sort

What is insert sort ？

A focus on Insert , Extract one element at a time as a temporary element , After comparing and moving in turn

Core rules ：

• In the first round , Pull away The penultimate element at the end of the array , As Temporary elements
• Compare the temporary element with the element after the array ： If The value of the following element is smaller than that of the temporary element , be The following element moves left
• If the following element is larger than the temporary element , Or it has moved to the end of the array , Then insert the temporary element into the current air attack
• Repeat the above steps , To complete the order

The core logic here is through each iteration , take Some elements are arranged in order , After a certain number of iterations , Achieve the effect of final sorting

give an example ：

The first iteration ：

1. First select the penultimate element 5 As a temporary element
2. Compare the temporary elements with the following elements in turn ,5 Than 3 Big , So it will 3 One left
3. At this point, we have reached the end of the array , Direct will 5 Insert

Second iteration ：

1. First select the penultimate element 7 As a temporary element
2. Compare with the following elements in turn ,7 Than 3 Big , take 3 One left
3. Next 7 And 5 Compare ,7 Than 5 Big , So it will 5 One left
4. The end of the array has been reached , Direct will 7 Insert

The third iteration ：

1. First select the penultimate element 4 As a temporary element
2. Compare with the following elements in turn ,4 Than 3 Big , take 3 One left
3. 4 Than 5 Small , Direct will 4 Insert the current gap position

We can find out ： Each iteration can add The elements at the end are in order

Time complexity ：

• The best situation

  If all the elements are arranged in ascending order , We Each iteration does not require moving elements , So time complexity is O(N)

• The worst case scenario

  If all the elements are in descending order , We Each iteration and the comparison in the iteration need to move , under these circumstances , The number of steps to compare is ：O((N^2 + N) / 2), The number of steps to move is ：O((N^2 + N) / 2). So the worst case is ：O(N^2 + N), Ignore that the constant is ：O(N^2)

The code is as follows ：

public static void insertSort(int[] array) {
    
	//  Start from the penultimate place , Traverse to the end 0 position , Traverse  N-1  Time 
    for (int i = array.length - 2; i >= 0; i--) {
    
      	//  Store the currently extracted elements 
      	int temp = array[i];
      	//  Start traversing from the right side of the extracted element 
      	int j = i + 1;
      	while (j <= array.length - 1) {
    
        	//  If an element , Less than temporary elements , Then this element moves left one 
        	if (array[j] < temp) {
    
          		array[j - 1] = array[j];
        	} else {
    
          		//  If it is greater than , Then insert the temporary element directly , And then exit the loop 
          		array[j - 1] = temp;
          		break;
        	}
        	j++;
      	}

      	//  Deal with reaching the tail 
      	if (j == array.length) {
    
        	array[j - 1] = temp;
      	}
    }
}

Bubble sort vs Selection sort vs Insertion sort

Bubble sort and insert sort can refer to orange Easily get bubble sort and select sort This article ~

First , Bubble sort is definitely poor . Selection sorting and insertion sorting depend on the situation

If The original array itself has many elements that have reached the desired sorting state and are in good order , So choose Insertion sort （ For example, the best case cited above , near O(N) ）. Otherwise select Selection sort

therefore , In practice , Or we should choose the corresponding algorithm according to the characteristics of real data

2、 Optimize insert sort - Bisection insertion sort

The core logic of the insertion algorithm is to find the location of the temporary element that should be inserted , It is similar to querying in an ordered array , Find where the element should be inserted

As shown in the figure ：

The pictures are selected from the official website of youkeda learning

The second iteration is equivalent to the result of the first iteration [3,5] Search for 7 Where it should be inserted . The third iteration is equivalent to the result of the second iteration [3,5,7] Search for 4 Where it should be inserted

In fact, for this kind of ordered list , Loop traversal is not the optimal solution , There's a better way ： Dichotomy search

therefore , The efficiency of sorting can be further improved by combining insertion sorting and binary search

Bisection method

//  Find the location of the index that should be inserted 
public static int searchIndex(int[] array, int left, int right, int aim) {
    
    while (left < right) {
    
        int middle = (right + left) / 2;
        int value = array[middle];
        if (value < aim) {
    
            left = middle + 1;
        } else {
    
            right = middle - 1;
        }
    }
    //  If the final element is still larger than the target element , Move the index position to the left （ Judge the current element and the target element , See if you need to insert before the current element ）
    if (array[left] > aim) {
    
        return left - 1;
    }
    //  Otherwise, it is to return to the current position 
    return left;
}

array： Original array

left and right： The interval to be inserted

aim： Target element to be inserted

Insert sort code optimization

Modify the insertion sort code again , Direct use of searchIndex The insertion position queried ：

public static void insertSort(int[] array) {
    
    //  Start from the penultimate place , Traverse to the end 0 position , Traverse  N-1  Time 
    for (int i = array.length - 2; i >= 0; i--) {
    
      	//  Store the currently extracted elements 
      	int temp = array[i];
      	int index = searchIndex(array, i+1, array.length-1, temp);
        
        //  According to the inserted index position , Move and insert the array . After obtaining the position to be inserted , Move the following elements in turn , Then insert 
        int j = i + 1;
        while (j <= index) {
    
            array[j - 1] = array[j];
            j++;
        }
        array[j - 1] = temp;
    }
}

I hope this article can get your approval ~~~ If you think this article is useful, remember to give the thumbs-up + Focus on , Or share it with your friends , I also hope you can give little orange some suggestions , Let's cheer together ！