折半插入排序

in 数据结构 with 1 comment

折半插入排序(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取整

这里只对两个极端情况进行说明

以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

算法分析

时间复杂度:
  1. 平均情况:

只是比较顺序改变,移动次数不变

平均比较次数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) $$

  1. 最坏情况:一开始元素就是有序从大到小的,时间复杂度为O(n^2^)
  2. 最好情况:一开始元素就是有序从小到大的,时间复杂度为O(n)
空间复杂度:

只使用了i,j,tmp,low,high,mid六个辅助变量,与问题规模n无关。空间复杂度为O(1)

稳定性:

插入时判断条件为R[mid]<tmp,故相同元素的相对位置不变。这是一种稳定的排序方法。

复杂性:

简单

归位:

否,不是全局有序。

Responses
  1. study 一起学习 go

    Reply