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

选择排序，说白了就是「每次挑一个最值出来」。我刚开始学排序时，觉得这思路太直白了——不就是找最小嘛。但后来发现，同样是「选」，简单选择和堆排序的效率差距，能差出几个数量级。今天咱们就把这两种选择排序掰开揉碎，看看它们到底差在哪。

一、简单选择排序

简单选择排序的思路，就像你在一堆扑克牌里找最小的那张。找到后放到最左边，然后从剩下的牌里继续找。嗯，就这么简单。

1. 算法原理

每次从待排序序列中选出最小（或最大）的元素，放到已排序序列的末尾。重复这个过程，直到所有元素排好。

我举个例子：数组 [5, 3, 8, 6, 4]。

  • 第一趟：找最小元素 3，与第一个元素 5 交换 → [3, 5, 8, 6, 4]
  • 第二趟：从 [5, 8, 6, 4] 中找最小 4，与第二个元素 5 交换 → [3, 4, 8, 6, 5]
  • 第三趟：从 [8, 6, 5] 中找最小 5，与第三个元素 8 交换 → [3, 4, 5, 6, 8]
  • 第四趟：从 [6, 8] 中找最小 6，位置不变 → [3, 4, 5, 6, 8]

2. 代码实现

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;
        }
    }
}
我的经验：简单选择排序的交换次数很少，最多 n-1 次。如果你在嵌入式系统里排序，数据量小（比如几十个），而且交换成本很高（比如交换的是大结构体），那简单选择排序其实挺合适的。我在一个传感器数据采集项目里就用过它，因为每次交换都要搬运几十个字节，冒泡排序的交换次数太多了。

3. 性能分析

指标 值
最好时间复杂度 O(n²)
最坏时间复杂度 O(n²)
平均时间复杂度 O(n²)
空间复杂度 O(1)
稳定性 不稳定

你可能会问：为什么最好和最坏都是 O(n²)？因为不管数据原本是什么顺序，它都得老老实实把每个元素都比一遍。说白了，它不关心数据是否已经有序，每次都从头找到尾。

避坑指南：我曾经在一个项目中用简单选择排序排 10 万个整数，结果等了十几秒才出结果。后来换成堆排序，不到 0.1 秒就搞定了。数据量一大，O(n²) 和 O(n log n) 的差距就是天壤之别。

二、堆排序

堆排序，说白了就是「用堆这种数据结构来加速选择」。简单选择排序每次找最小元素都要遍历整个数组，太慢了。堆排序通过维护一个堆，每次取堆顶元素，然后调整堆，把找最小的时间从 O(n) 降到了 O(log n)。

1. 堆的概念

堆是一棵完全二叉树，分为大顶堆和小顶堆：

  • 大顶堆：每个节点的值都大于等于其子节点的值。堆顶是最大值。
  • 小顶堆：每个节点的值都小于等于其子节点的值。堆顶是最小值。

堆排序通常用大顶堆来实现升序排序。为什么？因为每次把堆顶（最大值）放到数组末尾，剩下的元素再调整成大顶堆，重复下去就得到升序序列了。

2. 堆的调整（下沉操作）

堆调整是堆排序的核心操作。它的作用是把一个「除了根节点外，左右子树都已经是堆」的二叉树，调整成一个完整的堆。

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);
    }
}

这个函数做的事情很简单：找到当前节点和它的左右子节点中最大的那个，如果最大的不是当前节点，就交换，然后递归调整被交换下去的那个子树。

3. 建堆

建堆就是从最后一个非叶子节点开始，从下往上依次做堆调整。

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

为什么从 n/2 - 1 开始？因为最后一个非叶子节点的索引就是 n/2 - 1。叶子节点不需要调整，它们本身就是「堆」。

关键点：建堆的时间复杂度是 O(n)，不是 O(n log n)。虽然每个 heapify 是 O(log n)，但大部分节点在树中的高度很低，所以总时间其实是线性的。这个结论我当年面试时被问到过，答上来后面试官明显眼睛一亮。

4. 堆排序的完整实现

void heapSort(int arr[], int n) {
    // 第一步：建堆
    buildHeap(arr, n);

    // 第二步：逐个取出堆顶元素
    for (int i = n - 1; i > 0; i--) {
        // 将堆顶（最大值）与末尾元素交换
        int tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;

        // 调整剩余元素为大顶堆
        heapify(arr, i, 0);
    }
}

整个过程分两步：先建堆，然后反复取堆顶、调整堆。每次取出的最大值都放到数组末尾，最终数组就是升序的。

5. 性能分析

指标 值
最好时间复杂度 O(n log n)
最坏时间复杂度 O(n log n)
平均时间复杂度 O(n log n)
空间复杂度 O(1)
稳定性 不稳定

堆排序最大的优点是：不管数据怎么分布，它都能稳定在 O(n log n)。不像快速排序，最坏情况会退化到 O(n²)。我在一些对实时性要求高的嵌入式系统里，就喜欢用堆排序——它的性能是可预测的。

避坑指南：我曾经在 Cortex-M3 上实现堆排序时，发现递归的 heapify 函数会导致栈溢出。因为堆排序的递归深度是 O(log n)，按理说不会溢出，但那个系统的任务栈只有 256 字节。后来我把递归改成了迭代，问题就解决了。所以嵌入式开发里，能迭代就别用递归。

三、两种选择排序的对比

对比项 简单选择排序 堆排序
时间复杂度 O(n²) O(n log n)
空间复杂度 O(1) O(1)
交换次数 最多 n-1 次 约 n log n 次
适用场景 数据量小（<1000），交换成本高 数据量大，需要稳定性能
实现复杂度 简单 中等

简单选择排序虽然慢，但代码简单，不容易出错。堆排序虽然快，但实现起来要注意边界条件。我个人建议：如果你在写一个快速原型，数据量不大，用简单选择排序就够了。但如果是正式产品，尤其是数据量不确定的情况下，堆排序是更稳妥的选择。

四、知识体系图

选择排序知识体系 选择排序 简单选择排序 堆排序 每次选最小 O(n²) 交换少 建堆 O(n) O(n log n) 性能稳定 核心区别：简单选择每次找最小 O(n) → 堆排序用堆加速到 O(log n)

这张图把选择排序的两种实现方式梳理得很清楚了。左边是简单选择排序，右边是堆排序。它们的核心区别就在于「如何找最小/最大元素」——简单选择是暴力遍历，堆排序是用堆来加速。

我的建议：如果你刚开始学排序，先把简单选择排序写熟，理解「选择」的本质。然后再去啃堆排序，重点理解 heapify 和建堆的过程。我当年学堆排序时，光画堆的调整过程就画了十几张纸。画着画着，突然就通了。

好了，选择排序就讲到这里。记住一句话：选择排序的核心是「每次选一个最值」，而堆排序就是给这个「选」的过程装上了加速器。

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

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