Insert sort, also commonly known as direct insert sort. It is a very swimming algorithm for sorting a small number of elements. Insertion sort is one of the simplest sorting methods. The basic idea is to insert a record into an already ordered table, thus creating a new ordered table with the number of records increasing by one. In the process of its implementation, the use of a double-layer loop, the outer loop to all elements except the first element, the inner loop to the ordered list in front of the current element to be inserted position search, and move.

The basic idea: Each step inserts one of the data to be sorted into the previously sorted sequence until all the elements are inserted into the correct position.

The average time complexity of insertion sort is O(n^2), and the space complexity is constant order O(1). The specific time complexity is also related to the order of array.

In insertion sort, when the array to be sorted is ordered, it is optimal, and it only needs to compare the current number with the previous number, and then it needs to compare N minus 1 times, and the time complexity is O(N). The worst case is that the array to be sorted is in reverse order, which is where the most comparisons are made, and the worst case is O(n^2).

The pseudo-code for insert sort is:

INSERTION-SORT(A)
for j = 2 to A.length
    key = A[j]
    // Insert A[j] into the sorted sequence A[1, j - 1]
    i = j - 1
    while i > 0 and A[i] > key
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = key
Copy the code

To convert to Go code, there are:

package main

import "fmt"

func insertionSort(arr []int) []int {
	for j := 0; j < len(arr); j++ {
		key := arr[j]
		i := j - 1
		for i >= 0 && arr[i] > key {
			arr[i+1] = arr[i]
			i = i - 1
		}
		arr[i+1] = key
	}
	return arr
}

func main(a) {
	fmt.Println(insertionSort([]int{5.2.4.6.1.3}}))Copy the code

Of course, you can also write a section of automatic data generation test code, the test, 10W level data 2.67s, 100W level data 312.33s:

func main(a) {
	var arr []int
	for i := 0; i < 1000000; i++ {
		arr = append(arr, rand.Intn(1000000))
	}
	s := time.Now()
	insertionSort(arr)
	fmt.Println(time.Now().Sub(s))
}
Copy the code