折半插入排序
折半插入排序(Binary Insertion Sort)是对插入排序算法的一种改进。所谓插入排序，就是不断的依次将元素插入前面已排好序的序列中。
- 中文名称 折半插入排序
- 外文名称 Binary Insertion Sort
- 类型 插入排序
- 时间复杂度 O(n^2)
- 空间复杂度 O(1)
基本概念
折半插入排序(binary insertion sort)是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
具体操作
在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域(即low=m+1)，如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。
稳定性及复杂度
折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。附加空间O(1)。
折半查找只是减少了比较次数，但是元素的移动次数不变，所以时间复杂度为O(n^2)是正确的!
算法示例
C++
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#define LEN 8 // 有LEN个元素要排
struct Record { // 为了考察排序的稳定性，定义元素是结构体类型
int key;
int otherinfo;
};
void BInsertSort(Record *arr, int length) // length是要排序的元素的个数，0号单元除外
{
for (int i = 2; i <= length; ++i) {
arr[0] = arr[i]; // 将arr[i]暂存到arr[0]
int low = 1;
int high = i - 1;
while (low <= high) { // 在arr[low..high]中折半查找有序插入的位置
int m = (low + high) / 2; // 折半
if (arr[0].key < arr[m].key) // 关键字相同时，使low = m + 1，到高半区，保证稳定性
high = m - 1; // 插入点在低半区
else
low = m + 1; // 插入点在高半区
}
for (int j = i - 1; j >= high + 1; --j)
arr[j + 1] = arr[j]; // 记录后移
arr[high + 1] = arr[0]; // 插入
}
}
int main(void)
{
freopen("in.txt", "r", stdin);
Record a[LEN + 1] = {0};
for (int i = 1; i <= LEN; i++)
cin >> a[i].key >> a[i].otherinfo;
BInsertSort(a, LEN);
for (int i = 1; i <= LEN; i++)
cout << a[i].key << 't' << a[i].otherinfo << endl;
return 0;
}
/*
in.txt:
49 1
38 0
65 0
97 0
76 0
13 0
27 0
49 2
out:
13 0
27 0
38 0
49 1
49 2
65 0
76 0
97 0
*/
JAVA
C语言
#include <stdio.h>
typedef int ElemType ;
ElemType arr[]={0,9,8,7,6,5,4,3,2,1};
ElemType n=10,i,j;
ElemType low,high,mid;
void BinSort(ElemType r[],ElemType n)
{
for(i=2;i<=n;i++)
{
r[0]=r[i];
low=1; high=i-1;
while (low<=high)
{
mid=(low+high)/2;
if(r[0]<r[mid])
high=mid-1;
else
low=mid+1;}
for(j=i-1;j>=low;j--)
{
r[i]=r[j];
i--;
}
r[low]=r[0];} }
void put(ElemType r[],ElemType n)
{
for(j=1;j<n;j++)
printf("%dt",r[j]);
printf("n");
}
void main()
{
BinSort(arr,n);
put(arr,n);
}