第24讲：选择排序——简单选择排序与堆排序

选择排序，说白了就是「每次挑一个最值出来」。

我刚开始学排序时，觉得这思路太直白了——不就是找最小嘛。但后来在项目中处理海量数据时才发现，同样是「挑」，怎么挑、挑完怎么处理，差别大了去了。今天咱们就把两种典型的选择排序掰开揉碎讲清楚。

24.1 简单选择排序

简单选择排序的思路，你想想看：

  • 第一趟，从整个数组里找出最小的元素，放到第一个位置
  • 第二趟，从剩下的元素里找出最小的，放到第二个位置
  • 以此类推，直到全部排好

嗯，就是这么朴实无华。我当年第一次手写这个算法时，觉得它太「笨」了——每次都要扫描一遍剩下的元素。但它的优点是稳定、好理解，而且交换次数少。

代码实现

void selectSort(int arr[], int n) {
    int i, j, minIdx, tmp;
    for (i = 0; i < n - 1; i++) {
        minIdx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        if (minIdx != i) {
            tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }
    }
}
小提示：简单选择排序的时间复杂度是 O(n²)，空间复杂度 O(1)。它不稳定——举个例子，数组 [5, 5, 2] 排序后，两个 5 的相对顺序可能会变。

我在项目中用过一次简单选择排序——数据量只有几十个，而且要求交换次数尽量少。当时我查了一下，简单选择排序的交换次数最多是 n-1 次，比冒泡排序少多了。嗯，选它没错。

24.2 堆排序——从「堆」说起

堆排序就高级多了。它利用了一种叫「堆」的数据结构。

什么是堆？说白了，堆就是一棵完全二叉树，而且满足一个条件：

  • 大顶堆：每个节点的值都 ≥ 它的左右孩子
  • 小顶堆：每个节点的值都 ≤ 它的左右孩子

堆排序用的是大顶堆。为什么呢？因为大顶堆的根节点是最大值，我们把它取出来，放到数组末尾，然后调整剩下的元素重新成堆——这样每次都能拿到当前的最大值。

核心思想：建堆 → 取根 → 调整 → 再取根 → 再调整……直到全部取完。

24.2.1 建堆过程

建堆，就是从最后一个非叶子节点开始，从下往上、从右往左，对每个节点执行「下沉」操作。

举个例子，数组 [4, 10, 3, 5, 1] 要建成大顶堆：

  1. 先把它看成完全二叉树：根是 4，左孩子 10，右孩子 3，10 的左孩子 5，右孩子 1
  2. 最后一个非叶子节点是 10（索引 1），它比左孩子 5 大，比右孩子 1 大，不用动
  3. 再看根节点 4（索引 0），它比左孩子 10 小，交换 4 和 10
  4. 交换后，4 到了原来 10 的位置，继续下沉——比左孩子 5 小，再交换
  5. 最终得到大顶堆：[10, 5, 3, 4, 1]

你看，建堆的过程其实就是不断「下沉」的过程。我刚开始学的时候，总觉得这个下沉操作很绕，后来画了几遍图才彻底搞明白。

24.2.2 调整过程

建好堆之后，排序就简单了：

  1. 把根节点（最大值）和最后一个元素交换
  2. 堆的大小减 1（最后一个元素已经排好了）
  3. 对新的根节点执行下沉操作，重新成堆
  4. 重复以上步骤，直到堆为空

我举个例子，刚才的大顶堆 [10, 5, 3, 4, 1]：

  • 交换 10 和 1，得到 [1, 5, 3, 4, 10]，堆大小减为 4
  • 对根节点 1 下沉：和 5 交换，得到 [5, 1, 3, 4, 10]
  • 1 继续下沉：和 4 交换，得到 [5, 4, 3, 1, 10]
  • 现在堆是 [5, 4, 3, 1]，根是 5，交换 5 和 1，得到 [1, 4, 3, 5, 10]
  • 对 1 下沉：和 4 交换，得到 [4, 1, 3, 5, 10]
  • 继续……最终得到 [1, 3, 4, 5, 10]
注意：堆排序是不稳定的排序算法。我曾经在项目中因为没注意这一点，导致一个按时间排序的需求出了 bug——两个相同时间的数据顺序被颠倒了。排查了半天才发现是堆排序的问题。

代码实现

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        int tmp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = tmp;
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    // 建堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 排序
    for (int i = n - 1; i > 0; i--) {
        int tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;
        heapify(arr, i, 0);
    }
}

24.3 两种排序的对比

特性 简单选择排序 堆排序
时间复杂度 O(n²) O(n log n)
空间复杂度 O(1) O(1)
稳定性 不稳定 不稳定
交换次数 最多 n-1 次 较多
适用场景 数据量小、交换代价高 数据量大、需要快速排序

我个人习惯是：数据量小于 100 时，简单选择排序够用了；数据量大了，堆排序是更好的选择。当然，如果你对稳定性有要求，这两种都不合适——那就得考虑归并排序了。

24.4 堆排序的完整流程图

下面这张图展示了堆排序的完整流程，从建堆到排序结束：

堆排序完整流程图 步骤1：建堆 从最后一个非叶子节点开始 步骤2：交换 根节点 ↔ 最后一个元素 步骤3：堆大小减1 已排序区域扩大 步骤4：下沉调整 对新的根节点执行下沉 堆为空？ 否 是 排序完成

24.5 避坑指南

我曾经在实现堆排序时踩过一个坑——建堆时循环的起始索引写错了。我写成了 i = n / 2，结果最后一个非叶子节点没处理到，堆一直建不对。后来查资料才发现，最后一个非叶子节点的索引是 n/2 - 1（数组从 0 开始的情况下）。

还有一个坑：下沉操作一定要用递归或者循环，确保节点一直下沉到合适的位置。我见过有人只下沉一次就停了，结果堆的性质没完全恢复，排序结果自然不对。

我的建议：初学堆排序时，一定要在纸上画几遍完整的过程。建堆、交换、下沉、再交换……每一步都画出来。我当时画了整整三页纸，才彻底搞明白。别嫌麻烦，这比看十遍代码都管用。

好了，选择排序就讲到这里。简单选择排序和堆排序，一个简单但慢，一个复杂但快。你想想看，在实际项目中该怎么选？嗯，答案其实就在上面的对比表里。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →