排序算法这块很多朋友一开始是冲着背代码去的但背着背着就乱了——七种排序各自的代码长得差不多又各有各的坑考场上稍一紧张就把快排的 partition 写成死循环了。这篇东西就是把这七大排序直接插入、希尔、冒泡、快速、简单选择、堆、归并掰开揉碎讲清楚。每个算法我都按“思想图解 → 步骤拆解 → 代码实现 → 易错提醒”的顺序来写全程用 C 语言风格伪代码配套考点提示适合正在学数据结构、准备 408 考研或者期末突击的朋友。你看完会发现排序这东西根本不用背理解了它的脾气之后代码是顺着思路自己流出来的。1. 七大排序的整体架构与学习主线很多初学者拿到排序章节第一反应是七个算法放一起怎么记我的建议是先别急着码代码先在脑子里搭一个分类框架。1.1 为什么偏偏是这七个算法数据结构教材里标杆性排序远不止七种还有基数排序、计数排序这类非比较排序但核心的比较排序里教材反复拎出来讲的就是这七种。原因很简单它们覆盖了三种最基本、面试和考试中最高频的思想维度——插入、交换、选择外加一个分治策略的归并。你把这三个维度的框架立住了后面学什么排序都不会乱。在实际应试里这七个算法的出场率确实是最高的。408 统考、各大厂校招笔试、期末考试大题翻来覆去考的就是复杂度推导、稳定性判断、手写核心代码以及哪种场景选哪种排序。七种算法里快排是推荐系统、数据库底层最常用的排序思路堆排是大数据 TopK 的标配归并是外部排序和链表排序的基石而插入排序则是所有排序里开窍的第一步。把这七个吃透就等于把整个比较排序的体系盘活了。1.2 学习排序的三要素框架我辅导过不少学生发现大家排序学得混乱根本原因是没建立分析维度。看任何一个排序算法你只需要盯住三件事时间复杂度最好、最坏、平均分别是多少各自对应什么输入分布。空间复杂度是否原地排序是否需要额外辅助数组或递归栈。稳定性相同关键字的元素排序后相对顺序是否保持不变这在多关键字排序场景下非常重要。这三要素不是孤立的知识点。比如快排平均 O(n log n) 但最坏退化 O(n²)这个退化恰恰是因为 partition 极度不平衡导致的堆排时间复杂度稳定但在实际系统中反而不如快排常用是因为它访问内存不连续对缓存不友好。一旦你开始用三要素去横向对比算法优劣很多纠结自然就解开了。我用下面这张总表先给你一个全局观后续每个算法小节都会回到这张表来展开解释排序算法最好时间复杂度平均时间复杂度最坏时间复杂度空间复杂度稳定性直接插入排序O(n)O(n²)O(n²)O(1)稳定希尔排序依赖增量序列约 O(n^1.3)O(n²)O(1)不稳定冒泡排序O(n)O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定简单选择排序O(n²)O(n²)O(n²)O(1)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定1.3 从时间和空间两条维度横向对比除了三要素我建议你再从宏观行为上感知这几个算法的差异。最直观的一个维度是数据移动方式。插入类和冒泡类排序每次比较后只交换相邻元素每趟排序最多移动一个位置这类算法在数据基本有序时表现极好最好情况能到 O(n)。而选择类和希尔、快排、堆排这类跳跃式排序每次比较后可能跨越很远距离移动数据整体上加速了排序过程但也失去了稳定性因为跨距移动容易把相同值的相对顺序打乱。另一个维度是是否依赖初始序列。依赖初始序列的算法有插入排序、冒泡排序、快速排序它们在数据接近有序时效率显著提升不依赖初始序列的算法有简单选择、堆排、归并它们的效率完全由 n 决定。为什么因为前者每趟比较能提前终止比如冒泡已有序就停止交换而后者的比较次数是数学上固定的。理解了这一层你就知道为什么有时候数据已经排好了快排反而变慢了——因为退化成了最坏情况。2. 插入类排序直接插入与希尔排序插入类排序的核心思想一句话把待排序的元素逐个插入到已经有序的序列中像打扑克时整理手牌一样。这个思路朴素但衍生出的希尔排序却是第一个突破 O(n²) 壁垒的排序算法值得认真对待。2.1 直接插入排序的图解流程直接插入排序的整个流程非常直观。假设当前数组是[5, 2, 4, 6, 1, 3]我们从第二个元素开始往前看第一趟取2与前面的5比较5 往后挪把 2 放到位置 0序列变成[2, 5, 4, 6, 1, 3]。第二趟取4依次与5、2比较4 比 5 小所以 5 后挪4 比 2 大所以停在位置 1序列变成[2, 4, 5, 6, 1, 3]。第三趟取6和前面的 5 比比 5 大直接不动。第四趟取1一路往前比把前面所有比自己大的元素都往后挪一位最后插入到位置 0。第五趟取3同理插入到位置 1。如此迭代 n-1 趟所有元素就有序了。这个往前挪的过程本质上是tmp arr[i]; j i-1; while(j 0 arr[j] tmp) { arr[j1] arr[j]; j--; } arr[j1] tmp;的操作。注意arr[j] tmp这个条件用的是严格大于也就是说相等的元素不会发生交换相等值的相对顺序被完整保留——这就是它稳定的根源。你画图的时候会发现每一趟排序后序列前半部分始终有序。这跟选择排序不一样选择排序是每趟找到最小值放到前面但前面未必有序插入排序则是每趟都维护前面整体有序后面待处理的元素不断插入到这个有序区中。2.2 直接插入排序的代码实现与考场细节C 语言风格实现直接插入排序非常短void insertSort(int arr[], int n) { int i, j, tmp; // 从第二个元素开始逐个插入 for (i 1; i n; i) { if (arr[i] arr[i - 1]) { // 这句判断是优化关键 tmp arr[i]; j i - 1; while (j 0 arr[j] tmp) { arr[j 1] arr[j]; j--; } arr[j 1] tmp; } } }考场上有两个细节容易丢分第一while (j 0 arr[j] tmp)里的j 0一定要写在前面否则当 j 变成 -1 时再去访问arr[j]就越界了。第二if (arr[i] arr[i-1])这个判断不能省它是优化代码的关键——如果当前元素已经比有序序列最后一个元素大说明它已经在正确位置直接跳过这一轮内层循环。这在数据基本有序时能省掉大量无意义的比较。复杂度方面最好情况是数组本身有序每趟只需比较一次就结束总比较次数 n-1时间复杂度 O(n)最坏情况是逆序比较和移动次数都是 n(n-1)/2O(n²)。空间复杂度 O(1)。稳定性方面因为只有arr[j] tmp才移动相等的元素不移动所以是稳定的。提醒408 和期末考经常考一个问题数组基本有序时哪种排序最快答案就是直接插入排序因为它的最好情况是 O(n)而快排和选择排序在这种场景下依然要老老实实跑完 O(n²) 或 O(n log n)。2.3 希尔排序的增量思想图解希尔排序是插入排序的跳跃版本它引入了增量gap概念先让相距 gap 的元素组成一个逻辑子序列分别做插入排序然后缩小 gap再排序直到 gap 为 1 做最后的全体插入排序。为什么这样做会快因为直接插入排序最致命的问题是移动太慢每次只能挪一步如果最小的元素在最后面它要一步步挪到最前面消耗 O(n) 次移动。希尔排序先按大步长把远处的小元素快速传送到前面数据整体接近有序后最后一步 gap1 的插入排序就非常快。图解一个例子数组[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]第一趟取 gap5下标 0 和 5 一组8 和 3插入排序后为3, 9, 1, 7, 2, 8, 5, 4, 6, 0。下标 1 和 6 一组9 和 5排序后为3, 5, 1, 7, 2, 8, 9, 4, 6, 0。下标 2 和 7 一组1 和 4排序后不变。下标 3 和 8 一组7 和 6排序后为3, 5, 1, 6, 2, 8, 9, 4, 7, 0。下标 4 和 9 一组2 和 0排序后为3, 5, 1, 6, 0, 8, 9, 4, 7, 2。可以看到最小的元素 0 从位置 9 直接跳到了位置 4再经过下一轮 gap2 的排序就能很快到达前面。这就是跳跃式插入排序的优势所在。2.4 希尔排序的代码与增量序列选择希尔排序代码基于直接插入排序改了一个外层循环void shellSort(int arr[], int n) { int gap, i, j, tmp; // 增量序列n/2, n/4, ..., 1 for (gap n / 2; gap 1; gap / 2) { for (i gap; i n; i) { // 对每个子序列做插入排序 tmp arr[i]; j i - gap; while (j 0 arr[j] tmp) { arr[j gap] arr[j]; j - gap; } arr[j gap] tmp; } } }这段代码里最有意思的地方是for (i gap; i n; i)这一行。表面上看是遍历整个数组实际上它把间隔 gap 的子序列交叉在一起处理每个元素都跟它前面 gap 位的元素比较。这样写比先处理第 0 组、再处理第 1 组更简洁逻辑上也等价。增量序列对希尔排序的效率影响很大。教材常见的 n/2 折半序列实现简单但最坏情况依然是 O(n²)。比较经典的优化序列有 Hibbard 增量序列2^k - 1最坏情况能压到 O(n^(3/2))Sedgewick 序列能达到 O(n^(4/3))。考试如果问希尔排序的时间复杂度标准答法是取决于增量序列平均大约 O(n^1.3)最坏 O(n²)不必死记具体推导。稳定性方面希尔排序因为分组后跨距交换相同元素可能被分到不同组并发生交换所以是不稳定的。我在这个点上吃过亏有次笔试问稳定的 O(n²) 算法有哪些我写了希尔排序当场白给一分。3. 交换类排序冒泡排序与快速排序交换类排序的核心动作是比较 → 交换区别在于冒泡是相邻交换快排是跳跃交换。两者的性能天差地别但思想上是一脉相承的。3.1 冒泡排序的图解与优化点冒泡排序每趟从前往后扫描如果相邻两个元素逆序就交换这样每趟都会把当前未排序部分的最大值冒泡到末尾。以[5, 2, 4, 6, 1, 3]为例第一趟下来6会浮到最右边第二趟5浮到倒数第二依次类推。代码很简单void bubbleSort(int arr[], int n) { int i, j, tmp; // 用一个 flag 标记本趟是否发生交换 for (i 0; i n - 1; i) { bool swapped false; for (j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped true; } } // 如果本趟没有交换说明已经有序提前结束 if (!swapped) break; } }这个swapped标志是冒泡排序的灵魂优化。如果某趟扫描发现一次交换都没发生说明序列已经有序直接终止外层循环。加了这行代码后冒泡排序在基本有序场景下最快可以到 O(n)不加的话即使有序也要跑满 n-1 趟。冒泡排序是稳定的只有arr[j] arr[j1]才交换相等元素不会跨越彼此相对位置保持不变。空间 O(1)。实战经验很多人觉得冒泡排序太笨了实际编码里确实不会用它处理大量数据但它的价值在于探测有序性。比如数据流场景里你需要判断一个几乎有序的序列是否真的有序冒泡天然给你答案因为一趟扫描无交换就说明有序。3.2 快速排序的核心 partition 图解快速排序的思想是分治任选一个基准元素 pivot把数组分成两部分左边所有元素 ≤ pivot右边所有元素 ≥ pivot然后对左右子数组递归继续。这里最关键的是 partition划分怎么实现。教科书里最常见的 partition 是挖坑法或左右指针法。我演示左小右大的左右指针法选定最左边元素5为 pivotleft 指针指向下标 0right 指针指向下标 n-1。先从右往左找第一个比 pivot 小的元素停下再从左往右找第一个比 pivot 大的元素停下交换两者。重复上述过程直到 left 和 right 相遇。相遇点就是 pivot 的最终位置把 pivot 与相遇点交换。以[5, 2, 4, 6, 1, 3]为例pivot5right 先往左走找到3下标 5比 5 小left 往右走找到6下标 3比 5 大交换 6 和 3 得到[5, 2, 4, 3, 1, 6]。然后 right 继续左移找到1下标 4left 右移与 right 相遇在下标 4此时交换 pivot 5 和 1得到[1, 2, 4, 3, 5, 6]。以 5 为界左边全小于它右边全大于它第一趟 partition 完成。int partition(int arr[], int low, int high) { int pivot arr[low]; // 选第一个元素为基准 while (low high) { // 从右向左找比 pivot 小的元素 while (low high arr[high] pivot) high--; arr[low] arr[high]; // 挖坑填数 // 从左向右找比 pivot 大的元素 while (low high arr[low] pivot) low; arr[high] arr[low]; } arr[low] pivot; // 基准归位 return low; } void quickSort(int arr[], int low, int high) { if (low high) { int pos partition(arr, low, high); quickSort(arr, low, pos - 1); // 递归左半区 quickSort(arr, pos 1, high); // 递归右半区 } }3.3 快排的退化风险与工程优化技巧快排平均时间复杂度 O(n log n)空间复杂度 O(log n)递归栈深度但有一个致命弱点当每次 partition 选中的 pivot 恰好是当前区间最小值或最大值时划分极端不平衡递归树变成一条链时间复杂度退化为 O(n²)。最典型的退化场景就是数组已经有序 固定选第一个元素作 pivot。每次 pivot 都是最小值右侧递归树深度 n总比较次数 n(n-1)/2。很多新手第一次用快排排序一个有序数组直接被性能吓到就是这个原因。工程上的优化手段主要有四种随机选取 pivot在low到high之间随机选一个下标交换到 low 位使最坏情况概率趋近于零。三数取中法取low、mid、high三个位置的中位数作为 pivot能有效避免有序数组的退化。小区间使用插入排序当递归区间长度小于某个阈值比如 15时不再递归直接对小区间做插入排序。因为插入排序在数据量小时开销低于快排的递归开销。尾递归优化对递归栈深度进行控制减少栈溢出风险。考试和面试里你至少要知道有序数组 固定 pivot 导致快排退化 O(n²)这个结论然后能说出随机化和三数取中两种优化方案就够了。至于具体的随机数生成、三数取中代码属于加分项。经验分享我在实际写快排的时候习惯把 pivot 选中间位置的元素 ——int pivot arr[(lowhigh)/2]这样对于很多特殊输入都能自动避开退化。虽然理论上依然存在最坏情况但工程上已经足够稳。考试手写代码时如果题目没有特别要求写自然的递归版本就行但一定要在 partition 前加一行随机交换显得你有工程意识。4. 选择类排序简单选择与堆排序选择类排序的核心是每趟选出一个极值放到最终位置。简单选择每趟线性扫描选最小值堆排序则用堆这种数据结构加速选最小值的过程。4.1 简单选择排序的图解与代码简单选择排序的思路最直观第一趟扫描全部元素找到最小值放到下标 0第二趟扫描下标 1 到 n-1找到最小值放到下标 1重复 n-1 趟。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; } } }代码里有个细节if (minIdx ! i)保证了只有在找到更小元素时才交换。这不仅是为了减少无意义的赋值更重要的是如果两个元素相等选择排序不会做出多余的交换这在某些评判标准下能保住稳定性。但严格来说选择排序并不能保证稳定性——看一个例子[5, 5, 1]第一趟最小值 1 与第一个 5 交换两个 5 的相对顺序虽然没有变化但如果后面有和第一个 5 相等的另一个 5交换后相对位置就可能改变。所以标准结论是简单选择排序不稳定。无论数组是否有序简单选择排序的比较次数都是 n(n-1)/2时间复杂度恒定 O(n²)这也是它死板的一面。空间 O(1)。实际开发中基本不用它但考试必考因为它是每趟选一个极值思想最简单的载体。4.2 堆排序的建堆过程图解堆排序利用的是完全二叉树结构的数组表示。大根堆满足父节点值 ≥ 子节点值堆顶就是最大值每趟把堆顶与末尾元素交换然后对堆顶做下沉调整就能依次把最大值放到末尾。建堆的过程是从最后一个非叶子节点开始从下到上、从右到左做下沉调整。对数组[4, 10, 3, 5, 1, 8, 7]来说n7最后一个非叶子节点的下标是 n/2 - 1 2也就是值 3 的节点。以它为例节点 3 的左右孩子下标分别是 5值 8和 6值 78 最大且大于 3交换 3 和 8。接着处理下标 1值 10它的左右孩子是下标 3值 5和下标 4值 110 已经大于两个孩子无需调整。再处理下标 0值 4它的左右孩子是下标 1值 10和下标 2值 810 最大且大于 4交换 4 和 10交换后下标 1 的子树可能被破坏继续对下标 1 做下沉发现它的孩子是 5 和 14 小于 5继续交换直到越界。经过这个过程数组变成了[10, 5, 8, 4, 1, 3, 7]一个大根堆就建成了。void siftDown(int arr[], int k, int n) { int tmp arr[k]; // 暂存待下探的节点 while (k * 2 1 n) { // 存在左孩子 int child k * 2 1; // 如果右孩子存在且更大选取右孩子 if (child 1 n arr[child 1] arr[child]) { child; } if (tmp arr[child]) break; // 父节点已不小于较大孩子 arr[k] arr[child]; // 孩子上移 k child; // 继续向下比较 } arr[k] tmp; } void heapSort(int arr[], int n) { // 建堆从最后一个非叶子节点开始 for (int i n / 2 - 1; i 0; i--) { siftDown(arr, i, n); } // 依次把堆顶元素与末尾交换并调整 for (int i n - 1; i 0; i--) { int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; siftDown(arr, 0, i); // 对缩小后的堆继续调整 } }4.3 堆排序的复杂度分析与实战定位堆排序建堆过程的时间复杂度是 O(n)注意不是 O(n log n)数学推导是利用二叉树高度累加得到的总和公式证明过程考试偶尔会考然后每趟下沉调整是 O(log n)共 n 趟总体 O(n log n)。空间 O(1)这是它对比归并排序最大的优势。稳定性方面堆顶元素与末尾元素交换时可能打乱相同值的相对位置所以不稳定。堆排序工程上有个隐藏短板内存访问是跳跃式的对 CPU 缓存非常不友好。同样 O(n log n)实际运行时间往往比快排慢 2~5 倍。所以日常排序任务语言标准库基本都用快排比如 C 的 qsort、C 的 std::sort 内省式混合排序而堆排序真正的用武之地是 TopK 问题——在海量数据里找最大的 K 个元素维护一个小根堆堆顶就是当前第 K 大的门槛值每个新元素只需跟堆顶比较复杂度 O(n log K)比全排序快得多。教训有次我在项目里用堆排序给 10 万条用户记录排序实测比快排慢了三倍还不止。后来查资料才发现问题出在缓存局部性上。从那以后我给自己定了个规矩——堆排序只用在需要原地排序且对最坏时间复杂度有硬性要求或者TopK、堆这种二选一场景一般数据排序直接调用标准库快排。5. 归并排序分治思想的完美实践归并排序和前面几个排序思路都不一样。它的核心理念是先把问题切到最小再向上合并整个过程分拆和合并两个阶段典型的分治策略。5.1 归并排序的图解流程归并排序把数组递归拆成两半直到每个子数组长度为 1天然有序然后两两合并有序数组依次向上返回。拿[8, 4, 5, 7, 1, 3, 6, 2]举例递归拆到最底层分成 8 个单元素数组。合并[8]和[4]成[4, 8]合并[5]和[7]成[5, 7]合并[1]和[3]成[1, 3]合并[6]和[2]成[2, 6]。继续合并两个长度为 2 的有序数组[4, 8]和[5, 7]归并成[4, 5, 7, 8][1, 3]和[2, 6]归并成[1, 2, 3, 6]。最后合并[4, 5, 7, 8]和[1, 2, 3, 6]得到[1, 2, 3, 4, 5, 6, 7, 8]。这个归并过程就是经典的二路归并两个指针分别指向两个有序数组头部谁小谁进入临时数组直到全部处理完。其中的一笔关键账是归并排序的比较次数是固定的无论数组初始顺序如何每层都要做 n 次比较合并层数是 log n总复杂度稳定 O(n log n)。它不会像快排那样退化这是它最大的优势。5.2 归并排序的代码实现与空间开销void merge(int arr[], int left, int mid, int right) { int i left, j mid 1, k 0; int n right - left 1; int* tmp (int*)malloc(sizeof(int) * n); // 临时数组 while (i mid j right) { if (arr[i] arr[j]) { tmp[k] arr[i]; } else { tmp[k] arr[j]; } } while (i mid) tmp[k] arr[i]; // 左边剩余 while (j right) tmp[k] arr[j]; // 右边剩余 for (i 0; i n; i) { arr[left i] tmp[i]; // 回写 } free(tmp); } void mergeSort(int arr[], int left, int right) { if (left right) return; int mid (left right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); }注意 merge 里的条件arr[i] arr[j]用的是小于等于而不是小于这样当左右两个子数组里有相等元素时左边数组的元素先被取出右边相等元素的相对顺序依然在它之后归并排序因此是稳定的。这个细节很多教材不提但手写代码时一旦写错稳定性就丢了。空间复杂度是 O(n)因为每一层递归归并都要用到临时数组虽然递归深度 log n但同一时刻最多有一个完整长度的临时数组占用所以额外空间是 O(n)。这也是归并排序唯一的软肋——内存开销大。但对于链表这类不能用随机访问的结构归并排序反而是最佳选择因为它只需要遍历指针就能实现排序。5.3 归并排序的复杂度推导与多路归并扩展归并排序时间复杂度的推导可以用递推公式表达设 T(n) 是对 n 个元素排序的时间则有 T(n) 2T(n/2) O(n)。用主定理或者展开计算可得 T(n) O(n log n)。考试有时候会让你展开推导过程是T(n) 2T(n/2) n 4T(n/4) 2n ... 2^k T(n/2^k) k·n当 n/2^k 1 时 k log n所以 T(n) n·T(1) n log n O(n log n)。归并排序在实际工程中还有一个重要变体外部排序。当数据量大到内存放不下时比如 10GB 文件排序操作系统层面就是把文件切块每块装载内存做归并排序再通过多路归并合并成有序大文件。这就是为什么数据库和 MapReduce 底层离不开归并排序。理解了二路归并自然就能扩展到 K 路归并用一个大小为 K 的最小堆来快速选取 K 个序列中最小的当前元素每次堆调整 log K整体效率 O(n log K)。6. 排序代码易错细节与考试避坑指南最后这部分我从实战和考试角度出发把七大排序里最容易翻车的几个点集中拎出来帮你快速自查。这个板块的信息是普通教材里不会专门给你标记出来的血泪教训。6.1 边界条件与循环终止条件排序代码写错九成是边界问题。我总结了几个高频雷区while (j 0 arr[j] tmp)里j 0的位置。一旦 j 变成 -1 才去访问 arr[j]在 C/C 里就是数组越界在 Java 里直接抛异常。正确做法是 j 减到 -1 之前就判断循环是否继续。冒泡排序内层循环j n - 1 - i这个- i是为了忽略已经浮到末尾的有序区域。漏掉- i不会让结果错误但会徒增大量无意义比较。快排 partition 里的while (low high arr[high] pivot)不能丢掉low high这个前置条件。原因很简单如果 pivot 是当前区间最小值high 指针会一路左移越过 low出现 low high 的混乱状态整个数组就被穿串了。堆排序中n / 2 - 1是最后一个非叶子节点下标前提是数组下标从 0 开始。如果你用的是从 1 开始的数组最后一个非叶子节点下标是n / 2两者不能混用考试时尤其容易搞混。6.2 稳定性判断的快速记忆法稳定性是选择题、判断题的常客。死记硬背容易混我教你一个推理记忆法稳定直接插入排序相等不移动、冒泡排序相等不交换、归并排序左边先取。这三个的共同特点是只在相邻或有序合并时操作相等元素不会跨距交换。不稳定希尔排序分组跨距交换、简单选择排序极值跨越交换、堆排序堆顶与末尾交换、快速排序partition 时相等元素可能被越过。一句话口诀快些选堆不稳定快排、希尔、选择、堆排剩下三个稳定。这个谐音梗我用了很多年屡试不爽。6.3 每个排序的最好情况考点总结408 和面试有一个高频对比题以下排序算法中哪些的最好时间复杂度是 O(n)答案是直接插入排序、冒泡排序带 flag 优化版。原因我在前面说过这两个算法能提前终止而其他算法无论输入如何都必须跑完固定轮次。还有一个容易混淆的点简单选择排序的时间复杂度不随初始序列变化无论有序还是逆序都是 O(n²)。它的选择最小值操作必须扫描完剩余所有元素才能确定没有提前终止的机制。而归并排序也不依赖初始序列始终保持 O(n log n)但它的常数因子较大小数据量排序不如插入排序快。6.4 面试和考试现场手撕排序的万能策略如果面试官让你手写排序我建议你按照这个策略来如果只说写个排序优先写插入排序 快排两个。插入排序证明你基本功扎实快排证明你有高级算法意识两者互补。如果面试官指定手写快排一定要在开头加一句我选随机 pivot 或三数取中来避免有序数组退化这是明显的加分项很多候选人栽在这里。如果面试官问海量数据 TopK用堆排序思路给出 O(n log K) 方案并说明为什么不用快排——快排必须全量数据都在内存中大数据场景下内存不够。如果面试官问链表怎么排序直接答归并排序因为链表的随机访问特性决定了快排的 partition 在链表上效率很低而归并只需要指针操作。考试手撕代码时时间有限写核心函数即可。我给你的建议是先把 partition 单独写出来再写快排的递归函数堆排序则分 siftDown 和 heapSort 两个函数写。函数的拆分本身就是给阅卷老师的得分点因为即使最后结果有小 bug核心逻辑的步骤分也拿到了。平时练习的时候不要光在 IDE 里跑一定要在纸上手写几遍因为 IDE 的自动补全会掩盖你对变量声明和循环结构的真实掌握程度。最后说几句个人感受。排序算法这章我当年学的时候也觉得难但后来发现的规律是这七个算法本质上就三种思维模式插入类是维护有序区交换类是比较后交换选择类是每趟选极值归并是分而治之再合并。你只要抓住每种思维模式的一句话核心代码就像顺着思路自己长出来一样根本不用背。面试和考试再怎么变核心考的就是这几个算法的复杂度、稳定性、边界条件、场景适配。把这篇文章里每一个算法的图解流程和易错点过一遍再自己动手在纸上画几轮排序的过程这个章节你就彻底拿下了。