void InsertSort(SqList &L){
int i, j;
for(i = 2; i <= L.length; ++i){
if(L.r[i].key < L.r[i - 1].key){
// 将L.r[i]插入有序子表
L.r[0] = L.r[i]; // 复制为哨兵
L.r[i] = L.r[i - 1];
for(j = i - 2; L.r[0].key < L.r[j].key; --j)
L.r[j + 1] = L.r[j]; // 记录后移
L.r[i + 1] = L.r[0]; // 插入到正确位置
}
}
}
平均时间复杂度:O(n^2)
特点:简单、容易实现,适用于待排序记录基本有序或待排序记录较小时。
基本思想:因为 R1..i-1 是一个按关键字有序的有序序列,则可以利用折半查找实现“在R1..i-1中查找Ri的插入位置”,如此实现的插入排序为折半插入排序。
void BiInsertionSort(SqList &L){
for(i = 2; i <= L.length; ++i){
L.r[0] = L.r[i]; // 将L.r[i] 暂存到 r[0]
// 在 L.r[1..i-1]中折半查找插入位置
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; // 插入点在高半区
}
for(j = i - 1; j >= high + 1; --j)
L.r[j + 1] = L.r[j];
L.r[high + 1] = L.r[0];
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。