数据结构之折半插入排序

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

作者简介：大家好我是小唐同学(๑>؂<๑），为梦想而奋斗的小唐，让我们一起加油！！！

个人主页：小唐同学(๑>؂<๑）的博客主页

系列专栏：数据结构

博友们如果也是新手入门数据结构我希望大家可以多加练习 数据结构题库在牛客网就有已经给大家附上链接，可以直接点击跳转：刷题点这里

牛客网支持ACM模式哦，刷算法题也很推荐哦！！！

下面上文章------》

刷题推荐：

折半插入排序概念：

折半插入排序是直接插入排序与折半查找的结合，由于在插入排序过程中，已经生成一个（排好的元素组成的）有序数列。所以在插入代排元素时可以使用折半查找的方式来确定新元素的位置，当元素个数较多时，折半插入排序是优于 直接插入排序的。

算法步骤：

输入：

n个数的序列（数组--乱序）

输出：

输出一个排列好的新序列（默认升序）

算法思想：

折半插入排序时对一个序列分为有序区和无序区，有序区初始状态为0，直到无序区为0结束

折半插入排序思想其实与直接插入排序极其相似，只是查找的方式不同，

直接插入排序：从后向前依次比较寻找位置

折半插入排序：利用已排好数列进行折半查找进行确定位置

算法图示：

     ![](https://img-blog.csdnimg.cn/e6592c876b054fb1b4d3193a2ae97e1a.png)

算法比较过程：

1. 输入数据序列被分为有序区和无序区俩部分

2.最初有序区是没有元素的，从无序区不断取出元素（有序）放入

3.已知前i个元素已经有序排列，则第i+1个元素（无序区第一个---后文称为目标元素）

4.先与有序区的最后一个元素比较

    （1）如果目标值较大则说明此时位置正确，直接归入有序区，进行下一位判断

    （2）如果目标值较小则说明目标值在前列，需要进行二分查找判断位置

            ①搜索区间变为原来的一半，折半查找若有问题请看上文：数据结构与算法之折半查找

            ②确定位置后，将有序区间从后往前逐个后串，最后将临时变量temp中的值覆盖插入的位置

算法实现：

# include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[7];
    for(int i=0;i<7;i++)
    {
        cin>>a[i];
    }

    for(int i=1;i<7;i++)//i为无序区的首号元素 
    {    int temp=a[i];
        if(a[i]<a[i-1])//当 a[i]>a[i-1]时自动i++ 
        {
        
                    int left=0;
                    int right=i-1;     
                    while(left<=right)
                    {
                        int mid=(left+right)/2;
                        if(a[mid]<=temp)
                        {
                            left=mid+1;
                        }
                        else
                        right=mid-1;
                    }
          for(int j=i-1;j>=right;j--)
        {
            a[j+1]=a[j];
        }
        a[right+1]=temp;
        }         
    }
        for(int i=0;i<7;i++)
    {
        cout<<a[i]<<" ";
    }
}

时间复杂度：

最好的情况：O（n）--遍历一遍

最坏的情况：O（n*n）--每一个都要调换位置

综上则平均时间复杂度为O（n*n）;

空间复杂度：

中间用到中间变量，但是为常数，则空间复杂度为：O（1）