折半插入排序稳定吗_语言：数据结构-折半插入排序

(1)折半插入排序的基本思想

折半插入排序(Binary Insertion Sort)是直接插入排序的改进。在直接插入排序中，在寻找插入位置时，对已排好序的子序列从后向前通过顺序比较查找插入位置，当n很小时是较实用的方法。当n较大时，数据间的比较次数较多，效率不高。折半插入排序法在寻找插入位置的方法上进行了改进。其基本思想是对已排好序的有序子表，利用折半查找法寻找插入位置，以减少每一趟插入过程中数据间的比较次数。

(2)折半插入排序的步骤

设待排序的序列已存放在数组元素a[1]- a[n]中，以a[0]作为辅助工作单元。以下要把a[i]插入到已经有序的序列a[1]- a[i-1]之中，一趟折半插入排序的步骤如下：

1.设定折半查找的区间

 a[0]= a[i]； /*保存a[i]*/ s=1；j= i-1； /*设定折半查找的区间的起、止下标*/

2.利用折半查找法求插入位置

当s<=j do

 { m←∟(s+j)/2」； /*求区间中点坐标*/ 如果a[0]

3.将所找到的插入位置的元素及其后面的元素逐次后移一个位置

4.将a[0]插入

(3)折半插入排序的算法实现

/*对存放在a[1],a[2],…,a[n]中的序列进行折半插入排序*/void binsort(NODE a[],int n){ int x,i,j,s,k,m; for(i=2;i<=n;i++) { a[0]=a[i]; /*保存待插入的第i号记录*/ x=a[i].key; /*待插入记录的关键字*/ s=1; /*区间的起始下标*/ j=i-1 ; /*区间的终点下标*/ while(s<=j) /*当始点下标大于终点下标时结束循环*/ { m=(s+j)/2; if(x=j+1;k--) a[k+1]=a[k]; /*记录逐次后移,为插入记录留出空间*/ a[j+1]=a[0]; /*把第i个记录插入*/ }}

例如：一组记录序列的关键字为1，3，5，7，8，4。前面5个有序，现要把第6个关键字插入，插入过程如下：

一趟折半插入过程

折半插入排序改进了直接插入排序算法中查找插入位置的方法，减少了关键字间的比较次数，但记录的移动次数并没有得到改善。在数据量较大时，所用时间能有所减少，但时间复杂度为O(n2)。按上述方法，折半插入排序算法是稳定的。