8.3 选择排序：简单选择与堆排序

简单选择排序，堆的定义、建堆与筛选（下坠）过程，堆排序的性能，以及堆的插入与删除。

选择排序的基本思想是：每一趟（如第 $i$ 趟）在后面 $n - i + 1$（$i = 1, 2, \ldots, n - 1$）个待排序元素中选取关键字最小的元素，作为有序子序列的第 $i$ 个元素，直到第 $n - 1$ 趟做完，待排序元素只剩下 1 个，就不用再选了。

简单选择排序

假设排序表为 L[1..n]，第 $i$ 趟排序即从 L[i..n] 中选择关键字最小的元素与 L(i) 交换，每一趟排序可以确定一个元素的最终位置，这样经过 $n - 1$ 趟排序就可使得整个排序表有序。

1void SelectSort(int A[], int n) {
2    for (int i = 0; i < n - 1; i++) {    // 共 n-1 趟
3        int min = i;                     // 记录最小元素的位置
4        for (int j = i + 1; j < n; j++)  // 在 A[i..n-1] 中选最小
5            if (A[j] < A[min])
6                min = j;                 // 更新最小元素位置
7        if (min != i)
8            swap(A[i], A[min]);          // 与第 i 个位置交换
9    }
10}

性能分析：

• 空间效率：仅使用常数个辅助单元，故空间效率为 $O(1)$。
• 时间效率：从上述伪码中不难看出，在简单选择排序过程中，元素移动的操作次数很少，不会超过 $3(n - 1)$ 次，最好的情况是移动 0 次，此时对应的表已经有序；但元素间比较的次数与序列的初始状态无关，始终是 $n(n-1)/2$ 次，因此时间复杂度始终是 $O(n^2)$。
• 稳定性：在第 $i$ 趟找到最小元素后，和第 $i$ 个元素交换，可能会导致第 $i$ 个元素与其含有相同关键字元素的相对位置发生改变。例如，表 $L = \{2, \underline{2}, 1\}$，经过一趟排序后 $L = \{1, \underline{2}, 2\}$，最终排序序列也是 $L = \{1, \underline{2}, 2\}$，显然，2 与 $\underline{2}$ 的相对次序已发生变化。因此，简单选择排序是一种不稳定的排序算法。

堆排序

堆排序的思路很简单：首先将存放在 L[1..n] 中的 $n$ 个元素建成初始堆，由于堆本身的特点（以大顶堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。

可见，堆排序需要解决两个问题：① 如何将无序序列构造成初始堆？② 输出堆顶元素后，如何将剩余元素调整成新的堆？

建堆

$n$ 个结点的完全二叉树，最后一个结点是第 $\lfloor n/2 \rfloor$ 个结点的孩子。对第 $\lfloor n/2 \rfloor$ 个结点为根的子树筛选（对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换），使该子树成为堆。之后向前依次对各结点（$\lfloor n/2 \rfloor - 1 \sim 1$）为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止（“小元素不断下坠”）。反复利用上述调整堆的方法建堆，直到根结点。

1void HeadAdjust(int A[], int k, int len) {
2    A[0] = A[k];                         // A[0] 暂存子树的根结点
3    for (int i = 2*k; i <= len; i *= 2) {  // 沿较大的子结点向下筛选
4        if (i < len && A[i] < A[i+1])
5            i++;                         // 取较大的子结点的下标
6        if (A[0] >= A[i]) break;         // 筛选结束
7        else {
8            A[k] = A[i];                 // 将 A[i] 调整到双亲结点上
9            k = i;                       // 继续向下筛选
10        }
11    }
12    A[k] = A[0];                         // 被筛选结点放入最终位置
13}
14void BuildMaxHeap(int A[], int len) {
15    for (int i = len/2; i > 0; i--)      // 从最后一个分支结点开始
16        HeadAdjust(A, i, len);
17}
18void HeapSort(int A[], int len) {
19    BuildMaxHeap(A, len);
20    for (int i = len; i > 1; i--) {      // n-1 趟交换和建堆
21        swap(A[i], A[1]);                // 堆顶元素与堆底元素交换
22        HeadAdjust(A, 1, i - 1);         // 把剩余 i-1 个元素整理成堆
23    }
24}

堆的插入与删除

• 插入：对于大（小）根堆，新元素放到表尾，与父结点对比，若新元素比父结点更大（小），则将二者互换。新元素就这样一路”上升”，直到无法继续上升为止。每上升一层只需对比 1 次。
• 删除：被删除的元素用堆底元素替代，然后让该元素不断”下坠”，直到无法下坠为止。

即时练习