void SelectSort(SqList &L){
// 对记录序列R[1.. L.length]作简单选择排序
for(i = 1; i <= L.length; i++){
// 选择第 i 小的记录,并交换到位
k = i;
for(j = i + 1; j <= L.length; ++j)
if(L.r[j].key < L.r[k].key) k = j;
if(k != i) Swap(L.r[i], L.r[k]); // 交换
}
}
改进:简单选择排序没有利用上次选择的结果,是造成速度满的重要原因。如果,能够加以改进,将会提高排序的速度。
void HeapAdjust(HeapType &H, int s, int m){
// 已知 H.r [s..m]中记录的关键字除 H.r [s] 之外均
// 满足堆的特征,本函数自上而下调整 H.r [s] 的
// 关键字,使 H.r [s..m] 也成为一个大顶堆。
rc = H.r[s]; // 暂存 H.r [s]
for(j = 2 * s; j <= m; j *= 2){
// j 初值指向左孩子
// 自上而下的筛选过程;
if(j < m && H.r[j].key < H.r[j + 1].key) ++j;
// 左/右“子树根”之间先进行相互比较
// 令 j 指示关键字较大记录的位置
if ( rc.key >= H.r[j].key ) break;
// 再作“根”和“子树根”之间的比较,
// 若“>=”成立,则说明已找到 rc 的插
// 入位置 s ,不需要继续往下调整
H.r[s] = H.r[j]; s = j;
// 否则记录上移,尚需继续往下调整
}
H.r[s] = rc; // 将调整前的堆顶记录插入到 s 位置
}
void HeapSort ( HeapType &H ) {
// 对顺序表 H 进行堆排序
for(i = H.length / 2; i > 0; --i)
HeapAdjust(H, i, H.length); // 建大顶堆
for(i = H.length; i > 1; --i){
Swap(H.r[1], H.r[i])
// 将堆顶记录和当前未经排序子序列
// H.r[1..i]中最后一个记录相互交换
HeapAdjust(H, 1, i-1); // 将H.r[1...i-1]重新调整为大顶堆
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。