排序进阶：选择排序、归并排序、基数排序

各位同学，今天我们聊点硬核的。前面我们讲完了插入排序、交换排序这些基础款，说实话，它们在小规模数据下表现还行，但一旦数据量上来，性能就有点捉襟见肘了。今天我们要讲的这三种排序——选择排序的升级版、归并排序、基数排序，才是真正能在生产环境中扛大梁的角色。

我个人习惯把排序算法分成两类：一类是“比较排序”，一类是“非比较排序”。今天这三种里，前两种是比较排序，基数排序则另辟蹊径。咱们一个一个来。

一、简单选择排序——最朴素的“挑最小”

简单选择排序的思路，说白了就是“每次从剩下的元素里挑一个最小的，放到前面去”。你想想看，这就像你在一堆扑克牌里，一张一张找最小的那张，找到就放到手里，然后继续找剩下的里面最小的。

代码实现非常直观：

void selectSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        if (minIdx != i) {
            int tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }
    }
}

嗯，这里要注意：简单选择排序的时间复杂度是 O(n²)，不管数据原本是什么顺序，它都得老老实实比较 n(n-1)/2 次。我在项目中遇到过有人用它来排几万条数据，结果等了半天没反应——这就是没算清楚复杂度。

二、堆排序——用二叉树思想加速选择

简单选择排序慢在哪？慢在每次找最小值都要遍历整个剩余数组。那有没有办法能快速找到最小值？有，用堆。

堆排序的核心思想：先把数组构建成一个大顶堆（或小顶堆），然后每次把堆顶元素（最大值或最小值）和末尾元素交换，再调整堆。这样每次取最值的时间复杂度就从 O(n) 降到了 O(log n)。

看代码：

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

堆排序的时间复杂度是 O(n log n)，而且它是在原地排序，不需要额外空间。这一点在实际嵌入式开发中非常实用——内存就那么点，能省则省。

三、归并排序——分而治之的典范

归并排序的思路很优雅：把数组分成两半，分别排序，然后合并。你想想看，如果两个子数组都已经有序了，合并起来就很简单——像两叠按大小排好的扑克牌，一张一张比大小拿就行了。

代码实现：

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

归并排序的时间复杂度也是 O(n log n)，但它需要 O(n) 的额外空间来存储临时数组。这一点在嵌入式开发中要特别注意——如果你的系统内存只有几十 KB，归并排序可能就不太合适了。

四、基数排序——不比较，直接分桶

前面讲的排序都是通过比较元素大小来排序的。基数排序不一样，它按位来排。比如对三位数排序，先按个位分桶，再按十位分桶，最后按百位分桶。每次分桶后收集起来，最终就是有序的。

看代码：

void radixSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max) max = arr[i];

    for (int exp = 1; max / exp > 0; exp *= 10) {
        int output[n];
        int count[10] = {0};

        for (int i = 0; i < n; i++)
            count[(arr[i] / exp) % 10]++;

        for (int i = 1; i < 10; i++)
            count[i] += count[i - 1];

        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        for (int i = 0; i < n; i++)
            arr[i] = output[i];
    }
}

基数排序的时间复杂度是 O(d * (n + k))，其中 d 是位数，k 是基数（这里是10）。当数据范围不大时，它比 O(n log n) 的排序还要快。

五、四种排序对比

六、知识体系图

下面这张图帮你理清今天讲的内容之间的关系：

好了，今天的内容就到这里。这四种排序各有各的脾气，选哪个得看你的数据规模、内存限制、是否需要稳定排序。我个人建议：嵌入式开发优先考虑堆排序，大数据量且需要稳定用归并排序，整数排序且范围不大可以试试基数排序。至于简单选择排序——嗯，写写作业还行，生产环境慎用。