折半插入排序CC++代码实现

折半插入排序就是查找操作使用折半查找的直接插入排序，除此之外它与直接插入排序基本一样。

算法属性：

时间复杂度为O(n^2) 空间复杂度为O(1) 稳定排序。 因为要进行折半查找， 所以只能用于顺序结构。 适合初始记录无序，n较大时的情况。

代码如下：

#include<stdio.h> #define MAXSIZE 20 typedef int KeyType; typedef int InfoType; //记录类型 typedef struct { KeyType key; InfoType otherinfo; }RedType; //顺序表类型 typedef struct { RedType r[MAXSIZE + 1]; //r[0]闲置或作哨兵 int length; //顺序表长度 }SqList; //折半插入排序 void BInsertSort(SqList &L) { int i, j, m, low, high; for (i = 2; i <= L.length; ++i) { L.r[0] = L.r[i]; low = 1; high = i - 1; while (low <= high) { m = (low + high) / 2; if (L.r[0].key < L.r[m].key) { high = m - 1; } else { low = m + 1; } } //while结束时high+1即要插入的位置 for (j = i - 1; j >= high + 1; j--) { L.r[j + 1] = L.r[j]; //往后移 } L.r[high + 1] = L.r[0]; //插入记录 } } //打印排序结果 void println(SqList L) { for (int i = 1; i <= L.length; i++) { printf("%d, ", L.r[i].key); } printf("\n"); } int main() { SqList L; L.r[1].key = 5; L.r[2].key = 8; L.r[3].key = 1; L.r[4].key = 4; L.r[5].key = 3; L.length = 5; BInsertSort(L); println(L); }

运行结果：