数据结构——折半插入排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构——折半插入排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、算法介绍

1.算法思想

2.算法流程

二、算法实现

1.代码实现

2.测试用例及结果

三、性能分析

1.时间复杂度

2.空间复杂度

一、算法介绍

1.算法思想

折半插入排序的思想是借用了折半查找的思路，通过在已经有序的序列（默认序列第一个元素为有序序列）中利用二分查找快速定位插入位置，这样经过n-1趟插入就能完成排序，当元素较多时，折半插入排序效率更优于直接插入排序。

2.算法流程

默认序列第一个元素是已经有序序列，每次从无序序列中拿取一个元素，通过折半查找快速找到在有序序列中的插入位置，然后插入元素，经过n-1趟插入完成排序。默认排升序。

示例：

待排序序列：4，2，8，9，5，6，1，3，7

折半插入排序,数据结构,排序算法,c++,算法

二、算法实现

1.代码实现

#include<iostream>
using namespace std;

void BinarySearch(int* arr, int size) {//折半插入排序
	for (int i = 1; i < size; i++) {//默认第一个元素为有序序列，所以从1开始循环
		if (arr[i] < arr[i - 1]) {//如果当前元素大于等于有序序列所有元素，不需要进行查找插入
			int  key = arr[i];//标记待插入元素
			int left = 0;
			int right = i - 1;
			while (left <= right) {
				int mid = (left + right) / 2;
				if (arr[mid] > key) {
					right = mid - 1;
				}
				else {
					left = mid + 1;
				}
			}
			for (int j = i - 1; j > right; j--) {//顺序后移
				arr[j + 1] = arr[j];
			}
			arr[right + 1] = key;//插入元素
		}
	}
}

void PrintArr(int* arr, int size) {//数组打印
	cout << endl;
	for (int i = 0; i < size; i++) {
		cout << arr[i] << ' ';
	}
}

void Test() {
	int arr[] = { 4,2,8,9,5,6,1,3,7 };
	//int arr[] = { 15,1,1,45,12,125,15,45,20,-3 };
	int size = sizeof(arr) / sizeof(arr[0]);

	cout << "排序前：";
	PrintArr(arr, size);
	BinarySearch(arr, size);
	cout << endl << "排序后：";
	PrintArr(arr, size);
}

int main() {
	Test();
	return 0;
}