算法描述

与直接插入排序算法相比，折半插入排序算法只是将寻找插入位置这一过程进行了优化，采用折半查找法能更快找到待插入位置。

代码实现

// 折半插入排序，由小到大
#include <iostream>
#include <fstream>
using namespace std;

const int n = 8;

// 函数功能：获取待插入位置下标
// arr:待排表 
// low,high:有序子表上下界 
// key:待插入元素
int binary_search(int arr[], int low, int high, int key){
    if(low > high) return low; 
    int mid = (low + high) / 2;
    if(arr[mid] > key)
        return binary_search(arr, low, mid-1, key);
    if(arr[mid] < key)
        return binary_search(arr, mid+1, high, key);
}

void binary_insert_sort(int arr[], int i){
    int elem = arr[i];
    int j = binary_search(arr, 0, i-1, elem);
    for(int k=i; k>j; --k)
        arr[k] = arr[k-1];
    arr[j] = elem;
}

int main(){
    ifstream inFile;
    inFile.open("in.txt");
    int *arr = new int[n];
    for(int i=0; i<n; ++i)
        inFile >> arr[i];
    for(int i=0; i<n; ++i)
        binary_insert_sort(arr, i);
    for(int i=0; i<n; ++i)
        cout << arr[i] << " ";
    inFile.close();
    delete[] arr;
    return 0;
}

算法分析

（1）折半查找法提高了查找效率，直接插入排序需要查找O(n²)次，折半查找法只需查找O(nlogn)次；但是移动次数仍为O(n²)次，因此算法复杂度仍为O(n²)。

（2）折半插入排序为稳定的排序算法。