C语言手写排序算法全解析：原理、稳定性与性能陷阱

排序算法是我在数据结构课程里最先被要求“手写十遍”的内容，也是面试时候最常见的白板题。一开始我以为就是背模板，真正把多种排序算法放在同一个 C 语言工程里实现之后，才发现每一道代码背后都藏着边界条件、稳定性取舍和性能陷阱。这篇文章想把排序算法从原理到 C 语言实现完整拆一遍，顺便把我实际调试和性能对比时踩过的坑说出来。无论你是正在复习数据结构、准备算法面试，还是想在项目里写一个不依赖第三方库的排序模块，下文应该都用得上。

1. 为什么排序算法值得从头写一遍

1.1 排序算法不只是背模板，它串起了数据结构几乎所有基础

排序算法在很多人眼里是个“期末考试前背一下”的模块，真正到了面试或者工程里，才发现它的分量比想象中大。写一个排序过程，本质上是在同时复习数组的下标操作、元素的交换和移动、递归调用栈的压入弹出、树形结构的数组映射、以及复杂度分析。尤其用 C 语言实现时，数组越界、整数溢出、指针传递这些平时业务代码里很少暴露的细节，全都会被排序算法逼出来。

我在带新人的时候很爱让他们先写一个插入排序。这个算法看上去简单，但能把“循环边界”“提前保存当前值”“正确移动元素”三个基本功一次性检验完。很多写了几年业务代码的人，还会在 j = i - 1 这个位置犹豫半天。这就是排序算法的价值：它不是孤立的考点，而是一套用来验证你对数据结构基础到底掌握到什么程度的试金石。

从数据结构的视角看，数组排序是顺序表最典型的高频操作，链表排序可以锻炼指针操作，堆排序依赖完全二叉树的结构，归并排序则是分治思想的极好案例。只要你把常见排序算法逐一手写过，再回头看“数组、链表、递归、树、复杂度”这些章节，会发现之前零散的知识突然就被串起来了。这也是很多面试官喜欢靠排序题目来筛选候选人的原因：一个排序题，足以考察编码能力、边界思维和优化意识。

1.2 先建立全局选型观：时间复杂度、空间、稳定性缺一不可

排序算法不能只背复杂度表格，选型时要把三个维度放在一起看：时间、空间、稳定性。时间复杂度决定规模上限，空间复杂度决定能不能在嵌入式或内存受限环境里用，稳定性决定多字段排序时会不会破坏上一轮的顺序。

常见的场景我列成一张表，方便对照。

稳定性这个概念要单独解释一下：如果排序前有两个相等的元素，排序后它们相对位置保持不变，这类算法就是稳定的。为什么工程里在乎这个？举个例子，你先按班级排了一次，再按成绩排一次，第二趟如果用的是不稳定排序，那么同分学生里原本班级顺序就会被搅乱。正确的做法要么两层排序都用稳定算法，要么干脆把班级和成绩合成一个比较器，一次排序完成。理解稳定性的本质，比记住哪个算法不稳定重要得多。

2. 先把基础排序算法吃透

2.1 冒泡排序：优化点在“提前退出”和“有序区间”

冒泡排序的思路最直观：相邻元素两两比较，每一轮把当前最大值像气泡一样推到最右边。很多人觉得它简单，但实际上手写时最容易犯两个错。第一个是没有做“提前退出”优化，就算数组已经有序，依然傻乎乎地比较完所有轮次。第二个是内层循环边界写成 j < n - 1，没有考虑每一轮结束后末尾元素已经归位，导致无意义的重复比较，甚至把已经有序的区间又翻一遍。

一个更完整的写法是这样：

c复制void bubble_sort(int *a, int n) {
    for (int i = 0; i < n - 1; ++i) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

这里的 swapped 标志是灵魂。如果某一轮完全没有发生交换，说明数组已经整体有序，可以直接跳出外层循环。最坏情况下冒泡排序仍然是 O(n²)，但最佳情况下能做到 O(n)，这在近乎有序的数据集里有实际意义。冒泡排序也是稳定排序，因为只有在后一个元素严格小于前一个时才交换，相等元素不会越过对方。

在实际工程里，冒泡排序几乎没有被大规模使用的机会，但它的教学意义很大：它展示了“相邻元素两两比较”这个最基本的交换排序思想，后面的快排在某种意义上就是对这个思路的大跨度加速。我建议初学者不要跳过它，直接去背快排，很容易连“交换”和“移动”的区别都搞不清楚。

2.2 选择排序：交换次数最少的简单排序

选择排序每一轮在未排序区间里找最小元素，然后把它和未排序区间的第一个元素交换。这个算法和冒泡最大的区别在于：它不追求每轮都交换，而是只做一次最终交换。因此，选择排序虽然比较次数依旧是 O(n²)，但交换次数最多只有 n-1 次。在某些场景下，交换元素代价极高，比如交换的是复杂结构体、或者链表节点的指针，这个特性就很值得利用。

写法不难：

c复制void selection_sort(int *a, int n) {
    for (int i = 0; i < n - 1; ++i) {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            int tmp = a[min_idx];
            a[min_idx] = a[i];
            a[i] = tmp;
        }
    }
}

这里有个容易被人忽略的细节：min_idx != i 才交换。如果最小值本来就在当前位置，交换是多余的。在数组元素全部相等的情况下，加不加这个判断影响不大，但换到结构体数组排序，能避免很多无谓的内存拷贝。

选择排序是不稳定的。比如 [5a, 5b, 1]，第一轮找到最小元素 1，交换后变成了 [1, 5b, 5a]，两个 5 的相对顺序反了。所以如果业务代码里需要保持稳定性，不要选它。很多人记不清这个结论，我有个经验：除了冒泡、插入、归并这三个稳定，其他常见的简单排序基本都不稳定，判断标准就看“相等元素会不会发生跨越式移动”。

2.3 插入排序：近乎有序数据里被严重低估的算法

插入排序是打牌时整理手牌的思路：从数组第二个元素开始，把它不断向左移动，直到找到合适的位置。它最朴素，但被严重低估。在数据量小、或者数组已经基本有序的情况下，插入排序的执行效率甚至可以超过一部分 O(nlogn) 的算法，原因是它的常数极小，而且具有很好的缓存局部性。C++ 标准库的 std::sort 在小区间排序时，就会切回插入排序。

核心实现要注意保存 key，然后通过从后往前移动元素来腾位置：

c复制void insertion_sort(int *a, int n) {
    for (int i = 1; i < n; ++i) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key;
    }
}

我见过不少人把这段代码写成“每步都交换”的版本，逻辑上也没错，但每次都做三次内存读写，效率会变差。正确姿势是先把 key 保存下来，内层循环只做赋值，把比 key 大的元素整体右移，最后把 key 放入空出的位置。这个“先移动后插入”的思想非常重要，它也是归并排序合并过程和快排 partition 的基础。

插入排序的稳定性来自判断条件 a[j] > key：只有严格大于时才移动，等于 key 的元素保持原位置，所以相等元素的相对顺序不会变化。对近乎有序的数据，例如日志按时间记录后只偶尔乱序，插入排序每轮内层循环往往只需移动一两次，整体接近线性。这也是为什么工业级排序都会保留一个插入排序作为“最后一公里”的收尾工具。

3. 进阶排序算法：从 O(n²) 到 O(nlogn)

3.1 希尔排序：插入排序的“跨步”升级

希尔排序是插入排序的推广版本。插入排序每次只移动一步，如果一个小元素在数组末尾，它要一步一步走回开头，耗时太长。希尔排序的做法是先用较大的间隔 h 把数组分成多个子序列，对每个子序列做插入排序，然后不断缩小 h，最后 h=1 时再做一次完整插入排序。通过前期的大跨度跳跃，小元素可以快速移动到大致位置，最后一轮插入排序的负担就大大减轻。

代码上只需要把插入排序里的步长从 1 改成 gap，但整体结构需要重新设计：

c复制void shell_sort(int *a, int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int key = a[i];
            int j = i - gap;
            while (j >= 0 && a[j] > key) {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = key;
        }
    }
}

这里面 gap 的取法很关键。最简单的 gap = n/2 再不断折半，容易在某些数据分布下带来较差的效率。更经典的序列有 Hibbard 增量、Knuth 增量、Sedgewick 增量，它们的共同点是让增量之间保持一定的互质关系，避免子序列之间出现重复比较。希尔排序的时间复杂度分析比较复杂，平均约在 O(n^1.3) 到 O(nlog²n) 之间。它不是稳定排序，因为相同的值可能在不同间隔的子序列里被重新排列。

在实际工程里，现在很少单独使用希尔排序，但它给我们的启发很大：在无法一步到位时，可以先粗调、再精调。这种分阶段逼近的思想，在外排序、Cache 分块优化里会反复出现。面试时如果被问到“插入排序有什么优化方向”，希尔排序能讲清楚，通常比死背复杂度更能体现理解深度。

3.2 归并排序：稳定且可预测的递归排序

归并排序的分治思路很经典：把数组从中间分成两半，各自递归排序，然后把两个有序数组合并成一个。任何情况下时间复杂度都是 O(nlogn)，不会像快排那样在最坏情况下降级，而且它是稳定排序。代价是需要一个与数组等长的临时空间，以及递归调用栈的开销。

合并过程是归并排序最需要注意的地方。先看一个常规实现：

c复制void merge(int *a, int left, int mid, int right, int *tmp) {
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= right) tmp[k++] = a[j++];
    for (int p = left; p <= right; ++p) a[p] = tmp[p];
}

void merge_sort(int *a, int left, int right, int *tmp) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    merge_sort(a, left, mid, tmp);
    merge_sort(a, mid + 1, right, tmp);
    merge(a, left, mid, right, tmp);
}

这里有两个容易踩的坑。第一个，mid 计算千万不要写成 (left + right) / 2，当 left 和 right 都是很大的 int 时，加法可能溢出。虽然一般排序数组长度不会到 INT_MAX，但这是 C/C++ 代码评审里很常见的扣分点，顺手写成 left + (right - left) / 2 更稳妥。第二个，临时数组不要在每个递归调用里重新 malloc，正确做法是在主调用函数里一次分配好，然后通过参数传递下去。递归里反复分配内存，不仅慢，而且容易造成内存碎片。

归并排序对链表排序意义更大。链表不需要随机访问，用归并排序只要改变节点的 next 指针，就能做到原地排序。很多手写高级数据结构的场景里，归并排序是比快排更自然的选择。如果业务上要求稳定排序，且数据量大到不能用插入排序，归并排序几乎是唯一稳妥的答案。

3.3 快速排序：工程中最常用的排序，partition 才是核心

快排是 C 标准库 qsort 和其他很多库的基础实现，平均性能最好，常数小，且可以在数组上原地排序。它最核心的环节不是递归本身，而是 partition：选择一个基准值，把数组分成“小于等于基准”和“大于基准”两个部分，返回基准最终所在的下标，然后递归处理两侧。

最易写错的版本往往出现在 partition 的下标控制上。一个推荐的经典双指针写法如下：

c复制int partition(int *a, int left, int right) {
    int pivot = a[right];
    int i = left - 1;
    for (int j = left; j < right; ++j) {
        if (a[j] < pivot) {
            ++i;
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
    int tmp = a[i + 1];
    a[i + 1] = a[right];
    a[right] = tmp;
    return i + 1;
}

void quick_sort(int *a, int left, int right) {
    if (left >= right) return;
    int p = partition(a, left, right);
    quick_sort(a, left, p - 1);
    quick_sort(a, p + 1, right);
}

这段代码的思路是：用数组最后一个元素做基准，维护一个“小于区”的右边界 i，从左到右扫描，凡是小于基准的值就把它丢进“小于区”，最后把基准放到“小于区”右边界之后。这样写比挖坑法更不容易弄错，因为每次交换都明确前面是小于区、后面是待扫描区。递归时一定要处理成 p - 1 和 p + 1，如果直接传 p，当基准恰好是最大值或最小值时，会陷入无限递归。

快排的不稳定性显而易见：基准会和远处的元素交换，相等元素顺序会被打乱。但在绝大多数不需要稳定性的工程场景里，快排依然是首选，因为它对缓存友好、常数小、内存占用低。

3.4 快排的随机化与三向切分优化

标准快排在遇到已经完全有序的数组时，如果每次选最后一个元素或第一个元素当基准，partition 会把数组切成一大一小两个极度不平衡的部分，时间复杂度直接退化成 O(n²)。解决这个问题的思路有两种：随机选基准，或者三数取中。随机化会让每个输入都有概率选到好基准，虽然不能保证最坏情况不发生，但能把概率降到可以忽略。三数取中就是在区间首部、中间、末尾各取一个值，选择三个数中间的那个作为基准，这种方式在工程里更可控，不需要依赖随机数生成器。

还有一个很容易被忽略的问题是“大量重复元素”。比如一百万个元素全是 0 和 1，普通 partition 会把数组切成极小和极大两块，递归深度爆炸。这时候要用三向切分：把数组分成小于、等于、大于基准的三段，等于基准的中间段不再参与递归。三向切分在重复元素多的场景下能退化问题变成优势，甚至可以做到 O(n) 级别。面试时不需要把三向切分代码背得滚瓜烂熟，但能在普通快排基础上主动提到它，面试官通常会认为你不是只会背模板。

这些优化背后有一个共同逻辑：快排的性能取决于 partition 是否均衡。你写快排时如果发现“有序数组反而最慢”，不用慌，这就是缺乏随机化或中位数优化时的典型症状。在工程库的实现里，还会结合“小区间用插入排序”“迭代代替递归”等手段，因为这些优化都能在不同数据规模下真实提升执行速度。

4. 堆排序和线性排序：性价比和适用边界

4.1 堆排序：用二叉堆完成原地排序

堆排序利用的是完全二叉树的结构，不需要额外空间，时间复杂度稳定在 O(nlogn)。它把数组看成一个最大堆，堆顶是最大值，把堆顶交换到数组末尾，然后缩小堆的范围，再重新调整堆结构。整个过程最核心的是“下沉调整”函数，而不是“建堆”函数。

一个容易出错的点是数组下标从 0 开始，节点 i 的左子节点是 2*i+1，右子节点是 2*i+2，最后一个非叶子节点是 n/2-1。建堆时从最后一个非叶子节点开始，从后往前做下沉，比从前往后更符合堆的性质修正顺序。

c复制void sift_down(int *a, int n, int i) {
    while (1) {
        int max_idx = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && a[left] > a[max_idx]) max_idx = left;
        if (right < n && a[right] > a[max_idx]) max_idx = right;
        if (max_idx == i) break;
        int tmp = a[max_idx];
        a[max_idx] = a[i];
        a[i] = tmp;
        i = max_idx;
    }
}

void heap_sort(int *a, int n) {
    for (int i = n / 2 - 1; i >= 0; --i) {
        sift_down(a, n, i);
    }
    for (int i = n - 1; i > 0; --i) {
        int tmp = a[0];
        a[0] = a[i];
        a[i] = tmp;
        sift_down(a, i, 0);
    }
}

每次交换堆顶和末尾元素后，堆的有效范围减一，只管前 i 个元素。很多人会错在把第一次 sift_down 的范围写成 n，第二次也写成 n，这样末尾元素就会重新被拉回堆里，排序就不对了。堆排序不稳定，因为堆顶和末尾元素跨越式交换会破坏相等元素的相对顺序。它和快排、归并比常数较大，实际表现往往慢一些，但胜在“最坏情况也能保证 O(nlogn)”且空间 O(1)，适合对最坏性能有要求的嵌入式场景。

4.2 计数排序：用空间换时间的典型代表

计数排序是线性时间排序，但不基于比较。它的前提是数据范围有限且已知，一般只适合非负整数或者可以映射到非负整数的数据。比如成绩排序（0～100分）、年龄统计（0～120岁），计数排序一上去就是 O(n) 级别。

稳定版本的计数排序需要额外做前缀和，再从后往前填充输出数组。这个“从后往前”是保证稳定的关键：相同元素中，后出现的那个会先被放到靠后的位置，于是相对顺序被保留下来。

c复制void counting_sort(int *a, int n, int max_val) {
    int *cnt = calloc(max_val + 1, sizeof(int));
    int *out = malloc(n * sizeof(int));
    for (int i = 0; i < n; ++i) cnt[a[i]]++;
    for (int i = 1; i <= max_val; ++i) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; --i) {
        out[--cnt[a[i]]] = a[i];
    }
    for (int i = 0; i < n; ++i) a[i] = out[i];
    free(cnt);
    free(out);
}

这里的坑在于 calloc(max_val + 1, sizeof(int))，如果 max_val 很大，比如 2^31，这段代码会直接请求约 8GB 内存，程序必然崩溃。所以计数排序在使用前一定要评估值域范围。我见过有人拿它对 32 位随机整数排序，结果进程被杀掉后才意识到问题。正确做法是先扫描一遍数组，得到最大值和最小值，然后做值域偏移，比如对所有元素加一个偏移量映射到非负区间。

4.3 基数排序和桶排序：根据数据形态选择更聪明的方案

基数排序是逐位稳定的排序，从最低位开始，每一趟用计数排序或桶排序稳定地处理一位数字，最后整个数组天然有序。对于手机号、学号、身份证号这类定长整数，位数 k 固定，基数排序复杂度接近 O(n)，但它不是比较排序，不能一概而论地用在所有数据类型上。

桶排序则是把数据按值域切分到多个桶里，每个桶内部用快排或插入排序，最后按桶顺序拼接。桶排序适合浮点数据在一定区间内近似均匀分布的情况。比如对 0 到 1 之间的随机浮点数排序，分成 10 个桶，每个桶内数据量大致均匀，桶内排序代价就很小。如果数据严重倾斜，所有元素落进同一个桶，桶排序会退化。

这两个算法共同的核心思想是“利用数据的分布特征”来减少比较量。标准比较排序的下界是 O(nlogn)，但一旦知道数据的分布范围，就能突破这个下界。工程里的外部排序、大数据分桶归并，本质上也是在用类似思路换性能。面试如果遇到海量排序问题，不要条件反射只回答快排，先问数据特点，再决定是否用线性排序，这才是合格的工程师思路。

5. C 语言工程实现中的坑与通用化封装

5.1 C 语言排序最容易翻车的三个位置

第一个是边界条件。数组长度为 n，最后一个下标是 n-1，很多人写递归排序时把 [left, right] 闭区间和 [left, right) 半开区间混在一起。我自己最惨的一次是在快排里把递归区间写成 quick_sort(a, left, p)，遇到基准在最右侧时直接栈溢出。解决办法是统一约定：全文都用闭区间，所有递归和合并都按闭区间来写，不要一会半开一会闭。

第二个是循环变量被外层循环意外修改。排序代码里常有 i、j、k 多个游标，如果某个内层实现不小心把外层的 i 也当作临时变量用了，排序结果会非常诡异。我建议把交换操作封装成一个宏，或者在内部使用独立变量名，避免把外层索引拖进内层逻辑。

第三个是重复分配内存。归并排序如果在每个递归层次里都调用 malloc，在小规模数据上感觉不到，等数据量上到百万级就会明显变慢。正确做法是在排序入口函数中一次分配好临时缓冲区，然后递归时只传递指针。堆排序也建议把交换写成内存操作，避免在频繁调用里做多余的函数跳转。这些细节看起来小，但对 C 语言排序模块的性能影响非常直接。

5.2 用函数指针封装通用排序接口

C 语言的标准库 qsort 给了一个很好的示范：排序逻辑和元素比较方式解耦。我们也可以照着实现一套自己的排序接口，函数的参数从 int *a 改成 void *base、元素个数、元素大小、以及一个比较回调。这样同一套快排代码可以处理任意类型，包括结构体、指针、字符串数组。

关键在于 C 语言里 void* 不能直接做指针算术运算，需要先转成 char*，然后按元素大小 size 偏移。交换两个元素也不是简单交换指针，而是要按 size 个字节逐个搬运。比如：

c复制void my_sort(void *base, size_t nmemb, size_t size,
             int (*cmp)(const void *, const void *)) {
    char *arr = (char *)base;
    for (size_t i = 1; i < nmemb; ++i) {
        char key_buf[64];
        memcpy(key_buf, arr + i * size, size);
        size_t j = i;
        while (j > 0 && cmp(arr + (j - 1) * size, key_buf) > 0) {
            memcpy(arr + j * size, arr + (j - 1) * size, size);
            --j;
        }
        memcpy(arr + j * size, key_buf, size);
    }
}

这段只是一个示意，真正的快排封装还需要处理临时缓冲的 malloc 或变长数组。但思路已经够了：比较器统一成 int cmp(const void *a, const void *b)，返回值小于零表示 a 排在 b 前面。如果你要往工程里塞一个自己的排序库，这种设计能省掉大量重复代码，后续新增数据类型时只需要写新比较器，不需要改动排序核心。

5.3 稳定性的真实含义与多字段排序工程设计

稳定性在实际项目里最常见的应用是多字段排序。比如先按部门排序，再按绩效排序。如果第二趟使用不稳定排序，那么同一个绩效等级内部，部门顺序可能被打乱。很多业务页面里的“综合排序”并不是真正把两趟排序跑两遍，而是在比较器里先比较主键，主键相同再比较次键，一次排序就完成所有层级。

这个比较器写法在 C 语言里非常自然：

c复制int cmp_record(const void *a, const void *b) {
    const Record *ra = (const Record *)a;
    const Record *rb = (const Record *)b;
    if (ra->dept != rb->dept) {
        return ra->dept - rb->dept;
    }
    return ra->score - rb->score;
}

使用这种方式，即使底层算法是不稳定的，也不会出现业务逻辑上的稳定性问题，因为复合键本身已经把“先主后次”的信息交给一次排序去处理了。理解了这一点，就知道稳定性的价值更多体现在“多趟独立排序”的场景，而不是比较器追溯全部关键字的场景。这也是很多初学者容易误解的地方：不是所有多字段排序都必须用稳定算法。

6. 手写排序算法常见问题排查与实测心得

6.1 排序结果不对时按这个顺序排查

第一步看循环退出条件。下标是不是从 0 开始？j < n 还是 j < n - i？写错任何一个，排序要么越界，要么有一片区域永远没被覆盖。第二步看递归区间。快排和归并的递归参数，闭区间和半开区间不能混用。我之前排查过一个归并排序“后半段没排序”的问题，最后发现是 mid 的把左右边界算错了一位，导致右半数组全被丢掉。第三步看比较方向。升序是 a[j] > key，降序要反过来，这个看似简单，但很多人在交换条件上写反，结果排出来的数组恰好颠倒。

调试技巧上，我建议先跑三组小数据：空数组、单元素、两个元素。这三种情况最容易暴露越界和递归终止条件问题。然后跑一个完全逆序的数组，因为逆序往往是某类算法的最坏情况，能看出性能退化和递归栈问题。如果还是找不到原因，就在每轮循环后打印数组中间状态，不要用断点一步步走，那样很容易被大量状态刷花眼。

6.2 量级变大后性能骤降，原因可能不在排序本身

有人遇到“排序 1000 个元素很快，排 100 万个突然卡死”，第一反应是算法复杂度不对。但实际上，问题往往出在工程实现上。比如归并排序递归里反复 malloc 和 free，内存碎片和分配开销会在数据量变大后急剧放大；又比如交换元素时不是直接交换，而是反复插入删除操作，把一个结构体数组当成链表去维护；再比如比较函数里用了 strlen 或反复格式化字符串，导致比较开销远超排序本身。

我在实测 C 语言排序性能时，发现一个规律：先做性能分析，再做算法替换。用 perf 或简单的时间统计，看看时间到底花在比较、交换、循环还是内存分配。很多时候，把递归里的一次分配挪到入口处，性能就能翻倍，根本不需要换算法。快排之所以在真实世界成为默认选择，就是因为它的实现能够避免大量内存操作，而不是单纯因为复杂度是 O(nlogn)。

6.3 面试手写快排的三个建议

先把主流程写清楚，不要一上来就优化。普通双指针 partition、递归调用左右两侧，大概 20 行代码就能写完。写的时候注释好三个关键位置：partition 的返回值、左边递归区间、右边递归区间。很多面试者一紧张就把 p - 1 和 p + 1 写错，这种错误在面试官看来就是基本功不扎实。

第二个建议是主动聊基准值选择。如果面试官让你写快排，写完普通的版本后，最好主动提一句“这个版本在有序数组上可能退化，我可以用三数取中或者随机基准优化”。这句话本身就是加分项，说明你理解最坏情况从哪里来。第三个建议是测试场景覆盖到位。手写代码后自己口头跑一遍：空数组、单元素、两个元素、全部相同、逆序。如果函数里对空数组直接返回了，面试官会留下很好的印象。

6.4 实测经验：不同算法在千万级随机数据下的表现

我在一个普通开发机上做过简单测试，对 1000 万随机 int 数组排序，开启 O2 优化后，快排和归并都能稳定在 1 秒上下，归并因为临时数组的分配和拷贝略慢一点。堆排序明显更慢，常数大，但胜在不需要额外内存。插入排序在完全随机的数据上会肉眼可见地拉胯，但把它放在近乎有序的数据集里，表现甚至可以超过快排。选择排序在交换代价高的场景下有意义，但在普通内存数组里几乎找不到压倒性优势。

这些测试让我明白一个道理：算法复杂度表只能给出理论边界，真实工程里还要考虑缓存局部性、内存分配、比较器开销和数据分布。你不可能靠一张复杂度表解决所有排序需求，但把所有排序算法都亲手写一遍、跑一遍、调试一遍之后，你会形成自己的选型直觉。这个直觉，比死记“哪个排序是 O(nlogn)”重要得多。

我自己在写这套排序代码的过程中，最大的收获不是代码写得多熟练，而是终于理解了“为什么要稳定”“为什么要随机化”“为什么归并必须开额外空间”这些以前只能靠背的结论。排序算法这个题目，初看简单，但挖下去，几乎能覆盖算法与数据结构里所有核心思想。如果你还没动手把多种排序算法完整实现一遍，我建议你今天就挑一两个开始，先从插入和快排写起，再逐步补齐其他算法，你会明显感觉到自己的基本功变得更扎实。