CSDN21天学习挑战赛之折半插入排序

​

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

“九层之台，起于垒土”。学习技术须脚踏实地。

折半插入排序的概念

​插入排序是一种较基础的排序算法，原理也简单易懂，只要会玩扑克就应该能很快学会。

直接插入排序通过构建有序序列，依次扫描无序序列的每个元素，将其与有序序列比较，插入小于自身的元素后面，其余元素依次后移。

折半插入排序是直接插入排序的一个改进版本。由于直接插入排序具有有序序列，所以查找要插入位的置过程可以利用折半查找，减少了元素比较的次数，但元素移动次数并没有改变。

算法描述

1. 假设已有 i-1 个元素排好，取出第 i 个元素 temp。
2. 通过二分查找该元素应插入的位置 location，即右侧元素小于它，左侧元素大于它。
3. 将 location（包括） 后到 i（不包括）的元素依次后移一位。
4. 把temp放入location。
5. 回到第一步直至 i 等于 n。

C++实现

template<typename T>
void BinaryInsertSort(T* a, int size){
    
    int mid;
    for(int i = 1; i < n;i++){
    
        int lo = 0, hi = i - 1;
        while(lo <= hi){
    
            mid = lo + (hi - lo)/2;
            if(a[i] < a[mid])
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        int temp=arr[i];
         //由折半查找到的正确插入位置为high+1
        //将high+1后面的元素依次后移
        for(int j=i-1;j>=high+1;j--)
            arr[j+1]=arr[j];
        arr[high+1]=temp;
    }
}

最后一次循环有三种情况：

• lo == hi，a[hi] >= a[mid] 时， hi = mid-1，hi+1 就是 temp 需要插入的位置。
• lo == hi，a[hi] < a[mid] 时， lo = mid+1，hi+1 还是 temp 需要插入的位置。
• hi = lo + 1，a[mid] = a[lo] > a[i]时，hi = mid-1，hi+1 还是 temp 需要插入的位置。

综上 hi+1 就是 temp 需要插入的位置。

复杂度分析

1. 时间复杂度

   折半插入只是在查找位置是更加快速了，元素移动次数还是不变的，所以总得来说与直接插入排序处于同一量级，还是$O(n^2)$。但它的性能是要优于直接插入排序的。

2. 空间复杂度

   只需要维护几个索引与一个中间值，所以为$O(1)$。