企业官网建设流程全解析

一直觉得C语言的排序算法是个特别有意思的专题，冒泡、选择、插入、快排、归并、堆排，名字都能背下来，但真到动手写、写对、写快、写稳的时候，很多人就露怯了。我这些年面试过不少候选人，也帮人改过不少竞赛和课程设计的代码，发现同样的排序题，不同人能写出完全不同的境界。这篇就把C语言里最核心的那几个排序算法掰开揉碎讲一遍，每个都配上可直接编译运行的完整代码，把时间复杂度的推导逻辑、稳定性背后的工程意义、以及只有真正写过才会踩到的坑都说清楚。

这篇内容适合正在学C语言和数据结构的初学者，准备校招社招面试的开发者，以及需要在嵌入式或高性能场景下手写排序的工程师。看完你不仅能写出正确的排序，还能在面试里讲清楚为什么这么写、什么时候用哪种。

1. 排序算法整体设计与选型思路

1.1 为什么还需要手写排序算法

很多人第一反应是：C语言标准库里有qsort，C++有std::sort，Java有Arrays.sort()，为什么还要自己写排序？这个问题我在面试里被反向问过很多次，也在实际项目中遇到过必须手写排序的场景。

先说最现实的场景。嵌入式裸机开发中，很多环境根本没有完整的C标准库，或者库里的排序函数因为代码体积、栈空间限制根本不敢用。我在一个资源极紧张的单片机项目里就遇到过这种情况，ROM只有几十KB，RAM更是按字节算，这时候一个精简的插入排序或堆排序，比调用一个庞大的库函数要实在得多。

再说学习层面的价值。排序是理解算法设计思想的绝佳载体：分治思想看快排和归并，二叉树思想看堆排，增量策略看希尔排序，暴力穷举看冒泡和选择。你把排序吃透了，后面学查找、动态规划、贪心算法，思维模型都会顺很多。大学里讲数据结构，排序永远排在查找前面，就是为了让你先建立"操作数据"的直觉。

还有一个非常实际的原因是面试。算法面试中排序几乎是必考内容，但考的不是让你背代码，而是考察你能不能分析复杂度、能不能处理边界条件、能不能在特定约束下选择合适的算法。我面试别人的时候经常出这道题：有一个几乎已经排好序的大数组，只有少量元素错位，你会选什么排序？很多候选人上来就答快排，这恰恰说明他对算法缺少工程感知。正确答案应该是插入排序的变体，因为插入排序在近乎有序的数据上能做到接近O(n)的时间复杂度。

1.2 比较排序的统一评价维度

在动手写代码之前，我得先把一组很重要的评价维度讲清楚，否则你根本不知道怎么在算法之间做选择。排序算法的评价主要看四个维度：时间复杂度、空间复杂度、稳定性、以及是否原地排序。

时间复杂度和空间复杂度大家都熟悉，我重点说说稳定性和原地排序。稳定性指的是：如果两个元素的值相等，排序后它们在原数组中的相对顺序能否保持不变。为什么这个指标重要？最典型的例子是Excel表格的多字段排序。你先按姓名排一遍，再按班级排一遍，如果第二次用的是稳定排序，同一班级内部仍然是按姓名排好的；如果是不稳定排序，第一次排序的结果就完全白费了。实际业务中这种多级排序的需求非常普遍，这就是为什么归并排序在很多场景下不可替代。

原地排序则是指排序过程中是否需要额外的存储空间。不需要额外空间的算法空间复杂度是O(1)，比如堆排序；需要O(n)辅助数组的归并排序，在内存受限的嵌入式场景就可能不合适。

我把经典的七大比较排序算法先放在一个表里，这样你心里有个全局图，后面再逐个展开。

这张表建议你反复看，直到能默写出来。面试官问到任何排序算法，你先把这张表在脑子里过一遍，就成功了一半。

1.3 工程选型的真实约束

光会背表还不够，工程选型需要结合数据特征。数据规模、数据分布、内存限制、是否需要稳定排序，这四个约束条件组合起来，会把你引向完全不同的算法。

数据量小于50的时候，插入排序往往比其他O(n log n)算法还快。原因在于它没有递归调用开销，没有额外的数组拷贝，常数因子极小。很多工业级快排实现里，当递归划分到小区间时就直接切换到插入排序，靠的就是这个特性。数据量在几千到几万，内存又不紧张，归并排序是个好选择，稳定且性能可预期。数据量很大，内存又受限，堆排序最稳妥，它保证最坏情况也是O(n log n)，不像快排那样有退化风险。数据基本有序？插入排序是王道。数据含大量重复元素？三路快排是专门针对这种情况设计的。

我在实际项目中总结出来的经验是：不要迷信某一个算法，而是在每次排序前先问问自己四个问题。数据有多大？内存够不够？数据本身有什么特征？排序结果需不需要稳定？这套决策流程走下来，选型基本不会错。

2. 经典排序算法的核心实现与细节解析

2.1 冒泡排序：理解交换与优化的起点

冒泡排序是所有排序算法里最直观的一个。它的核心思想很简单：从头到尾依次比较相邻的两个元素，如果顺序不对就交换，一趟下来最大的元素就像气泡一样冒到了最后。下一趟继续，直到所有元素有序。

#include <stdio.h> void bubble_sort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int swapped = 0; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; swapped = 1; } } if (!swapped) { break; } } }

注意我加了一个swapped标志位，这是冒泡排序最常见的优化。如果某趟遍历中一次交换都没发生，说明数组已经完全有序，直接终止。这个优化让冒泡排序在最好情况下（数据完全有序）的时间复杂度降到了O(n)。

关于冒泡排序的稳定性，每次只交换相邻的逆序对，相等的元素永远不会交换位置，所以它是稳定的。但冒泡排序的效率确实不高，O(n^2)的平均复杂度让它只能作为教学算法存在。实际应用中很少用它，但它作为理解"交换排序"思想的第一课非常有价值。

2.2 选择排序：最直观的"找最小"策略

选择排序的思路比冒泡还要简单：每一趟从无序区中找到最小的元素，放到有序区的末尾。也就是说，第i趟排序就是在区间[i, n-1]里找最小值，然后和arr[i]交换。

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

写选择排序的时候，有一个很多初学者容易犯的错误：在找最小值的过程中就急着交换。比如发现arr[j]比arr[min_idx]小，就马上交换，这样虽然也能排对，但交换次数大幅增加，而且破坏了选择排序"每趟只交换一次"的特性。正确做法是先记录最小值下标，整趟扫描结束后再交换一次。

《CLRS》里用循环不变量来证明选择排序的正确性，这个思路很值得掌握。循环不变量在这里就是：前i个元素已经是有序的，且它们是整个数组中最小的那i个元素。每一趟迭代后，区间[0, i]扩大一个元素，性质依然保持。循环开始时成立，循环中保持，循环结束时自然推出整个数组有序。这种证明方法后面用到快速排序、归并排序时同样适用。

选择排序有个明显弱点：它不稳定。原因就在交换这一步。假设数组是[5, 3, 5, 1]，第一趟找到的最小值是1，把它和第一个5交换，原本在前面的5就被换到了后面，两个5的相对顺序就被破坏了。这个细节面试中经常被追问，记住这个例子就能讲清楚。

2.3 插入排序：处理近乎有序数据的利器

插入排序的思路像整理扑克牌。你摸到一张新牌，会把它插到手里已经排好序的牌中合适的位置。算法实现上，从第二个元素开始，往前扫描已经排好序的部分，找到合适的位置插入。

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

这个实现里有个重要细节：key变量必须提前保存出来，因为后面的元素后移操作会覆盖掉arr[i]。很多初学者直接写成arr[j + 1] = arr[j]然后最后arr[j + 1] = arr[i]，结果发现arr[i]早就被覆盖了。

插入排序的平均复杂度是O(n^2)，最好情况是O(n)。数据越接近有序，它的表现越好。这个特性让它在真实工程中很有价值，因为很多场景下的数据并不是完全随机的，而是带有一定顺序的。我给一个朋友优化一个日志处理程序时，发现他维护的列表基本有序，只是偶尔插入几个新条目，把原来的快速排序换成插入排序后，整体耗时反而下降了30%。原因就是快排的递归和分区开销在数据量小且近乎有序时完全是浪费。另外注意，插入排序是稳定排序，因为后移时遇到相等元素就停下来，插到相等元素的后面。

2.4 希尔排序：插入排序的跨越式升级

希尔排序是插入排序的改进版，它解决了插入排序一个核心痛点：插入排序每次只能把元素移动一个位置，如果最小的元素恰好在最后面，要把它移到最前面需要移动n次。希尔排序的做法是先让数组中任意间隔为gap的元素都有序，然后逐步缩小gap，最后gap=1时就是对整个数组做一次插入排序。

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

这个实现用的是最朴素的希尔增量序列n/2, n/4, ..., 1。每一趟gap排序都是把间隔gap的子序列分别做插入排序，距离为gap的元素可以一次跳gap步，所以大大减少了移动次数。

希尔排序的时间复杂度分析比较复杂，取决于增量序列的选择。朴素的折半增量最坏是O(n^2)，但有一些精心设计的增量序列可以做到O(n^(4/3))甚至更好。有一个非常实际的经验：对于中等规模（几百到几千）的数据，希尔排序的实际运行时间往往不输给快排，因为它不需要递归，常数因子非常小。我在一些对代码体积有要求、又不想引入复杂排序算法的嵌入式项目中，就经常用希尔排序作为折中方案。

希尔排序是不稳定的，原因在于间隔gap排序会跨越多个位置交换元素，相等的元素可能被不同的子序列处理，相对顺序就可能颠倒。

2.5 归并排序：稳定性与分治的完美结合

归并排序是经典的"分而治之"策略：先把数组对半分成两部分，分别排序，再把两个有序数组合并成一个有序数组。关键在于merge操作，它利用了两个子数组各自有序的特点，用双指针线性扫描完成合并。

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 merge_sort(int arr[], int left, int right) { if (left >= right) { return; } int mid = left + (right - left) / 2; merge_sort(arr, left, mid); merge_sort(arr, mid + 1, right); merge(arr, left, mid, right); }

注意mid的计算用了left + (right - left) / 2而不是(left + right) / 2，这是为了防止left + right溢出。虽然在这个场景下不容易溢出，但这是C语言算法题里一个非常普遍的隐患，养成习惯就好。

归并排序的空间复杂度是O(n)，因为每次合并都需要临时数组。我最开始学归并排序的时候，总觉得每次递归都申请临时数组会很浪费，后来想明白了：虽然每一层递归都创建临时数组，但同一时刻只有一条递归路径上的数组是有效的，加上栈空间，总共就是O(n)的辅助空间加上O(log n)的递归栈空间。

归并排序的次数复杂度是严格的O(n log n)，最好最坏都一样，而且它是稳定排序。在merge时，当L[i]和R[j]相等时，我们取左边子数组的元素，这就保证了稳定性。这一点在C语言里写结构体多重排序时非常有用。另外可以加一个优化：如果arr[mid] <= arr[mid+1]，说明两个子数组合并前已经整体有序，可以跳过merge操作，这在处理近乎有序数据时能省下不少时间。

2.6 快速排序：工程上最快的比较排序

快排的核心是partition操作：选一个基准元素，把数组分成左右两部分，左边的都小于等于基准，右边的都大于等于基准，然后对左右两边递归排序。

int partition(int arr[], int low, int high) { int pivot = arr[low]; int i = low, j = high; while (i < j) { while (i < j && arr[j] >= pivot) { j--; } if (i < j) { arr[i++] = arr[j]; } while (i < j && arr[i] <= pivot) { i++; } if (i < j) { arr[j--] = arr[i]; } } arr[i] = pivot; return i; } void quick_sort(int arr[], int low, int high) { if (low >= high) { return; } int p = partition(arr, low, high); quick_sort(arr, low, p - 1); quick_sort(arr, p + 1, high); }

上面的写法叫挖坑法。基准元素先被拿出来，留下一个"坑"，然后从右边找一个小于基准的数填到坑里，右边留下新坑，再从左边找一个大于基准的数填到右边的坑，反复交替，最后把基准放回最终位置。这个实现比Swap交换法的交换次数少，在工程中也更常用。

快排平均时间复杂度O(n log n)，但最坏情况会退化到O(n^2)。退化发生的条件也很典型：如果数组已经有序，而每次选基准都选到第一个或最后一个元素，那么每次分区只减少一个元素，递归深度变成n，复杂度自然退化成O(n^2)。这是快排最大的软肋，工程上一般用两种手段缓解。第一是三数取中，在arr[low]、arr[mid]、arr[high]三者中取中间值做基准，极大程度避免有序数组退化。第二是小区间切换到插入排序，比如当区间长度小于10时直接用插入排序收尾，减少递归调用开销。

void quick_sort_opt(int arr[], int low, int high) { while (low < high) { if (high - low < 10) { insertion_sort(arr + low, high - low + 1); return; } int mid = low + (high - low) / 2; if (arr[mid] < arr[low]) { int tmp = arr[low]; arr[low] = arr[mid]; arr[mid] = tmp; } if (arr[high] < arr[low]) { int tmp = arr[low]; arr[low] = arr[high]; arr[high] = tmp; } if (arr[high] < arr[mid]) { int tmp = arr[mid]; arr[mid] = arr[high]; arr[high] = tmp; } int tmp = arr[low]; arr[low] = arr[mid]; arr[mid] = tmp; int p = partition(arr, low, high); if (p - low < high - p) { quick_sort_opt(arr, low, p - 1); low = p + 1; } else { quick_sort_opt(arr, p + 1, high); high = p - 1; } } }

上面这个优化版本包含了三数取中、小区间插入排序、以及尾递归优化。尾递归优化的思路是：每次都递归处理元素少的一侧，元素多的一侧用循环继续处理，这样能把递归深度控制在O(log n)以内，避免栈溢出。

2.7 堆排序：最坏情况也稳定的性能底线

堆排序利用了完全二叉树的性质。这里我用大顶堆来排序：先把数组调整成一个大顶堆，堆顶就是最大值，把堆顶和末尾元素交换，然后对前n-1个元素重新调整堆，重复这个过程就得到了升序结果。

void sift_down(int arr[], int start, int end) { int root = start; while (2 * root + 1 <= end) { int child = 2 * root + 1; if (child + 1 <= end && arr[child] < arr[child + 1]) { child++; } if (arr[root] < arr[child]) { int tmp = arr[root]; arr[root] = arr[child]; arr[child] = tmp; root = child; } else { break; } } } void heap_sort(int arr[], int n) { for (int i = n / 2 - 1; i >= 0; i--) { sift_down(arr, i, n - 1); } for (int i = n - 1; i > 0; i--) { int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; sift_down(arr, 0, i - 1); } }

建堆的过程是从最后一个非叶子节点开始往前依次做下沉调整。为什么不用从叶子节点开始？因为叶子节点本身满足堆的性质，没必要调整。最后一个非叶子节点的下标是n/2 - 1，这个公式要记住，它来自完全二叉树的下标关系。

堆排序最大的优势是：空间复杂度O(1)，最坏时间复杂度O(n log n)，没有快排那样退化到O(n^2)的风险。这也是为什么在一些对最坏性能有硬性要求的实时系统中，宁可选择堆排序也不用快排。不过堆排序有一个容易被忽略的缺点：它对缓存的利用非常差。因为堆排序访问数组是跳跃式的（父子节点下标相差两倍），不像快排那样顺序访问，所以在现代CPU的缓存架构下，堆排序的实际运行速度往往不如快排。我实测过在10万元素级别，快排通常比堆排序快两到三倍。

堆排序还不稳定，这一点在面试里也经常被问到。另外补充一点，很多人以为堆排序只是用来排序，其实它更重要的应用是求Top-K问题。在百万级数据中找出最大的100个，维护一个大小为100的小顶堆，一遍扫描就能搞定，内存占用极小，这是堆这个数据结构的真正用武之地。

3. 实测对比与性能复盘

3.1 基准测试环境与测试数据设计

光看理论分析还是不够，排序算法到底谁快谁慢，跑一组数据心里才有底。我编写了一套简单的基准测试程序：生成随机数据、近似有序数据、大量重复数据三类测试集，数据规模从1万到50万，统一开-O2优化编译，用clock()计时。

测试数据的设计是有讲究的。随机数据测试算法的平均性能，近似有序数据测试算法对有序数据的适应能力，大量重复数据测试算法在重复元素场景下的表现。在实际业务里，这三种数据分布基本覆盖了大多数场景。

#include <stdio.h> #include <stdlib.h> #include <time.h> void generate_random(int arr[], int n) { for (int i = 0; i < n; i++) { arr[i] = rand() % 1000000; } } void generate_nearly_sorted(int arr[], int n) { for (int i = 0; i < n; i++) { arr[i] = i; } for (int i = 0; i < n / 20; i++) { int a = rand() % n; int b = rand() % n; int tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; } } void generate_duplicated(int arr[], int n) { for (int i = 0; i < n; i++) { arr[i] = rand() % 100; } }

generate_nearly_sorted模拟的是"基本有序但有些错位"的真实场景，先把数组按升序生成，再随机交换其中5%的元素。generate_duplicated则模拟大量重复数据，值域只有0到99。

3.2 实际耗时数据与分析方法

以下是我在本地跑出的一组典型数据（耗时单位毫秒，-O2编译，数据规模10万）：

这组数据显示了几个重要结论。第一，插入排序在近似有序场景下几乎无敌，8毫秒是全场最优，这验证了"几乎有序用插入排序"的工程经验。第二，基础快排在近似有序和大量重复数据下表现不佳，分别达到420毫秒和260毫秒，这正是退化导致的。因为我的基础快排每次都取第一个元素做基准，近似有序数据会让分区极度不平衡，大量重复数据则让partition的扫描失去意义。第三，归并排序在三种数据分布下都很稳定，没有明显短板，代价是O(n)的额外空间。

这个实验也解释了为什么工业级排序库极少使用"裸快排"。无论是C++的std::sort还是很多数据库的排序实现，在快排的基础上都做了三数取中、小区间插入排序、以及针对重复元素的三路划分优化。纯粹的快排只是一个教学原型，离工程可用还有距离。

3.3 标准库qsort与手写实现的取舍

C标准库提供了qsort函数，它在很多平台上内部是优化的快速排序变体。用法很简单：

#include <stdlib.h> int compare_int(const void *a, const void *b) { int x = *(const int *)a; int y = *(const int *)b; return (x > y) - (x < y); } qsort(arr, n, sizeof(int), compare_int);

注意比较函数的写法。这里用(x > y) - (x < y)而不是直接return x - y，这是为了避免整数溢出。如果x很大y很小，x - y可能溢出为负数，导致比较结果错误。这个细节在面试和实际编码中都很容易踩坑。

qsort的性能通常不错，但有两个问题。一是它通过函数指针调用比较函数，每次比较都有一次间接调用的开销，在数据量大时这个开销不可忽略。二是qsort的实现细节取决于标准库，无法保证是稳定排序。在商业项目中，如果只是做一次普通的数组排序，我建议直接用qsort，省时省力。但如果是对性能敏感的热路径，或者需要稳定排序、需要对特定数据分布做优化、或者运行环境缺少标准库，那就值得自己写一个专用的排序函数。比如自己写一个针对int数组的快排，去掉函数指针调用，直接用<比较，实测在10万元素级别能比qsort快20%左右。

4. 常见问题与排查实录

4.1 边界条件与区间表示

排序算法里最容易出bug的就是边界。我帮人review代码时见过最多的问题是：for循环的终止条件多了个等号，导致越界访问；或者区间表示混乱，一会儿左闭右闭、一会儿左闭右开，自己把自己绕晕。

我的建议是：每个排序函数在实现前，先明确区间表示。比如归并排序和快排，我习惯用左闭右闭区间[left, right]，这样递归调用的边界非常清晰。left >= right时表示区间为空或只有一个元素，直接返回。习惯了这种写法后，各种边界判断都变得有规律可循。

另外一定要单独测试几个边界用例：空数组、单元素数组、两个元素数组、全部相等的数组。这些用例在单元测试中都必须通过。我见过不少人排序代码在正常数据上完全没问题，一跑空数组就崩，原因就是没有在函数开头检查n <= 1。

4.2 稳定性问题与字符串排序的实际联系

稳定性这个词在理论课上可能只是一个定义，但在真实业务里它直接决定结果对不对。举一个我做过的例子：一个字符串排序需求，需要先按长度升序排，长度相同的按字典序排。最简单可靠的做法是：先用字典序排一遍，再用稳定排序按长度排一遍。第二次排序只要是稳定的，长度相同的字符串就自然保持了第一次字典序的结果。如果第二次用的是不稳定排序，比如选择排序，那么长度相同的字符串顺序会乱掉，整个结果就错了。

这个例子里，归并排序是最合适的选择。插入排序也可以，只要数据量不大。但绝对不能选择排序或堆排序。这里的判断依据就是稳定性。你在选算法之前，先回答一个问题：数据里有没有多个字段需要依次排序？有的话，最后一轮排序（或倒数第二轮）必须用稳定排序。

4.3 递归深度的隐患与栈溢出

归并排序的递归深度固定是O(log n)，这个很安全。快排就危险了，最坏情况下递归深度能达到O(n)。我在一个实际项目中就遇到过：对10万个逆序数据排序，裸快排直接栈溢出崩溃。排查过程很曲折，一开始以为是数据问题，后来定位到递归深度超过了默认栈空间限制。

解决方案有几种。最简单的是在partition之前随机打乱数据，让退化概率降到极低。更妥当的做法是采用尾递归优化，像我在2.6节展示的那样，只递归处理较小的一半，较大的一半用循环处理。最彻底的方案是换成堆排序或归并排序，它们没有这种退化风险。在实际工程里，如果数据来源不可控、无法保证分布特征，我倾向于用堆排序兜底，或者直接用迭代实现的非递归快排。

4.4 交换操作中的隐蔽陷阱

交换两个变量，初学者最喜欢写经典的三行代码：tmp = a; a = b; b = tmp;，这当然是正确的。但有些教材为了追求"炫技"教人用异或交换：a ^= b; b ^= a; a ^= b;，这个写法在大多数情况下也能工作，但有一个致命陷阱：如果a和b指向同一个内存地址，异或三次会把值清零。

这个坑在排序里真的会踩到。比如快排的partition中，如果两个指针最终指向同一位置并触发交换，用异或交换就会把那个位置的元素变0。我见过一个真实的案例：一段用异或交换的快排代码，在特定数据下总是莫名出现0，排查了几天才找到原因。从此我在所有代码里都坚持用中间变量交换，不追求这种没有实际收益的"优化"。你说它炫吗？是挺炫的，但它省不了多少性能，却可能带来灾难性的后果。

5. 实战项目中积累的几条核心建议

写了这么多年代码，排序算法用了一轮又一轮，有几条建议想单独拎出来说。

第一条，背代码没有意义，要背决策逻辑。面试官一问排序，你不要直接开始背快排，而是先说清楚你的选择依据。数据规模多大、数据特征如何、是否需要稳定、内存有没有限制，把这四个问题回答完，再写代码，面试官对你的评价会完全不同。

第二条，一定要自己写一遍基准测试。不要以为理解了复杂度分析就够了，实际跑一遍数据，你才会真正明白常数因子对性能的影响有多大。我在没有亲自跑测试之前，也以为堆排序挺快，直到看到它被快排稳稳压了一头，才真正理解了"复杂度相同不等于性能相同"这句话。

第三条，如果是在真实项目中，优先用标准库，不要自己造轮子。qsort能解决大部分问题。但你要保证自己造轮子的能力——面试会考，嵌入式场景会用到，而且理解排序原理本身就是一个工程师的基本素养。

排序这类基础算法，真的是写一次有一次的新体会。我每次回头重写这些代码，都会发现自己能写出一点不同的优化。这可能就是基础算法的魅力，它就在那里，但你和它之间可以有无数种对话方式。