Lecture 32：选择排序

选择类排序每趟选出一个极值放入已排序区。简单选择排序每趟线性扫描未排序区；堆排序用大根堆快速得到当前最大值，将每趟代价降到 $O(\log n)$。

32.1 简单选择排序

32.1.1 过程与性质

定义：#简单选择排序

描述：第 $i$ 趟从未排序区 A[i..n-1] 中选出最小关键字，与 A[i] 交换，使有序区长度增加一个。

void SelectSort(int A[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int min = i;
        for (int j = i + 1; j < n; ++j)
            if (A[j] < A[min]) min = j;
        if (min != i) {
            int t = A[i]; A[i] = A[min]; A[min] = t;
        }
    }
}

无论初始序列是否有序，均需在未排序区寻找最小值，比较次数固定为：

$$ (n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}=O(n^2) $$

额外空间为 $O(1)$，交换次数最多为 $n-1$，记录移动次数通常少于冒泡排序。
简单选择排序不稳定：若最小元素与首元素交换，可能跨过中间相等关键字记录。
既可用于顺序表，也可在链表中通过记录最小结点后调整链接实现；但查找最小值仍是线性扫描。

32.2 堆与堆排序

32.2.1 堆的定义与顺序存储

定义：#大根堆 #小根堆

描述：堆是用顺序表存储的完全二叉树。大根堆中每个父结点关键字不小于孩子，小根堆中每个父结点关键字不大于孩子。

对于下标从 $1$ 开始的顺序表，结点 $i$ 的关系为：

$$ \text{left}(i)=2i,\quad \text{right}(i)=2i+1,\quad \text{parent}(i)=\left\lfloor\frac{i}{2}\right\rfloor $$

大根堆满足：

$$ A[i]\ge A[2i]\quad(2i\le n),\qquad A[i]\ge A[2i+1]\quad(2i+1\le n) $$

右孩子只在 $2i+1\le n$ 时存在；当结点总数为偶数时，最后一个非叶结点可能只有左孩子，不能无条件访问 A[2i+1]。
堆只保证父子关系，不保证同层、同子树所有元素完全有序；不能把堆当作二叉排序树。
大根堆的堆顶为全表最大值，小根堆的堆顶为全表最小值。

顺序表下标与完全二叉树位置一一对应。图中大根堆只要求每条父子边满足“父不小于子”，例如左右子树之间不要求整体大小关系。

32.2.2 建堆与下坠调整

定义：#向下调整 #筛选

描述：若以结点 $k$ 为根的左右子树已是大根堆，而 $A[k]$ 可能较小，则将它沿关键字较大的孩子方向不断下移，直到重新满足堆序。

以下代码把堆元素放在 A[1..len]，另预留 A[0] 暂存下坠元素，因此实际数组至少需要 len+1 个单元；传入的 len 是堆元素数，不含暂存位。

void HeapAdjust(int A[], int k, int len) {
    A[0] = A[k];
    for (int i = 2 * k; i <= len; i *= 2) {
        if (i < len && A[i] < A[i + 1]) ++i;
        if (A[0] >= A[i]) break;
        A[k] = A[i];
        k = i;
    }
    A[k] = A[0];
}

void BuildMaxHeap(int A[], int len) {
    for (int i = len / 2; i > 0; --i)
        HeapAdjust(A, i, len);
}

从最后一个非叶结点 $\lfloor n/2\rfloor$ 倒序调整，能确保调整某结点前其孩子子树已是堆。
逐个插入建堆可达 $O(n\log n)$；上述自底向上建堆总时间为 $O(n)$，是重要结论。

建堆不是“$n/2$ 个结点各做 $O(\log n)$”的简单乘法。靠近叶子的结点数量多但最多下坠很少层，靠近根的结点数量少；按结点可下坠高度 $h$ 汇总：

$$ \begin{aligned} \sum_{h\ge0}O!\left(\frac{n}{2^{h+1}}\right)\cdot O(h) &=O(n)\sum_{h\ge0}\frac{h}{2^{h+1}}\ &=O(n) \end{aligned} $$

32.2.3 堆排序、插入与删除

堆排序：

建立大根堆。
将堆顶最大值与当前无序区末尾交换；末尾成为最终有序区。
缩小堆长度，对新堆顶向下调整。
重复至堆长为 $1$，得到递增序列。

void HeapSort(int A[], int len) {
    BuildMaxHeap(A, len);
    for (int i = len; i > 1; --i) {
        int t = A[1]; A[1] = A[i]; A[i] = t;
        HeapAdjust(A, 1, i - 1);
    }
}

建堆为 $O(n)$，后续 $n-1$ 次调整各为 $O(\log n)$，总时间为 $O(n\log n)$。
辅助空间为 $O(1)$，但堆排序不稳定，堆顶与末尾的交换可能改变相等记录相对次序。

堆插入：

把新元素放到完全二叉树的表尾，结构仍然完全。
大根堆中，若新元素大于父结点便交换并继续向上；小根堆中，若新元素小于父结点便交换并继续向上。
到达根或与父结点满足堆序时停止，最多上升树高，时间为 $O(\log n)$。

原稿小根堆示例把 $13$ 追加到表尾后，先与父结点 $32$ 交换；此时 $13<17$，还必须继续与 $17$ 交换，最终得到 $09,13,65,17,45,78,87,53,32$。图中第二幅只是一次上升后的中间状态，不是最终堆。

删除堆中元素：

用当前堆底元素覆盖待删位置，再把堆长减 $1$，保持完全二叉树形状。
若替换元素破坏了与父结点的堆序，就向上调整；否则若破坏了与孩子的堆序，就向下调整。
删除堆顶是上述过程的特例：根没有父结点，只需用堆底替换后向下调整。单次删除为 $O(\log n)$。

WARNING · 原稿删除图的前提错误图上把原结构标成“小根堆”，但 $46$ 的孩子是 $17,45$，已经违反 $46\le17,45$，所以它不能作为一棵合法小根堆的标准删除起点。若只把红色 $46$ 视为待删位置，用堆底 $32$ 覆盖并与较小孩子 $17$ 交换，确实可得到合法结果 $09,17,65,32,45,78,87,53$；做题时仍应先检查输入是否真满足堆序，不能照图盲目下坠。

32.3 本节复盘

简单选择排序每趟选最小值，比较次数固定 $O(n^2)$，原地但不稳定。
堆是完全二叉树的顺序存储，不是全局有序结构；大根堆顶仅保证全局最大。
自底向上建堆为 $O(n)$，堆排序总时间为 $O(n\log n)$、空间 $O(1)$、不稳定。