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

前言：
✌ 作者简介：游坦之 ✌
🏆 大学软件工程在读，希望学到真本领，经世致用 🏆
📫 如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步👀
💬 人生格言：丑且益坚，病当益壮💬
🔥 如果感觉博主的文章还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦

🍳折半插入排序

🔍什么是折半查找

​ 折半插入排序是对插入排序算法的一种改进。所谓插入排序，就是不断的依次将元素插入前面已排好序的序列中。说白了，就是将一个集合，分为有序区和无序区，前区是有序区，后区是还没有处理的集合数据，前区的范围从0到n，后区的范围从n到0，其中n是集合中元素的数量。

🎍举个栗子

​ 对元素{5,3,2,1,4}进行从小到大的排序。此时index为0，代表有序区元素的数量，同时代表指向当前要排序的元素。

​ 第一次，因为有序区元素为0，所以把元素直接放在有序区的第一个，此时index更新为1。（红色方块代表排序完了）

​ 第二次，此时指向第二个元素也就是3，因为此时有序区元素不为空，所有在有序区内进行二分查找一次进行比较。(0+1/2 = 0 )，所以与第0个元素5比较，3<5，5元素往后移动一个，3放到5原来的位置，index更新为2。

​ 第三次，重复上述过程，2放在了3的原位置，index更新为3。

​ 第四次，重复上述过程，1又放在了2的原位置。index更新为4。

​ 第五次，重复上述过程，index更新为5。排序完毕。

🎷思考

​ 折半插入排序的时间复杂度，由于该算法需要遍历所有的元素，也就是n。对于每一个元素来说，又需要一次二分查找，时间复杂度也就是logm，综上，折半插入排序的时间复杂度即为O(nlogn)。

​ 折半插入排序的退出条件，当index==n的时候，即对所有的元素排序完毕之后，退出排序。

🎈实战演练

对{5,1,3,2,4}进行折半插入排序的算法实现

#include 
using namespace std;
const int M = 1010;
int n; 
int temp;
int index = 0;
int a[M]; 
int main()
{
	cin>>n;
	for(int i=0;i>a[i];
	}
	for(int i=0;ia[i])
				{
					r = mid-1;
				}else if(a[mid]=mid;j--)
				{
					a[j+1] = a[j];
				}
				a[mid] = temp;
			}else{
				temp = a[i];
				for(int j=i-1;j>=mid+1;j--)
				{
					a[j+1] = a[j];
				}
				a[mid+1] = temp;
			} 
			index++;
		}
			cout<<"排序"<