折半插入排序（Binary Insertion Sort）是对直接插入排序算法的一种改进，与直接插入排序相比，折半插入的变化在于比较的次序上。折半插入每次比较时都选择中间的元素进行比较，故又称为二分插入排序
排序思路
将待排序的数组R[0..n-1]分为两个部分[0..i-1]和[i..n-1]。其中[0..i-1]为有序区间，[i..n-1]为无序区间。
对于第i趟排序（这里规定第一趟排序从R[1]开始,毕竟一个单独字符R[0]不需要排序嘛！），[0..i-1]已经为有序区间。将元素R[i]分别于之前的每一个中间元素进行比较，在有序区找到合适的位置后，将R[i]插入该位置。
直接插入排序每次与之前的一个元素比较，而折半插入排序与插入区间的中间元素进行比较。期间不断调整区间端点low和high，直至low大于high。
为什么需要low大于high时跳出循环？
为便于说明，不妨设区间为[a..b],其中 low=a,high=b,mid=(a+b)/2取整
这里只对两个极端情况进行说明
a+1=b，即区间内只有两个元素，此时区间mid=low=a,high=b
- 若R[mid]>tmp，则区间右端点移动至原区间中点的前一个，即此时high=mid-1=a-1，显然high<low了，考虑到low左边的数据小于tmp，而tmp小于R[mid],说明tmp应该插入到mid位置，即high+1的位置。
- 若R[mid]<=tmp，则区间 左端点移动至原区间中点的后一个，即此时low=mid+1=a，此时low=high，转至下一种情况。
a=b，即区间内只剩一个元素，此时mid=low=high=a
- 若R[mid]>tmp，则区间变为high=mid-1=a-1，此时high<low，应将tmp插入到mid的位置，即high+1
- 若R[mid]<=tmp，区间变为low=mid+1=a+1，此时high<low，考虑到high右边不小于tmp，所以应将tmp放到mid后面的位置，即high+1（稳定性体现）
以c为例,从小到大排序
排序算法
#include<stdio.h>
void binInsert_sort(int R[],int n){
int tmp,i,j,low,high,mid;
for(i=1;i<n;i++){
if(R[i]<R[i-1]){
tmp=R[i];//记录下R[i]的值，方便插入
low=0;high=i-1;//初始插入区间为[0..i-1]
while(low<=high){
mid=(low+high)/2;
//[low..mid-1],[mid],[mid+1..high]
if(R[mid]>tmp)
high=mid-1;//调整区间为[low..mid-1]
else
low=mid+1;//调整区间为[mid+1..high]
}
//将i前的元素逐个后移，直到前面的元素不大于tmp
for(j=i-1;j>=high+1;j--){
R[j+1]=R[j];
}
R[j+1]=tmp;
}
//打印第i趟排序后的结果
printf("%d: ",i);
int k;
for (k = 0; k < n;k++){
printf("%d ", R[k]);
}
printf("\n");
}
}
int main(void){
int a[] = {9,8,7,6,5,4,3,2,1,0};
binInsert_sort(a, 10);
}动图演示：
这是动图.gif
输出结果：
1: 8 9 7 6 5 4 3 2 1 0
2: 7 8 9 6 5 4 3 2 1 0
3: 6 7 8 9 5 4 3 2 1 0
4: 5 6 7 8 9 4 3 2 1 0
5: 4 5 6 7 8 9 3 2 1 0
6: 3 4 5 6 7 8 9 2 1 0
7: 2 3 4 5 6 7 8 9 1 0
8: 1 2 3 4 5 6 7 8 9 0
9: 0 1 2 3 4 5 6 7 8 9算法分析
时间复杂度：
- 平均情况：
只是比较顺序改变，移动次数不变
平均比较次数log~2~(i+1)-1,平均移动次数i/2+2
$$ \sum_{i=1}^{n-1} (\log_2{(i+1)} -1+\frac{i}{2}+2)=O(n^2) $$
- 最坏情况：一开始元素就是有序从大到小的，时间复杂度为O(n^2^)
- 最好情况：一开始元素就是有序从小到大的，时间复杂度为O(n)
空间复杂度：
只使用了i，j，tmp，low，high，mid六个辅助变量，与问题规模n无关。空间复杂度为O(1)
稳定性：
插入时判断条件为R[mid]<tmp，故相同元素的相对位置不变。这是一种稳定的排序方法。
复杂性：
简单
归位：
否，不是全局有序。
本文由 ukuq 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jan 25, 2019 at 10:44 pm
study 一起学习 go