数据结构——折半插入排序

一、算法介绍

1.算法思想

折半插入排序的思想是借用了折半查找的思路，通过在已经有序的序列（默认序列第一个元素为有序序列）中利用二分查找快速定位插入位置，这样经过n-1趟插入就能完成排序，当元素较多时，折半插入排序效率更优于直接插入排序。

2.算法流程

默认序列第一个元素是已经有序序列，每次从无序序列中拿取一个元素，通过折半查找快速找到在有序序列中的插入位置，然后插入元素，经过n-1趟插入完成排序。默认排升序。

示例：

待排序序列：4，2，8，9，5，6，1，3，7

二、算法实现

1.代码实现

#include<iostream>
using namespace std;
void BinarySearch(int* arr, int size) {//折半插入排序
  for (int i = 1; i < size; i++) {//默认第一个元素为有序序列，所以从1开始循环
  if (arr[i] < arr[i - 1]) {//如果当前元素大于等于有序序列所有元素，不需要进行查找插入
    int  key = arr[i];//标记待插入元素
    int left = 0;
    int right = i - 1;
    while (left <= right) {
    int mid = (left + right) / 2;
    if (arr[mid] > key) {
      right = mid - 1;
    }
    else {
      left = mid + 1;
    }
    }
    for (int j = i - 1; j > right; j--) {//顺序后移
    arr[j + 1] = arr[j];
    }
    arr[right + 1] = key;//插入元素
  }
  }
}
void PrintArr(int* arr, int size) {//数组打印
  cout << endl;
  for (int i = 0; i < size; i++) {
  cout << arr[i] << ' ';
  }
}
void Test() {
  int arr[] = { 4,2,8,9,5,6,1,3,7 };
  //int arr[] = { 15,1,1,45,12,125,15,45,20,-3 };
  int size = sizeof(arr) / sizeof(arr[0]);
  cout << "排序前：";
  PrintArr(arr, size);
  BinarySearch(arr, size);
  cout << endl << "排序后：";
  PrintArr(arr, size);
}
int main() {
  Test();
  return 0;
}

2.测试用例及结果

测试用例1：4，2，8，9，5，6，1，3，7

测试结果：

测试用例2：15，1，1，45，12，125，15，45，20，-3

测试结果：

三、性能分析

1.时间复杂度

最坏情况 ：

根据算法思想可知，最坏情况即元素刚好与排序要求相反的情况，每次都需要进行位置折半查找，虽然利用折半查找提高了查找性能，但是移动元素的次数是固定的，所以最坏情况下的时间复杂度为 。

最好情况 ：

最好情况自然就是元素本身已经有序的情况下，那么每个元素只需要在开始时的一次比较就确认已经处于对应位置，不再需要进行折半查找插入，因此最好情况下的时间复杂度为 。

平均情况   ：

综合两种情况，折半插入排序的时间复杂度为 。

2.空间复杂度

由于算法实现中只使用了几个临时变量作为标记，没有借助额外的辅助空间，所以空间复杂度为O(1)。