选择排序¶

选择排序 | Hello 算法

堆 | Hello 算法

堆排序 | Hello 算法

选择排序每一趟从待排序区间里挑一个最值, 放到最终位置. 408 里这一类主要是简单选择排序和堆排序: 前者线性扫一遍找最小, 后者用堆把「找最值」降到 \(O(\log n)\).

和冒泡一样, 每趟至少有一个元素就位; 差别是冒泡靠相邻交换挤过去, 选择是直接把最值换到目标槽.

简单选择排序¶

简单选择排序（Straight Selection Sort）第 \(i\) 趟在 \(a[i..n-1]\) 里找出最小元, 与 \(a[i]\) 交换. 做完 \(n-1\) 趟, 前缀 \(a[0..n-2]\) 已是最终次序, 最后一个元素不必再选.

以 \(\{5, 2, 4, 1, 3\}\) 为例, 竖线左侧是已就位的前缀:

 | 5  2  4  1  3
1 | 2  4  5  3      选 1 与 5 交换
1  2 | 4  5  3      选 2, 已在槽上
1  2  3 | 5  4      选 3 与 4 交换
1  2  3  4 | 5      选 4 与 5 交换

算法实现¶

void select_sort(int a[], int n) {
    int i, j, min, tmp;
    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++)
            if (a[j] < a[min])
                min = j;
        if (min != i) {
            tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
    }
}

算法分析¶

• 比较次数固定 \(\sum_{i=1}^{n-1} i = n(n-1)/2\), 与初始序列无关, 最好 / 平均 / 最坏都是 \(O(n^2)\) (非自适应)

• 交换至多 \(n-1\) 次, 移动次数比冒泡、插入少

• 空间复杂度 \(O(1)\), 原地算法

• 不稳定. 例如对 \(\{5_a, 5_b, 2\}\) 应用选择排序, 第一趟把 \(2\) 与 \(5_a\) 对调, 变成 \(\{2, 5_b, 5_a\}\).

• 顺序表、链表都能做; 链表上找最小仍要扫一遍, 交换改指针即可

堆排序¶

堆排序（Heap Sort）还是「每趟选最值」, 但把待排序区间看成一棵完全二叉树, 并维持堆序, 于是取最值只要看根, 修复堆只要沿一条根到叶的路走.

堆¶

堆是一棵完全二叉树, 满足:

• 大根堆: 任意结点 \(\geqslant\) 其左右孩子 (根是最大)

• 小根堆: 任意结点 \(\leqslant\) 其左右孩子

升序排序建大根堆: 根永远是当前堆里的最大值.

完全二叉树用数组顺序存最合适¹. 408中习惯以 \(1\) 为起始下标:

\(0\) 下标则是父 \(\lfloor (i-1)/2 \rfloor\), 左 \(2i+1\), 右 \(2i+2\), 最后分支 \(\lfloor n/2 \rfloor - 1\). 下面的实现代码用 \(0\) 下标.

向下调整¶

某结点的左右子树已经是堆, 只有它自己可能违规: 把它与较大的孩子对调, 再对这个孩子继续, 直到堆序恢复或走到叶子. 这条路最长 \(O(\log n)\).

void sift_down(int a[], int i, int n) {
    int tmp = a[i];
    int child = 2 * i + 1;           /* 左孩子 */
    while (child < n) {
        if (child + 1 < n && a[child + 1] > a[child])
            child++;                 /* 取较大的孩子 */
        if (tmp >= a[child])
            break;
        a[i] = a[child];
        i = child;
        child = 2 * i + 1;
    }
    a[i] = tmp;
}

建堆与排序¶

1. 建堆: 从最后一个分支结点往根走, 对每个结点 sift_down. 子树先堆化, 父亲再调整, 整棵树变成大根堆

2. 排序: 把根与当前堆底对调 (最大值进入有序后缀), 堆长减 \(1\), 对新根 sift_down. 重复 \(n-1\) 次

以 \(\{5, 2, 8, 3, 1, 6, 4\}\) 为例. 层序对应的树:

      5                    8
   2     8      建堆    3     6
  3 1   6 4           2 1   5 4

竖线右侧是已就位的后缀:

初始                 5  2  8  3  1  6  4
建堆                 8  3  6  2  1  5  4 |
换顶 + 调整          6  3  5  2  1  4 | 8
                     5  3  4  2  1 | 6  8
                     4  3  1  2 | 5  6  8
                     3  2  1 | 4  5  6  8
                     2  1 | 3  4  5  6  8
                     1 | 2  3  4  5  6  8

void heap_sort(int a[], int n) {
    int i, tmp;
    for (i = n / 2 - 1; i >= 0; i--) /* 建堆 */
        sift_down(a, i, n);
    for (i = n - 1; i > 0; i--) {
        tmp = a[0];
        a[0] = a[i];
        a[i] = tmp;
        sift_down(a, 0, i);          /* 堆长变为 i */
    }
}

算法分析¶

• 建堆 \(O(n)\), 不是 \(O(n\log n)\): 高度 \(h\) 处约 \(\frac{n}{2^{h+1}}\) 个结点, 各花 \(O(h)\), 求和是常数倍的 \(n\)

• 之后 \(n-1\) 次调整, 每次 \(O(\log n)\), 排序阶段 \(O(n\log n)\)

• 合计最好 / 平均 / 最坏都是 \(O(n\log n)\), 非自适应. 和归并一样摸到了比较排序的 \(\Omega(n\log n)\) 下界, 且最坏不会退化成 \(O(n^2)\) (这点强于快排)

• 空间 \(O(1)\), 原地 (调整在原数组上进行)

• 不稳定: 根与堆底对换可能让相等元跨越很远

• 依赖下标跳到父子, 只适用于顺序表

堆也是优先队列的常用实现: 入堆 / 出堆 \(O(\log n)\), 看堆顶 \(O(1)\). Top-K 一类问题先建堆再取 \(K\) 次堆顶即可. 只找一次第 \(k\) 小、不必维护动态集合时, 平均更快的是快速选择.

两种选择排序对照¶