选择排序
简单选择排序
基本思想
- 每一趟在后面 n-i +1个中选出关键码最小的对象, 作为有序序列的第 i 个记录
算法实现
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]); // 交换
}
}算法分析
时间复杂度：O(n^2)
移动次数：
- 最好情况：0
- 最坏情况：3(n-1)
- 空间复杂度: O(1)
- 稳定性: 稳定
树形选择排序
基本思想
- 取得 n 个对象的关键码，进行两两比较，得到 n/2 个比较的优胜者(关键码小者)，作为第一步比较的结果保留下来。
- 这 n/2 个对象再进行关键码的两两比较，…，如此重复，直到选出一个关键码最小的对象为止。
算法分析
- 含有n个叶子节点的完全二叉树的深度为log2 n+1，则选择排序的每一趟都需作log2n次比较，排序的时间复杂度O(nlog2n)。
- 需要辅助存储空间较多（n-1），和最大值作多余的比较等等。
改进：简单选择排序没有利用上次选择的结果，是造成速度满的重要原因。如果，能够加以改进，将会提高排序的速度。
堆排序
- 堆：把待排序的数据元素存放在数组中r[1…n]，把r看成是一棵完全二叉树，每个结点表示一个记录。r[i]结点的左孩子是r[2i]，右孩子是r[2i+1]。
- 若r[i].key<=r[2i].key，并且 r[i].key<=r[2i+1].key，则称此完全二叉树为堆。（小根堆）
- 若r[i].key>=r[2i].key，并且 r[i].key>=r[2i+1].key，则称此完全二叉树为堆。（大根堆）
基本思想
- 将无序序列建成一个堆
- 输出堆顶的最小（大）值
- 使剩余的n-1个元素又调整成一个堆，则可得到n个元素的次小值
- 重复执行，得到一个有序序列
无序序列建成堆
如何在输出堆顶元素后调整，使之成为新堆？
- 输出堆顶元素后，以堆中最后一个元素替代之
- 将根结点与左、右子树根结点比较，并与小者交换
- 重复直至叶子结点，得到新的堆
算法实现
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]重新调整为大顶堆
}
}
算法分析
- 时间效率：O(nlog2n)
- 空间效率：O（1）
- 稳定性：不稳定
适用于n 较大的情况
