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

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

🔥前言

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

折半插入排序算法解析

一、理解算法思想

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

二、算法流程

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

三、代码实现

1、源代码

折半插入排序数据结构练习

application/x-rar 0星 超过10%的资源 752.0B

下载

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] << " ";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

解析：

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

• 而且最终的插入位置应该放在最后比较元素的后一个位置，也就是mid对应位置的后面，所以是mid+1。如果用low表示，就刚好是low，如果用high表示，则是high+ 1。

2、运行效果

四、调试程序，分析算法流程

1、详细的调试过程

1. 使用VS编译器，在程序更改序列的的位置设置断点
   
2. 启动调试，可以看到程序已经运行到断点处且无错误
   
3. 根据上一个调试结果可以看到第一个程序入口位置是 i = 3，二分查找结束的条件是 low >high，那么继续逐语句调试，观察数组中元素值的变化
   
4. 上一张图片arr[3]变为了50，随之j--，再次调试的话arr[2]的值也会发生改变
   
5. 可以看到arr[2]的值变为45，那么下一次调试将跳出for循环，arr[1]的将变为入口位置的元素值
   
6. 那么该入口的折半插入排序就完成了，接下来运行到外层for循环，继续寻找无序入口并重复上面的操作
   
7. 上次调试的情况是当i=5时，进入折半排序入口，流程和前五步一致，所以直接看最终调试结果
   
   

2、时间复杂度

对于折半插入排序来说，元素的串位次数没有并发生变化，只是在查找位置是更加快速了，因此该算法与直接插入排序处于同一量级。不过在数据量很大时，要优于直接插入排序，时间复杂度仍为O($n^2$)

本文到此结束，如有问题务必交流指正，期待你的关注与支持~
​