插入排序——折半插入排序

1、简述：

折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

实现步骤：

• 定义：已知列表arr，从第二个元素开始，i=1，arr[temp] = arr[i]， arr[low] 表示首元素，arr[high]表示末元素，中间值arr[mid] = arr[ (low+high)/2];
• 比较temp和mid 的元素大小，
  • 当temp < mid，则选择low到mid-1的位置作为新插入区域，即[low, high=mid-1]；
  • 否则，选择mid+1到high的位置作为新插入区域，即[low=mid+1, high]；
  • 循环直到low<=high不成立
• 移动元素：将[low, i)位置的元素向后移动，把temp的元素插到low的位置。

2、复杂度

时间复杂度：O(n2)（比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变）

空间复杂度：O(1)

3、稳定性：稳定排序

4、例子：

C++代码：?

#include <iostream>
using namespace std;

#define LEN 8 // 有LEN个元素要排

void BInsertSort(int arr[], int length)
{
    for(int i = 1; i < length; i++){
              
        int temp = arr[i];
        int low = 0;
        int high = i - 1;
      
        while(low <= high){  // 在arr[low..high]中折半查找有序插入的位置
            int mid = (low + high) / 2;   // 折半
            if(temp < arr[mid]){ // 关键字相同时，使low = m + 1，到高半区，保证稳定性
                high = mid - 1; // 插入点在低半区
            }else{
                low = mid + 1; // 插入点在高半区
            }
        }
      
        for(int j = i; j >= low + 1; j--){
            arr[j] = arr[j - 1];
        }
      
        arr[low] = temp;
        cout<<"i="<<i<<"的排序结果：";
        for (int a = 0;a < length;a++) {
            cout << arr[a] << " ";
        }
        cout<<endl;
    }
}
int main(void)
{
    int arr[LEN] = {45, 98, 66, 90, 88, 78, 25, 45};
    BInsertSort(arr, 8);
    return 0;
}

输出结果：

i=1的排序结果：45 98 66 90 88 78 25 45 
i=2的排序结果：45 66 98 90 88 78 25 45 
i=3的排序结果：45 66 90 98 88 78 25 45 
i=4的排序结果：45 66 88 90 98 78 25 45 
i=5的排序结果：45 66 78 88 90 98 25 45 
i=6的排序结果：25 45 66 78 88 90 98 45 
i=7的排序结果：25 45 45 66 78 88 90 98 

?参考：折半插入排序_百度百科