选择排序 | EXP Notes

基本概念

每一趟在 n-i+1(i=1,2,…,n-1) 个元素中选择最小的作为有序序列的第 i 个元素，进行这样操作的的排序称为选择排序。

简单选择排序（Simple Selection Sort）

基本思想

对于待排序列 L[1…n]，第 i 趟排序即是从 L[i…n] 中选择最小的元素与 L[i] 交换，每一趟排序可以确定一个元素的最终位置，经过 n-1 趟排序就可以完成整个序列的排序。

容易发现，简单选择排序会产生有序子序列，且是全局有序。

代码实现

void SelectSort(int L[], int n)
{
    int i, j, min;
    for (i = 1; i < n; ++i) // n-1趟
    {
        min = i; // 记录这一轮比较最小值位置
        for (j = i+1; j <= n; ++j)
            if (L[j] < L[min]) // 找最小值
                min = j;
        // 一趟排序
        if (min != i) swap(&L[i], L[min]);
    }
}

归纳分析

不稳定排序（unstable sort）

在第 i 趟找到最小元素后，和第 i 个元素交换，交换会导致第 i 个元素和后面与其相同的元素的相对位置改变，因此简单选择排序是不稳定排序。

空间复杂度（in-place 原地算法，O(1)）

交换元素需要 1 个辅助空间，简单选择排序的空间复杂度为 O(1)。

时间复杂度

元素比较的次数与初始状态无关，元素两两之间比较一次，始终是 n(n-1)/2 次。

元素移动的次数与初始状态有关，但是不会超过 3(n-1) 次。

最好情况下，原序列已经有序，移动操作的次数为 0；

最坏情况下，原序列刚好逆序，移动操作的次数为 3(n-1)；；

无论何时，简单选择排序的时间复杂度为 O(n²)。

初态影响

比较次数与初始状态无关，始终是 O(n)；

移动次数与初始状态有关，最坏是 O(n)。

过程特征

一趟排序可以确定一个元素的最终位置（最值），会产生全局有序的有序子序列。

适用性

算法证明（来自算法导论）

循环不变式：A[1…i-1] 包含了 A 中最小的i-1个元素，且已排序。

初始：i=1，A[1…0]=空，因此成立。

保持：在某次迭代开始之前，保持循环不变式，即 A[1…i-1] 包含了A中最小的 i-1 个元素，且已排序，则进入循环体后，程序从 A[i…n] 中找出最小值放在 A[i]处，因此 A[1…i] 包含了A中最小的i个元素，且已排序，而i++，因此下一次循环之前，保持循环不变式：A[1…i-1]包含了A中最小的i-1个元素，且已排序。

终止：i=n，已知A[1…n-1]包含了A中最小的i-1个元素，且已排序，因此A[n]中的元素是最大的，因此A[1…n]已排序，证毕。

问题

冒泡排序和插入排序哪个更快？

插入排序中移动的次数直接是逆序对的个数，而冒泡排序中交换的次数是逆序对的个数，由前面的分析可知，一次交换需要移动3次元素，因此冒泡排序执行的时间至少是逆序对的个数，因此插入排序的执行时间至少比冒泡排序快。

算法改进

简单选择排序，每趟循环只能确定一个元素排序后的定位，可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置，从而减少排序所需的循环次数。改进后对 n 个数据进行排序，最多只需进行[n/2]趟循环。

void SelectSort_1(int L[], int n)
{
    int i, j, min, max; // 记录最小值的下标

    for (i = 1; i <= n/2; ++i) // 每次选出两个，故需要n/2趟
    {
        min = max = i;
        // 第 i 趟排序开始时，已分别确定了 i-1 个最大值和最小值
        // 剩余范围 [i...n-i+1]
        for (j = i+1; j <= n-i+1; ++j)
        {
            if (L[j] < L[min])
                min = j;
            else if (L[j] > L[max])
                max = j;
        }

        // 存在的问题：如果先移动 min ，那么当 max 刚好位于 i 时，
        // 会将 max 移动到原来 min 的位置，所以要判断 max 与 i 的关系
        // 同理，如果先移动 max ，那么当 max 刚好位于 n-i+1 时，
        // 会将 min 移动到原来 max 的位置，所以要判断 min 与 i 的关系

        if (min != i) swap(&L[min], &L[i]); // 当前最小值归位 L[i]

        // 先交换完 min 后，判断 max 与 i 的关系，来决定是否要更新 max 的位置
        if (max == i) max = min;

        if (max != n-i+1) swap(&L[max], &L[n-i+1]); // 当前最大值归位 L[n-i+1]
    }
}

堆排序（Heap Sort）

产生来源

对于选择排序优化的重点在于减少比较的次数，显然要在 n 个元素中选择最值，至少需要进行 n-1 次比较，但是在剩余 n-1 个元素中选择最值并不一定需要 n-2 次，因为可以依据大小比较的传递性，结合前面 n-1 次比较的结果减少后续比较的次数，于是就有了树形选择排序（Tree Selection Sort），又称为锦标赛排序（Tournament Sort）。

首先，对 n 个元素进行两两比较，然后在 ⌈n/2⌉ 个较小者中在进行两两比较，如此重复知道选择出最小值，这个过程很像锦标赛决出冠亚季军，故此得名锦标赛排序，而这个过程画出来就是一棵完全二叉树（胜者树），因此又名树形选择排序。

排序过程用一颗完全二叉树表示，待排序元素位于叶子节点，每个非终端节点均为其左右孩子节点中的较小者，而最终的根节点就是当前的最小值元素；

而为了决出次小者，可以将上一步确定的最小值元素在其原来的叶子节点位置标注位 Infinity，然后这个叶子节点开始重复之前的动作，自底向上两两比较，进而确定次小者；

依次类推，得到排序结果。

一棵含有 n 个节点的完全二叉树深度为 ⌊log₂n⌋+1，因此，除了确定最小值之外，决出每个次小者时仅需要进行 ⌊log₂n⌋ 次比较操作，故时间复杂度为 O(nlog₂n)。

不过，这种树形选择排序需要很多辅助空间，并且每次都会和 Infinity 重复比较，浪费时间。

于是，在 1964 年，Williams 结合连续存储表示的完全二叉树的父子节点之间的关系，提出了堆排序（Heap Sort）。

基本思想

堆的定义如下：具有 n 个元素的序列 L[1…n]，当且仅当满足

（1）L[i] ≤ L[2i] 且 L[i] ≤ L[2i+1]

或者

（2）L[i] ≥ L[2i] 且 L[i] ≥ L[2i+1]

其中，i = {1,…⌊n/2⌋}

满足（1）称为小根堆（小顶堆），非叶子节点的值不大于其孩子节点，根节点（堆顶）为最小元素；
满足（2）称为大根堆（大顶堆），非叶子节点的值不小于其孩子节点，根节点（堆顶）为最大元素。

以大根堆为例：

初始时把待排序列 L[] 看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储顺序，使之成为一个大根堆，输出堆顶元素，得到 n 个元素中最大的元素。然后对前面 n-1 个元素重新调整使之成为新堆，输出堆顶元素，得到 n 个元素中次大的元素。依此类推，最后得到有 n 个节点的有序序列，这个过程称为堆排序。

因此，实现堆排序需解决两个问题：

如何将无序的待排序列建成堆；
输出堆顶元素后，怎样调整剩余的 n-1 个元素，使其成为一个新堆。

首先讨论第 2 个问题：输出堆顶元素后，对剩余 n-1 个元素重新建成堆。

调整小顶堆的方法：

1）设 n 个元素的堆，输出堆顶元素后，用堆中最后一个元素替代堆顶元素（最后一个元素与堆顶进行交换），堆被破坏，仅因为根结点不满足堆的性质，于是只需要自上而下进行调整；
2）将堆顶元素与左、右子树中较小元素的进行交换；
3）若与左子树交换后，左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法（2）；
4）若与右子树交换后，右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法（2）；
5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被重建。

上述自顶向下的调整过程称为“筛选”。

讨论完第 2 个问题就可以回过头来谈论第 1 个问题，从无序序列建堆。

很容易得到，从一个无序序列建堆的过程就是一个反复筛选的过程，将无序序列看成一课完全二叉树，那么从最后一个非终端节点 ⌊n/2⌋ 开始依次各个分终端节点为根的子树（⌊n/2⌋ ~ 1）进行筛选，一直进行到根节点即可完成初始建堆。

代码实现

// 自顶向下调整 [s...n]
void HeapAdjustDown(int L[], int s, int n)
{
    int i; // 复用 s 作为双亲指针，而 i 作为孩子指针
    L[0] = L[s]; // L[0] 暂存当前堆顶
    for (i = 2*s; i <= n; i *= 2)
    {
        // i <= n, i+1 <= n 保证不越界
        if (i < n && L[i] < L[i+1]) ++i;
        if (L[i] <= L[0]) break;
        // else
        // {
            L[s] = L[i]; s = i;  // 孩子大，孩子上移，双亲指针下移
        // }
    }
    L[s] = L[0];
}

堆排序：

void HeapSort(int L[], int n)
{
    // 从下往上筛选，初始建堆
    int i;
    for (i = n/2; i >= 1; --i)
        HeapAdjustDown(L, i, n);

    // 筛选调整
    for (i = n; i > 1; --1) // n-1 趟即可
    {
        swap(&L[1], &L[i]); // 选出的最大值交换至最后，剩余 i-1 个元素重新建堆
        HeapAdjustDown(L, 1, i-1);
    }
}

归纳分析

不稳定排序（unstable sort）

进行筛选时，有可能把后面相同元素调整到前面，所以堆排序是一种不稳定排序。

空间复杂度（in-place 算法，O(1)）

需要一个辅助空间用于交换当前决出的最大元素（堆顶），因此空间复杂度为 O(1)。

时间复杂度

堆排序运行时间主要耗在初始建堆和调整建堆时进行的反复筛选上。

向下调整的时间与树深（高）有关，对深度为 h 的堆，筛选算法进行的比较次数至多 2(h-1) 次，而移动次数至多 h 次，因此时间复杂度为 O(h)。

于是，

初始建含有 n 个元素、深度为 h 的堆时，因为第 i 层节点至多为 2^i-1，以它为根的二叉树深度为 h-i+1，那么调用 ⌊n/2⌋ 次筛选函数总共进行的比较次数不超过

Σ2^i-1·2(h-i) = Σ2ⁱ·(h-i) = Σ2^h-j·j ≤ (2n)Σj/2^j ≤ 4n, 其中 i = {h-1, h-2, … 1}

因此在元素个数为 n 的序列上初始建堆，其时间复杂度为 O(n)，说明可以在线性时间内完成从无序序列初始建堆。

又 n 个节点的完全二叉树的深度为 ⌊log₂⌋+1，所以调整建新堆调用筛选函数 n-1 次，总共比较次数不超过

2(⌊log₂n-1⌋+⌊log₂n-2⌋+…+⌊log₂2⌋) < 2n(⌊log_n⌋)

最好、最坏和平均情况下，堆排序时间均为 O(nlog₂n)，这是堆排序相对于快速排序的最大优点。

初态影响

由3得，在最好、最坏和平均情况下，堆排序时间均为 O(nlog₂)，
最好情况下，初始基本有序，不会改变比较次数，移动次数会有相应减少，因此，初始状态堆堆排序效率影响不大。

过程特征

一趟排序可以确定一个元素的最终位置（最值），会产生全局有序的有序子序列。

适用性

堆排序的时间复杂度和快速排序一个量级，不过辅助空间比快排少，并且不会出现快排那种最坏情况。

堆排序利用了顺序存储完全二叉树双亲结点与孩子节点之间的位置关系，所以堆排序适用于顺序存储的序列。

对于数据量较少的序列，不提倡使用堆排序，对于数据量较大的序列比较有效。

堆能用于构建优先级队列，优先队列常应用于操作系统中作业调度、任务调度、进程间调度等。

堆数据结构也应用于 Dijkstra、Prim 算法。

堆的扩展

堆支持插入和删除；

堆进行删除操作时，删除的堆顶最值元素先与堆尾元素交换，然后从根节点自顶向下调整；

堆进行插入操作时，插入的元素节点先放在堆尾，然后从新节点自底向上调整。

自底向上调整的算法实现如下：

void HeapAdjustUp(int L[], int n)
{
    int i;
    L[0] = L[n]; // 暂存
    for (i = n; i >= 1; i /= 2)
    {
        if (i/2 >= 1 && L[i/2] < L[0])
            L[i] = L[i/2];
        else break;
    }
    L[i] = L[0];
}

注意：不能用于堆排序中输出堆顶后调整新堆，因为向上调整的前提是，除最后一个元素外，前面的元素符合堆的要求，显然在堆顶破坏后，前面的元素就不符合堆的定义了。

上篇: 归并排序下篇: 交换排序（一）

基本概念
简单选择排序（Simple Selection Sort）
堆排序（Heap Sort）