Insertion sort

Insertion sort is a simple and effective comparison sorting algorithm.

Idea: During each iteration the algorithm randomly removes an element from the input sequence and inserts the changed element into the correct position in the sequence to be sorted. This process is repeated until all input elements have been selected once and the sorting is complete.

Insertion sort is a little bit like the way we used to grab cards when we were kids, if we grab a card, we put it in our hand; When you grab the second card, you compare it to the first card in your hand, place it on the left less than the first card in your hand, and otherwise, place it on the right.

Therefore, repeat this for all cards, so that the correct sorting order is inserted each time until the cards are exhausted.

The demo

Suppose we need to sort from smallest to largest, and the animation looks like this:

Go code implementation

package main
import "fmt"
func main(a) {
    arrays := []int{6.2.5.8.9.3.1}
    length := len(arrays)
    insertionSort(arrays, length)
    for i := 0; i < length; i++ {
        fmt.Printf("%d ", arrays[i])
    }
}
func insertionSort(unsorted []int, length int) {
    for i := 0; i < length; i++ {
        var insertElement = unsorted[i]
        var insertPosition = i
        for j := insertPosition - 1; j >= 0; j-- {
            if insertElement < unsorted[j] {
                unsorted[j+1] = unsorted[j]
                insertPosition--
            }
        }
        unsorted[insertPosition] = insertElement
    }
}
Copy the code

Running results:

[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\ go data structure \main.go" 1 2 3 5 6 8 9Copy the code

conclusion

Insertion sort is simple to implement, easy to understand, high efficiency when the amount of data is small, the actual running efficiency of the algorithm is better than selection sort and bubble sort.

Time complexity: The worst time complexity of the algorithm is O(n2)O(n^2)O(n2). If the input sequence is already pre-sorted, the optimal time complexity is O(n+d)O(n+d)O(n+d) O(n+d). DDD is the number of reversals.

Space complexity: The space complexity is O(1)O(1)O(1), that is, no other auxiliary space is used.

Stability: Insertion sort is a stable sorting algorithm that preserves the original order of input data while maintaining the same key value.

Article inspiration: visualgo.net/zh