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

@TOC

🍳折半插入排序

🔍什么是折半查找

​ 折半插入排序是对插入排序算法的一种改进。所谓插入排序，就是不断的依次将元素插入前面已排好序的序列中。说白了，就是将一个集合，分为有序区和无序区，前区是有序区，后区是还没有处理的集合数据，前区的范围从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 <iostream>
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<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n;i++)
    {
        if(index==0)
        {
            index++;
        }else{
            int l = 0;
            int r = index;
            int mid;
            while(l<=r&&mid<=i)
            {
                 mid = (l+r)/2;
                if(a[mid]>a[i])
                {
                    r = mid-1;
                }else if(a[mid]<a[i])
                {
                    l = mid+1;
                }else{
                    break;
                }
            }
            if(a[i]<a[mid])
            {
                
                temp = a[i];
                for(int j=i-1;j>=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<<"排序"<<index<<"次的情况是:"<<endl; 
        for(int i=0;i<n;i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}

✨$\textcolor{blue}{原创不易}$ <br/>
👍 $\textcolor{green}{点赞，不会损失一匹布}$ <br/>
⭐️ $\textcolor{green}{收藏，不会丢掉一厘金}$ <br/>
✏️ $\textcolor{green}{留下痕迹，却会温暖作者的心！}$ <br/>