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