归并排序与基数排序：二路归并排序（递归与非递归实现）、基数排序（LSD与MSD）

排序算法这块，前面我们聊了不少基于比较的排序。今天要讲的这两个，路子不太一样。归并排序是分治思想的典型代表，基数排序则另辟蹊径，用“分配”代替“比较”。我个人觉得，理解这两种排序，能帮你打开排序的另一扇窗。

一、二路归并排序：分而治之的典范

归并排序的核心思想，说白了就八个字：先拆后合，两两合并。

你想想看，一个无序数组，怎么排？归并排序的做法是：先把数组从中间一分为二，左边排好，右边排好，然后合并两个有序数组。那左边怎么排？继续拆。一直拆到每个子数组只有一个元素——单个元素天然有序。然后再一层层合并回去。

嗯，这里要注意：合并两个有序数组，需要借助一个临时数组。这是归并排序空间复杂度的来源。

1. 递归实现：最直观的写法

递归版本最容易理解，代码也最简洁。我刚开始学归并排序时，就是从这个版本入手的。

// 合并两个有序区间 [left, mid] 和 [mid+1, right]
void merge(int arr[], int left, int mid, int right, int temp[]) {
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    // 把临时数组拷回原数组
    for (i = 0; i < k; i++)
        arr[left + i] = temp[i];
}

// 递归版归并排序
void mergeSortRecursive(int arr[], int left, int right, int temp[]) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSortRecursive(arr, left, mid, temp);
    mergeSortRecursive(arr, mid + 1, right, temp);
    merge(arr, left, mid, right, temp);
}

这段代码的逻辑很清晰：先拆，再合。递归深度是 log₂n，每一层合并的总代价是 O(n)，所以总时间复杂度 O(n log n)。

2. 非递归实现：迭代版归并

递归版本虽然好理解，但函数调用有开销，而且递归深度太深可能栈溢出。非递归版本用迭代代替递归，性能更好。

非递归的思路是：从长度为 1 的子数组开始合并，然后长度翻倍，再合并，直到整个数组有序。

void mergeSortIterative(int arr[], int n) {
    int *temp = (int *)malloc(n * sizeof(int));
    if (!temp) return;

    // size 表示当前子数组的长度，从 1 开始，每次翻倍
    for (int size = 1; size < n; size *= 2) {
        // 每次合并两个长度为 size 的子数组
        for (int left = 0; left < n - size; left += 2 * size) {
            int mid = left + size - 1;
            int right = (left + 2 * size - 1 < n - 1) ? 
                         left + 2 * size - 1 : n - 1;
            merge(arr, left, mid, right, temp);
        }
    }

    free(temp);
}

这段代码里，外层循环控制子数组长度，内层循环遍历数组，两两合并。注意边界处理：最后一个子数组可能长度不足 size，要单独处理。

二、基数排序：用分配代替比较

基数排序的思路很有意思——它不比较元素大小，而是根据元素的“位”来分配。比如排序整数，先按个位分桶，再按十位分桶，最后按百位分桶。分完就排好了。

基数排序有两种实现方式：LSD（Least Significant Digit，从低位开始）和 MSD（Most Significant Digit，从高位开始）。

1. LSD 基数排序：从低位到高位

LSD 是最常用的版本。它从最低位开始，逐位进行“分配-收集”操作。每次分配时，把元素放到对应数字的桶里，然后按桶的顺序收集回来。

// 获取数字的第 digit 位（从 0 开始，0 表示个位）
int getDigit(int num, int digit) {
    for (int i = 0; i < digit; i++)
        num /= 10;
    return num % 10;
}

// LSD 基数排序
void radixSortLSD(int arr[], int n) {
    // 先找到最大值，确定位数
    int maxVal = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > maxVal) maxVal = arr[i];

    int maxDigit = 0;
    while (maxVal > 0) {
        maxVal /= 10;
        maxDigit++;
    }

    int *temp = (int *)malloc(n * sizeof(int));
    int count[10] = {0};

    for (int d = 0; d < maxDigit; d++) {
        // 统计每个桶的元素个数
        memset(count, 0, sizeof(count));
        for (int i = 0; i < n; i++) {
            int digit = getDigit(arr[i], d);
            count[digit]++;
        }

        // 计算每个桶的起始位置（前缀和）
        for (int i = 1; i < 10; i++)
            count[i] += count[i - 1];

        // 从后往前遍历，保证稳定性
        for (int i = n - 1; i >= 0; i--) {
            int digit = getDigit(arr[i], d);
            temp[--count[digit]] = arr[i];
        }

        // 拷贝回原数组
        for (int i = 0; i < n; i++)
            arr[i] = temp[i];
    }

    free(temp);
}

这段代码里，我用了计数排序的思想来实现每个位的排序。注意从后往前遍历——这是为了保证稳定性。基数排序的稳定性很重要，因为后续位的排序不能破坏前面位的顺序。

2. MSD 基数排序：从高位到低位

MSD 从最高位开始分桶。它的特点是：高位分完后，每个桶内的元素在高位上已经有序，然后递归地对每个桶按次高位排序。

MSD 的实现比 LSD 复杂一些，因为需要递归处理每个桶。而且 MSD 通常需要配合插入排序来优化——当桶内元素较少时，直接插入排序比继续递归更高效。

// MSD 基数排序的递归辅助函数
void msdRadixSort(int arr[], int left, int right, int digit) {
    if (left >= right || digit < 0) return;

    int count[10] = {0};
    int *temp = (int *)malloc((right - left + 1) * sizeof(int));

    // 统计当前位各数字的出现次数
    for (int i = left; i <= right; i++) {
        int d = getDigit(arr[i], digit);
        count[d]++;
    }

    // 计算每个桶的起始位置
    int start[10] = {0};
    for (int i = 1; i < 10; i++)
        start[i] = start[i - 1] + count[i - 1];

    // 分配元素到临时数组
    int pos[10];
    memcpy(pos, start, sizeof(pos));
    for (int i = left; i <= right; i++) {
        int d = getDigit(arr[i], digit);
        temp[pos[d]++] = arr[i];
    }

    // 拷贝回原数组
    for (int i = left; i <= right; i++)
        arr[i] = temp[i - left];

    free(temp);

    // 递归处理每个桶
    for (int i = 0; i < 10; i++) {
        int l = left + start[i];
        int r = left + start[i] + count[i] - 1;
        if (count[i] > 1)
            msdRadixSort(arr, l, r, digit - 1);
    }
}

void radixSortMSD(int arr[], int n) {
    // 找最大值确定位数
    int maxVal = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > maxVal) maxVal = arr[i];

    int maxDigit = 0;
    while (maxVal > 0) {
        maxVal /= 10;
        maxDigit++;
    }

    msdRadixSort(arr, 0, n - 1, maxDigit - 1);
}

MSD 的好处是：如果高位分布不均匀，某些桶可能很小，可以提前结束递归。但它的递归开销比 LSD 大，而且需要额外的空间来记录每个桶的边界。

三、两种排序的对比与选择

我个人在实际项目中的选择经验是：如果数据是整数且范围不大（比如 0~10⁶），基数排序往往更快。但如果数据是浮点数或自定义结构体，归并排序更通用。

四、知识体系总览

下面这张图总结了本章的核心知识点和它们之间的关系：

这张图把两种排序的核心分支和特点都列出来了。你可以看到，归并排序的两个实现方式本质相同，只是写法不同；基数排序的 LSD 和 MSD 则代表了两种不同的处理顺序。