Insert sort directly:
Algorithm idea:
1. The array is divided into two parts: ordered part and unordered part
2. Divide the initial data into ordered parts and unordered parts. In each step, insert the data of an unordered part into the ordered part that has been arranged previously
And so on until all elements are sorted
Average time complexity: O(n2)
Data comparison times: (n - 1) + (n - 2) + (n - 3) +... + 1 = 1/2n2 - 1/2n
Number of data exchanges: (n - 1)
Total complexity: 1/2n2 + 1/2n - 1
Optimal time complexity: O(n2)
Worst time complexity: O(n)
Space complexity: O(1)
Stability: stable
When an element moves from an unordered part to an ordered part, it will move only when it is not equal (greater than or less than), and will not be processed when it is equal
Suitable for the scene: a small number of elements, and basically orderly
Code implementation:
i: number of ordered sequences or left index of unordered sequences
j: It is used to traverse the array, compare the elements to be arranged with the ordered sequence elements, and move the elements

package main

import "fmt"

func main() {
	arr := []int{1, 7, 6, 7, 98, 9, -1, 7, 89, 14, -4, -5, -657}
	insertSort(arr)
	for _, v := range arr {
		fmt.Println(v)
	}
}

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

Insert normal sort:
Algorithm idea:
1. The array is divided into two parts: ordered part and unordered part
2. Divide the initial data into ordered parts and unordered parts. In each step, insert the data of an unordered part into the ordered part that has been arranged previously
3. Wait until all elements are sorted
Average time complexity: O(n2)
Data comparison times: (n - 1) + (n - 2) + (n - 3) +... + 1 = 1/2n2 - 1/2n
Number of data exchanges: (n - 1)
Total complexity: 1/2n2 + 1/2n - 1
Optimal time complexity: O(n2)
Worst time complexity: O(n)
Space complexity: O(1)
Stability: stable
When an element moves from an unordered part to an ordered part, it will move only when it is not equal (greater than or less than), and will not be processed when it is equal
Suitable for the scene: a small number of elements, and basically orderly
Code implementation:
i: number of ordered sequences or left index of unordered sequences
j: It is used to traverse the array and compare the elements to be arranged with the elements of the ordered sequence

package main

import "fmt"

func main() {
	arr := []int{1, 7, 6, 7, 98, 9, -1, 7, 89, 14, -4, -5, -657}
	insertSort(arr)
	for _, v := range arr {
		fmt.Println(v)
	}
}

func insertSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		for j := i - 1; j >= 0; j-- {
			if arr[j+1] < arr[j] {
				swap(arr, j+1, j)
			}
		}
	}
}

func swap(arr []int, i, j int) {
	tem := arr[i]
	arr[i] = arr[j]
	arr[j] = tem
}

Binary Insertion Sort
Algorithm idea:
1. The array is divided into two parts: ordered part and unordered part
2. Divide the initial data into ordered parts and unordered parts. In each step, insert the data of an unordered part into the ordered part that has been arranged previously
3. The comparison method is binary search
4. Wait until all elements are sorted
Average time complexity: O(n2)
Data comparison times: (n - 1) + (n - 2) + (n - 3) +... + 1 = 1/2n2 - 1/2n
Number of data exchanges: (n - 1)
Total complexity: 1/2n2 + 1/2n - 1
Optimal time complexity: O(n2)
Worst time complexity: O(n)
Space complexity: O(1)
Stability: stable
When an element moves from an unordered part to an ordered part, it will move only when it is not equal (greater than or less than), and will not be processed when it is equal
Suitable for the scene: a small number of elements, and basically orderly
Code implementation:
i: number of ordered sequences or left index of unordered sequences
left, right: = left and right boundary index of binary search
tem: temporary variable
j: Used to traverse the array and move the elements in the second half

package main

import "fmt"

func main() {
	arr := []int{1, 7, 6, 7, 98, 9, -1, 7, 89, 14, -4, -5, -657}
	insertSort(arr)
	for _, v := range arr {
		fmt.Println(v)
	}
}

func insertSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		// Binary search
		left, right := 0, i-1
		tem := arr[i]
		for left <= right {
			mid := left + (right-left)/2
			if arr[mid] > tem {
				right = mid - 1
			} else {
				left = mid + 1
			}
		}
		// Move arr [left... I - 1] one grid to the right
		for j := i; j > left; j-- {
			arr[j] = arr[j-1]
		}
		arr[left] = tem
	}
}

Two way insertion sort