活动地址：CSDN21天学习挑战赛

✅作者简介：C/C++领域新星创作者，为C++和java奋斗中
✨个人社区：微凉秋意社区
🔥系列专栏：经典算法
📃推荐一款模拟面试、刷题神器👉注册免费刷题

🔥前言

书接上文，今天带来算法基础中的折半插入排序，一个综合了直接插入排序和二分查找的算法。和以往四篇不同，这篇文章将会加入详细调试的图片，帮助大家理解该算法的流程。本篇文章也将收录在经典算法专栏，此专栏免费且收录经典算法，感兴趣的朋友可订阅以便持续观看。

文章目录

折半插入排序算法解析
- 一、理解算法思想
- 二、算法流程
- 三、代码实现
- - 1、源代码
  - 2、运行效果
- 四、调试程序，分析算法流程
- - 1、详细的调试过程
  - 2、时间复杂度

折半插入排序算法解析

一、理解算法思想

每次从原有数据中取出一个数，插入到之前已经排好的序列中，直到所有的数全部取完，该算法过程与直接插入排序算法极为相似，区别就是在插入的时候高效的选择位置。
- 使用二分（折半）查找来选择插入位置

二、算法流程

外层循环用来找到序列中无序的入口
进入无序入口后，记录入口位置元素值并进入二分查找
二分查找结束后，将元素值向依次后覆盖
最后将入口位置的元素值插入到二分查找结束的位置即可

三、代码实现

1、源代码

int main(void)
{
	int arr[6] = { 27,45,50,35,66,32 };
	int len = sizeof(arr) / sizeof(arr[0]);
	cout << "排序前：" << endl;
	for (int i = 0; i < len; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	for (int i = 1; i < len ; i++)
	{
		if (arr[i] < arr[i - 1])
		{
			int temp = arr[i]; 
			int low = 0;
			int high = i - 1;  
			while (low <= high) {
				int middle = (low + high) / 2;
				if (temp < arr[middle])
				{
					high = middle - 1;
				}
				else
				{
					low = middle + 1;
				}
			}
			for (int j = i - 1; j >= high + 1; j--)
			{
				arr[j + 1] = arr[j];
			}
			arr[high + 1] = temp;
		}
	}
	cout << "排序后：" << endl;
	for (int i = 0; i < len; i++) {
		cout << arr[i] << " ";
	}
}

解析：

由于不会出现重复元素，所以最后一定会将搜索区间缩小至low与high重合(左右区间端点不断移动)。在最后一次循环时，low、high的值相同，在比较完成后，左右端点发生交错，相差为1，此时要选择一个变量的值作为新插入元素的位置参照。
需要明确的是，在左右端点重合之前，待插入元素必定是能够落在low与high的区间内的，这就决定了tmp一定大于low对应的元素，小于high对应的元素。