二分排序法

运行结果：

思想：

1， 逐渐扩大排好序区间，用待排元素插入到排好序的序列中
2，查找待插入位置时用二分查找法

#include<iostream>

// 折半插入排序
void binarySort(int a[], int n) {
	int i, j, low, mid, high;
	for (i = 2; i < n; ++i) {
		a[0] = a[i];	// 待排元素，a[0]用来存储每次待排的元素，不参与整体排序
		low = 1; high = i - 1;	// 已排好序的区间
		while (low <= high) {		// 查找插入位
			mid = (low + high) / 2;
			if (a[mid] > a[0])
				high = mid - 1;		// 在左边
			else
				low = mid + 1;		// 在右边
		}
		for (j = i - 1; j > high; --j)
			a[j + 1] = a[j];	// 统一后移
		a[high + 1] = a[0];		// 插入元素
	}
}

// 打印函数
void display(int a[], int n) {
	for (int i = 1; i < n; ++i) {
		std::cout << a[i] << ' ';
	}
	std::cout << '\n' << std::endl;
}

int main() {
	int a[]{ 0,1,5,7,6,4 };
	int n = sizeof(a) / sizeof(a[0]);
	std::cout << "二分排序前：\n";
	display(a, n);
	binarySort(a, n);
	std::cout << "二分排序后：\n";
	display(a, n);

	return 0;
}

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性： 稳定