企业官网建设流程全解析

我在刷题平台做算法训练的时候，最先想跳过的题型就是排序。原因很现实：日常写业务代码直接调内置方法，谁还手写冒泡？但刷题平台里“排序数组”这类题目明摆着告诉你，别用内置排序，手写一遍。于是问题来了：冒泡、选择、插入、快速、计数这五种排序，看着都懂，一动手就各种边界错、超时、排序结果不对。今天就把这五兄弟放在一起，从原理、代码、复杂度到实际刷题时的坑，一次性捋清楚。

这五种排序基本覆盖了面试和算法入门里的主流思路：有最直观的交换类排序，有利用“部分有序”的插入排序，有分治思想的快速排序，还有不基于比较的计数排序。理解它们不只是在 LeetCode 上过一道排序题，更是在理解算法复杂度、稳定性、原地操作、递归这些底层概念。我会尽量不用废话，直接把能落地的实现和踩坑记录写出来。

1. 先把排序算法在 LeetCode 里的位置搞清楚

1.1 为什么刷题要先过排序这一关

很多人觉得排序题目简单，不值得花时间。实际上，排序是后续很多题目的基石。二分查找要求有序数组，合并区间先要排好序，求第 K 大元素本质上也在考分区思想和堆排序。我在刷题早期有个很深的教训：看到“两数之和”想到哈希表没问题，但遇到“合并区间”这种明显需要先排序的题，如果排序没想清楚，整个解题流程就会卡在第一步。

另外，刷题平台里很多题不允许直接用内置排序函数，要求手写。这就逼着你必须掌握至少一种稳定、高效的排序实现。快速排序和归并排序是主流，但冒泡和插入也不是没用，它们在特定场景下甚至更快。比如数组趋于有序时，插入排序的表现可以接近 O(n)；数据范围很小时，计数排序能跑到 O(n)。只知道“用 sort”而不理解背后的选择逻辑，写复杂题时很容易手足无措。

1.2 五种排序横向对比与选型思路

先给一张我总结的对照表，后面再逐个细说。这张表不需要背，关键是理解每一栏背后的含义。

选型时我一般这样判断：如果数据规模很小，冒泡、选择、插入随便选，代码简单不容易错；如果数据规模大，优先写快速排序，配合随机 pivot 基本不会踩到最坏情况；如果数据是范围有限的整数，比如一千以内、十万个数的成绩排名，计数排序是性能怪物。刷题时并不要追求“一个算法打天下”，而是要让每个算法在最合适的场景下发挥价值。

2. 冒泡排序：最直观但最容易写错的交换排序

2.1 实现与优化细节

冒泡排序的核心思想非常直观：每一轮把相邻的两个元素比较，如果顺序不对就交换，这样每一轮结束后，最大的元素会“冒”到数组末尾。重复 n 轮后，整个数组有序。它的循环边界特别容易写错，尤其是内层循环的终止条件。

看这段 Python 实现：

def bubble_sort(nums): n = len(nums) for i in range(n): swapped = False for j in range(n - i - 1): if nums[j] > nums[j + 1]: nums[j], nums[j + 1] = nums[j + 1], nums[j] swapped = True if not swapped: break return nums

注意内层循环range(n - i - 1)的-1是从哪来的。第 i 轮开始时，数组末尾已经有 i 个元素排好了，所以它们不需要再参与比较。而比较nums[j]和nums[j+1]时，j最多取n-i-2，正好访问到倒数第二个元素，避免索引越界。如果不加-1，最后一轮会比较nums[n-1]和nums[n]，直接报错。

优化点在于swapped标志。如果某轮从头到尾没有任何交换，说明数组已经完全有序，可以提前退出。这个优化在处理“基本有序”的数组时收益很大。假设输入是[1, 2, 3, 4, 5, 6]，第一轮扫过一遍发现没有交换，直接结束，时间复杂度降到 O(n)。在 LeetCode 的隐藏用例里，经常有近乎有序的数组，这个优化有时候能把超时救回来。

2.2 冒泡排序的适用场景与踩坑

冒泡排序在刷题里很少作为最终答案，因为它平均 O(n²) 的复杂度摆在那里，数据量稍大就会超时。但它非常适合理解“交换排序”和“稳定性”的概念。我见过不少初学者把冒泡写成这样：

for i in range(n): for j in range(i + 1, n): if nums[i] > nums[j]: nums[i], nums[j] = nums[j], nums[i]

这个写法其实是“选择排序”的变体，每一轮把nums[i]和后面每个元素比较，大数不断换到后面，最后也能排好，但它不是传统意义上相邻交换的冒泡。如果面试官问“冒泡排序的特点是什么”，你的回答是“相邻元素两两比较，不稳定”，但代码里写的却是非相邻交换，印象分会大打折扣。

另一个常见坑是忘记提前退出优化，导致明明swapped已经 False 了，还在继续空跑循环。对于一万个有序数字，没有优化的冒泡要跑一亿次比较，有优化则只跑一万次，差别非常大。刷题时如果看到大数据量，冒泡基本不该出现在答案里，但如果是手写代码题，允许你选择算法，尽量选性能更好的。

3. 选择排序：不稳定但思路最干净

3.1 实现原理与代码

选择排序的思路比冒泡更直接：每一轮从未排序区间里找出最小值的下标，把它和当前区间第一个元素交换。重复 n 轮后，整个数组有序。它的比较次数依然很多，但交换次数最多只有 n 次，这是它相对于冒泡的一个优势。

def selection_sort(nums): n = len(nums) for i in range(n): min_idx = i for j in range(i + 1, n): if nums[j] < nums[min_idx]: min_idx = j if min_idx != i: nums[i], nums[min_idx] = nums[min_idx], nums[i] return nums

这段代码里最值得说的是min_idx的初始化。它是每一轮“当前最小元素的位置”，如果忘记更新，或者把 j 错写成 i，排序结果就会出错。我早期写过把nums[min_idx]和nums[j]比较搞反的代码，导致最后结果是从大到小排。所以建议在代码里明确命名：min_idx表示下标，不是数值。

3.2 为什么说选择排序不稳定

稳定性指的是：两个相等的元素，排序后相对顺序保持不变。选择排序为什么不稳定？看一个最简单的例子：[5, 8, 5, 2]。第一轮找到最小元素 2，下标为 3，把它和下标 0 的 5 交换。交换后，原本在后面的 5 跑到最前面，原本在前面的 5 移到后面，两个 5 的相对顺序被破坏了。

理解稳定性在 LeetCode 里有什么用？很多问题要求“排序后保持原有顺序”，比如按成绩排序，成绩相同的按学号排序。如果底层排序不稳定，就可能需要额外记录索引或者改成稳定排序。常见的稳定排序有冒泡、插入、归并、计数排序；不稳定排序有选择、快速、堆排序。我在写“根据某个属性排序且要求同属性保持原序”的题时，会先确认自己用的排序算法是否稳定，避免出现逻辑问题。

选择排序的实际应用场景主要是数据量小、且希望交换次数尽量少的场景。在刷题里它不会是最优解，但它是理解“每轮选择一个最小值”这类算法的入门钥匙。后面要学的堆排序，本质上就是一种利用堆结构快速找到最小值/最大值的选择排序优化版。

4. 插入排序：接近有序时效率惊人的“摸牌”算法

4.1 实现细节与边界处理

插入排序的思路可以用打扑克牌来理解：你手里已经有一堆排好序的牌，新摸到一张牌时，从右手边开始逐个往前比较，找到合适位置插进去。数组实现时，我们要把待插入的元素先保存下来，然后将前面比它大的元素统一后移，最后把保存的元素放到空出来的位置。

def insertion_sort(nums): n = len(nums) for i in range(1, n): v = nums[i] j = i - 1 while j >= 0 and nums[j] > v: nums[j + 1] = nums[j] j -= 1 nums[j + 1] = v return nums

这里最重要的边界条件是j >= 0。如果写成while nums[j] > v，当 j 变成 -1 时，nums[-1]会取到数组最后一个元素，结果完全不可控，而且很难排查。在 Python 这种负索引友好的语言里尤其要注意。

另一个容易出错的点是最后nums[j + 1] = v，而不是nums[j] = v。因为循环退出时 j 已经到了第一个不大于 v 的位置，v 应该插入在 j 的后面。很多人这里少加了一个 1，导致元素被放进已经错误的位置。

4.2 插入排序在复杂算法中的应用

插入排序单独用在 LeetCode 上机会不多，但它是很多高级排序的“底牌”。比如快速排序在实际工程中，当递归区间长度小于某个阈值（比如 16）时，会改用插入排序，因为小数组上递归调用的开销远大于插入排序本身。归并排序同样可以在小数组时切换到插入排序。这种优化策略在刷题时不一定需要实现，但理解它能帮助你分析哪些算法更适合小规模数据。

插入排序对“近似有序”的数据非常高效。假设数组中每个元素距离最终位置不超过 k，插入排序的时间复杂度可以达到 O(nk)。LeetCode 中有些题会给“几乎有序”的条件，此时如果贸然使用快速排序，反而不如插入排序直观。日常开发里，比如日志列表已经按时间排好，新来几条少量数据需要合并排序，插入排序就能直接用上。

插入排序稳定、原地、实现简单，是第一个值得认真掌握的“在线”算法：它可以在接收流式数据时，一边插入一边保持数组有序。虽然直接大量插入会导致 O(n²)，但在很多实时场景里，数据量不大，它是最容易维护的方案。

5. 快速排序：实际工程里最常用的分治排序

5.1 分区思想与基础实现

快速排序是整个排序算法体系里的重头戏。它采用分治策略：选择一个基准元素 pivot，把数组分成小于 pivot 和大于等于 pivot 的两部分，然后递归处理左右部分。关键就在于 partition（划分）这一步怎么写。

最常见的写法是 Lomuto 分区法：取最右边元素作为 pivot，用两个指针 i 和 j 扫描数组。j 负责遍历，i 始终指向“下一个小于 pivot 的元素应该放的位置”。扫描结束后，把 pivot 放到中间位置。

def quick_sort(nums, left, right): if left >= right: return pivot = nums[right] i = left for j in range(left, right): if nums[j] < pivot: nums[i], nums[j] = nums[j], nums[i] i += 1 nums[i], nums[right] = nums[right], nums[i] quick_sort(nums, left, i - 1) quick_sort(nums, i + 1, right)

这个实现简洁，但有两个需要注意的点。第一，range(left, right)不包括 right，也就是 pivot 本身不参与扫描。第二，分区完成后，pivot 已经在i位置，递归时左右区间必须跳过它，否则会死循环。我在刷题时遇到过递归栈溢出，就是因为递归区间没写好，把 pivot 又放进去了。

5.2 随机化与三路快排

快速排序最坏情况是 O(n²)，典型场景是数组已经有序时，如果固定取最右元素作为 pivot，每次分区有一边为空，递归深度变成 n。解决方式是引入随机化：在[left, right]范围内随机选一个下标，和nums[right]交换，再继续用 Lomuto 分区。这样即使输入有序，也能大概率避免最坏情况。

import random def quick_sort_random(nums, left, right): if left >= right: return pivot_idx = random.randint(left, right) nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx] pivot = nums[right] i = left for j in range(left, right): if nums[j] < pivot: nums[i], nums[j] = nums[j], nums[i] i += 1 nums[i], nums[right] = nums[right], nums[i] quick_sort_random(nums, left, i - 1) quick_sort_random(nums, i + 1, right)

随机化在 LeetCode 上非常关键。如果测试用例里故意包含大量重复元素或有序数组，固定 pivot 的快排很容易超时。更好的方案是三路快排：把数组分成小于 pivot、等于 pivot、大于 pivot 三个区间，这样所有等于 pivot 的元素一步到位，不用参与后续递归。处理“数组包含大量重复值”的排序题时，三路快排的耗时远小于普通快排。

def quick_sort_3way(nums, left, right): if left >= right: return pivot = nums[right] lt = left gt = right i = left while i <= gt: if nums[i] < pivot: nums[lt], nums[i] = nums[i], nums[lt] lt += 1 i += 1 elif nums[i] > pivot: nums[gt], nums[i] = nums[i], nums[gt] gt -= 1 else: i += 1 quick_sort_3way(nums, left, lt - 1) quick_sort_3way(nums, gt + 1, right)

这个写法里lt是小于区的右边界，gt是大于区的左边界，i是当前扫描位置。当nums[i] > pivot时，把i位置的元素和gt交换，但i不自增，因为交换过来的元素还没看过。只有当元素小于等于 pivot 时，i才会移动。这个细节非常容易写错，建议自己走一遍[3,1,3,2]的例子。

5.3 快速排序在 LeetCode 中的进阶应用

快速排序不止是用来给整个数组排序。它的分区过程天然可以用于“找第 K 大”的问题。比如 LeetCode 经典题“数组中的第K个最大元素”，可以先 partition，如果 pivot 的位置正好是 n-K，就直接返回；如果小于，就去右区间找；如果大于，就去左区间找。这样平均时间复杂度是 O(n)，比先排序再取元素更高效，因为不需要把整个数组排好。

还有一个常见应用是“颜色分类”问题，本质上就是三路快排的一次 partition，只不过区间的值不是三个任意数，而是 0、1、2。用三路快排的思想可以一趟扫描把数组分成三段，不需要递归，空间复杂度 O(1)。

写快排时还有一个练习方向是非递归实现。虽然刷题时 Python 默认递归深度大概在一千左右，一万个元素的有序数组如果发生最坏情况，递归会栈溢出。使用随机 pivot 后，概率很低，但为了保险，可以用显式栈模拟递归。我一般把快速排序当成“必须能默写”的算法，递归和非递归都要会。

6. 计数排序：突破比较排序下限的非比较排序

6.1 适用条件与完整实现

计数排序不是基于比较的排序，它利用的是数值范围的有限性。思路很简单：统计每个数值出现的次数，然后根据统计结果把元素放回原数组。时间复杂度是 O(n + k)，其中 k 是数值范围。当 k 远小于 n 时，效率非常高。

但计数排序有强前提条件：数据必须是整数，或者可以映射成整数；数值范围不能太大。如果数据最大是一亿，最小是零，虽然只有十个元素，也要开辟一亿长度的数组，内存直接爆炸。所以刷题时看到数据范围很大，不要硬套计数排序。

我在实现时习惯加上偏移量，让排序支持负数：

def counting_sort(nums): if not nums: return [] min_val = min(nums) max_val = max(nums) k = max_val - min_val + 1 count = [0] * k for v in nums: count[v - min_val] += 1 # 前缀和，用于稳定排序 for i in range(1, k): count[i] += count[i - 1] n = len(nums) res = [0] * n for v in reversed(nums): pos = count[v - min_val] - 1 res[pos] = v count[v - min_val] -= 1 return res

这个版本用了前缀和，所以是稳定排序。如果不要求稳定性，可以更简单地按频次填充：

res = [] for i in range(k): res.extend([i + min_val] * count[i])

但很多 LeetCode 题目要求稳定，或者后续需要基于这个排序再做其他操作，所以我习惯写前缀和版本。注意for v in reversed(nums)这一步正是稳定性的关键。倒序遍历原数组时，相同的元素会从后往前被放入结果数组，保持它们在原数组中的相对顺序。

6.2 计数排序的实战场景

计数排序在 LeetCode 里很少作为单独考点，但它在一些看似需要高级算法的题目里能提供“作弊级”性能。比如“根据字符出现频率排序”，字符串中字符的范围只有 26 个英文字母（或者 256 个 ASCII），完全可以用计数排序。还有“有序数组的平方”这类题，通常双指针最优，但计数排序也能做，只是没必要。

我踩过的一个坑是忽略偏移量导致数组越界。比如 nums 里全是负数，直接count[v] += 1会报错，因为下标不能为负。必须先用min_val做偏移。反过来，如果数据包含很大的正数，count数组也要开得足够大，否则会访问越界。刷题时最好先看题目给的数据范围约束，再决定是否使用计数排序。

另一个实战技巧是：计数排序可以当作“哈希表”的替代品来理解。它记录的是值到频次的映射。在很多计数类题目里，即使不需要最终排序结果，也要用到“统计每个数字出现次数”这一步，这就是计数排序的前半部分。比如“缺失的第一个正整数”问题，在不允许额外 O(n) 空间时，用计数思想配合下标映射，可以原地统计。

7. 常见问题与排查技巧实录

7.1 排序结果不对，先查边界和下标

我见过最多的 bug 集中在几个地方：内层循环范围少减一、插入排序忘记处理 j 为负数、快排递归区间没有跳过 pivot、交换元素时写错了下标。排查这类问题有一个笨但有效的办法：找一个小数组，比如[4, 2, 2, 8]，手动在纸上走一遍代码，标出每一步数组的变化。通常走到第二步就能发现是哪一行逻辑出了问题。

另外，Python 刷题时一定要小心负索引。比如nums[-1]表示最后一个元素，不是报错。当循环变量不小心变成 -1 时，程序不会崩溃，但会有诡异结果。我建议所有数组下标操作都加注释，尤其在循环边界处。

7.2 超时问题：从 O(n log n) 到 O(n)

LeetCode 超时通常不是代码写错了，而是算法复杂度不够。如果你的排序题用了冒泡或选择，数据量在一万以上，基本会超时。此时应该换成快速排序或者计数排序。如果是快速排序超时，大概率是固定 pivot 撞上了测试用例的“有序数组”或者“大量重复元素”。解决办法就是随机 pivot 或三路快排。

有时候超时不是排序本身的问题，而是你在排序时做了多余的操作。比如复制了整个数组，或者每次比较都调用一个耗时的函数。刷题时优先保证原地排序，减少不必要的append和extend，空间和时间都能省下来。

7.3 稳定性与额外空间怎么记忆

整数数组排序本身不太在意稳定性，因为相等的整数无法区分。但在结构体排序里，稳定性就很重要。比如按成绩排序，成绩相同的学生希望保持原来的学号顺序。冒泡、插入、归并、计数是稳定排序；选择、快速、堆排序不稳定。我记忆的方法是：稳定排序大多是把相等元素“搬”到另一侧，而不是“跨越”其他元素。冒泡和插入只在相邻元素间交换，保持顺序；归并合并时优先取左半部分，保持顺序。选择排序会把最小值交换到前面，可能跨越其他相等元素，所以不稳定。

额外空间方面，冒泡、选择、插入、快排（递归栈不算）都是原地排序；归并排序需要 O(n) 额外数组；计数排序需要 O(k) 辅助空间。如果题目限制了常数空间，计数排序就不能用。快速排序虽然原地，但递归调用栈平均是 O(log n)，不算严格 O(1)。这一点在面试或者讨论题解时容易被问到。

7.4 刷题时的个人建议

我在实际刷题过程中，排序算法大概反复写了三轮。第一轮是看题解背代码，第二轮是动手默写，第三轮是总结每个算法的适用边界。我的体会是，不要死记代码，要给每个算法找到一个“触发关键词”。比如“相邻交换”就想到冒泡，“每轮选最小”就想到选择，“摸牌”就想到插入，“分治随机 pivot”就想到快排，“整数范围小”就想到计数排序。

遇到 LeetCode 的排序类题目，先读题目的数据范围。如果 n 小于 1000，写个插入排序一般也能过，但最好知道为什么能过；如果 n 到十万，就要谨慎选择 O(n²) 算法；如果数值范围很窄，优先考虑计数排序。这个判断过程比代码本身更重要。

最后再分享一个小技巧：在本地练习时，把五种排序写在一个文件里，用一个随机的[5,1,4,2,8]数组作为测试用例，每写完一个算法就打印结果。这样能快速发现手误，也能加深对算法细节的记忆。面试前不用刷几十道题，把这五种排序默写三遍，比背题解更有用。