[数据结构与算法]插入排序算法：折半插入排序

插入排序算法：折半插入排序

1.简介

插入排序算法思想：将待排序元素分为已排序子集和待排序子集，依次从待排序子集选择一个元素插入到已排序子集中，使已排序子集仍然有序。重复以上过程直到所有元素都有序为止。

排序规则：

1. 假总共有n个需要排序，那么待排序有n-1，第1个元素默认有序
2. 以索引1切分，前面为有序子集，后面为无序子集
3. 将无序子集中取出1个元素a，按折半查找(二分查找)从有序子集中找到第一个大于a的位置b，从位置b开始的所有有序子集元素向右偏移1位，在a放入到位置b。如果有序子集中没有数据大于a，将a放到有序子集末尾
4. 重复步骤3直到无序子集为空

2.图示

注意：图示没有二分查找索引位置的过程

3.演示

3.1.文件树型图

binary-insertion-sort
├── binary-insertion-sort.go
└── binary-insertion-sort_test.go

3.2.代码

binary-insertion-sort.go

package binary_insertion_sort

func BinaryInsertSort(arr []int) {
	length := len(arr)
	var low, high, mid int

	for i := 1; i < length; i++ {
		t := arr[i]
		// binary search
		for low, high = 0, i-1; high >= low; {
			mid = (low + high) / 2
			if t < arr[mid] {
				high = mid - 1
			} else {
				low = mid + 1
			}
		}

		// backward offset 1
		for j := i - 1; j >= low; j-- {
			arr[j+1] = arr[j]
		}
		// insert data
		arr[low] = t
	}
}

binary-insertion-sort_test.go

package binary_insertion_sort

import "testing"

func TestBinaryInsertSort(t *testing.T) {
	arr := []int{3, 1, 9, 20, 4}
	BinaryInsertSort(arr)
	t.Log(arr)
}

3.3.测试

=== RUN   TestInsertSort
    straight-insertion-sort_test.go:8: [12 20 24 34 53]
--- PASS: TestInsertSort (0.00s)
PASS

4.参考

• 《C/C++函数与算法速查手册》