企业官网建设流程全解析

写业务代码这些年，真正从头手写排序的次数一只手数得过来，但每次被问到、每次要调优一段跑得慢的代码，最后拼的都是这十个算法里攒下的底子。冒泡、选择、插入、希尔、归并、快速、堆、计数、桶、基数——十个名字，背后其实是五类截然不同的思路：交换、插入、选择、分治、桶思想。很多人背下了复杂度和代码模板，却说不清"为什么快排要比归并快""为什么 Java 对基本类型和对象用了两套排序""为什么明明有库函数还要自己写"。这篇笔记我按"数据怎么动"这条线把十大排序算法重新捋一遍，每个算法给算法思想、给能看懂的文字图解、给可直接跑的代码，重点讲清工程里真正会踩的坑：基准怎么取、边界怎么写、什么时候快排会退化成 O(n²)、稳定性在什么场景下会咬你一口。适合正在准备数据结构与算法笔记的同学，也适合写了几年代码想把底层逻辑补回来的开发者。读完之后，你至少应该能做到三件事：看到一组数据能立刻判断该用哪个算法、能手写快排和归并不出错、能解释每个优化点的来龙去脉。

1. 按"数据是怎么移动的"把十个算法分成五族

大多数人记排序算法是靠口诀硬背，背完就忘。我自己的经验是，先记住"数据在数组里是怎么挪位置的"，剩下的一切都能推出来。这一层想通了，复杂度、稳定性、适用场景基本都是自然结论，不需要单独背。

1.1 五族分类：交换、插入、选择、分治、桶

• 交换族：冒泡排序、快速排序。核心动作是把两个元素对调，直到所有逆序对消失。冒泡是"相邻交换"，快排是"远距离交换"——这个差别直接决定了两者一个是 O(n²)，一个是 O(n log n)。
• 插入族：直接插入排序、希尔排序。核心动作是把一个元素插到前面已经有序的序列里合适的位置。希尔排序就是"带步长的插入排序"，先让远距离的元素有序，减少后面的搬移量。
• 选择族：简单选择排序、堆排序。核心动作是每一轮从待排区域里挑出最值放到已排区域的末端。堆排序之所以快，是因为它用堆结构把"挑最值"从 O(n) 降到了 O(log n)。
• 分治族：归并排序。核心动作是先切半、各自排好、再合并。它的"贵"在于要额外空间，"稳"在于合并过程天然稳定。
• 桶族：计数排序、桶排序、基数排序。这三个是不比较元素大小的排序，靠"把元素丢进对应的桶"完成。它们的下限能突破 O(n log n)，代价是对数据分布有要求。

把这五族记住，你会发现面试官问"快排和归并的区别"，本质上是在问"交换族和分治族的取舍"；问"堆排序和选择排序的关系"，就是在问"选择族里 O(n) 挑选怎么变成 O(log n)"。用族的概念去组织记忆，比零散地背十个算法牢固得多。

1.2 十大排序算法速查表

下面这张表我建议直接抄进笔记首页，它是所有讨论的起点。表里的平均时间复杂度、最坏情况、空间、稳定性四项，是选型时最先看的指标。

表里有几个容易被忽略的细节，值得单独拎出来说。快排的空间复杂度不是 O(1)，虽然它没有额外开数组，但递归调用栈要占 O(log n)，最坏情况下递归深度到 n，栈空间就是 O(n)。希尔排序的最好情况是 O(n)，因为当数组已经基本有序时，插入排序本身就接近线性。桶排序的最坏情况是 O(n²)，这个反直觉——如果有人故意把数据全塞进同一个桶，那就退化成了桶内做插入排序，等于什么都没优化。

1.3 稳定性不是学术概念，它会实实在在咬你一口

稳定性的定义是：对于值相等的两个元素，排序后它们的相对次序保持不变。为什么这件事重要？举个最常见的业务场景——电商列表先按销量降序排，再按价格升序排。如果用的是不稳定的排序，第二次排序会把第一次排好的销量顺序打乱，结果就是同价格的商品销量顺序乱了。用稳定排序就不会有这个问题，因为价格相同的元素会保留上一轮的销量顺序。

再比如 Python 里对一组元组排序，sorted(data, key=lambda x: x[2])，Python 用的是 TimSort（归并+插入的混合算法），是稳定排序，所以相同 key 的记录会保持原有顺序。这个特性在数据处理里非常有用，等于免费拿到"多级排序"的能力。反过来，Java 的Arrays.sort(int[])用的是双轴快速排序，不稳定；而Arrays.sort(Object[])用的是 TimSort，稳定。同一门语言里两套策略，背后的考量就是：基本类型不需要区分"相等的两个 3"，而对象可能需要。顺着这个思路去理解为什么要分成两套实现，比死记结论强。

2. 冒泡、选择、插入：入门三件套的真实差距

这三个算法代码最短，但恰恰是被讲得最浅的。很多人的笔记里，三者的区别只有"复杂度一样、写法不同"。实际上它们的常数因子、对数据初始状态的敏感度、以及能不能在线处理，差别非常大。

2.1 冒泡排序：提前退出优化才是它唯一的价值

冒泡排序的算法思想很直观：每一轮从头到尾比较相邻两个元素，逆序就交换，一轮下来最大的元素就"冒"到了末尾。如果写成硬循环，它永远是 O(n²)，没有任何亮点。真正值得学的是那个提前退出的优化。

def bubble_sort(a): n = len(a) for i in range(n - 1): swapped = False for j in range(n - 1 - i): if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] swapped = True if not swapped: # 这一轮没有任何交换，说明已经有序 break return a

加上swapped标记之后，对已经有序的数组，冒泡排序只需要跑一轮就能退出，时间复杂度降到 O(n)。这里有个细节很多人会写错：swapped必须定义在外层循环内部，每轮重置一次；如果定义在外面，第二轮之后就再也不会为真，提前退出会失效。

还有一个更进一步的优化思路：记录每一轮最后一次交换发生的位置，因为这个位置之后的元素已经有序了，下一轮只需要扫到这个位置就行。不过说实话，冒泡排序交换次数等于数组的逆序对数量，这个性质在统计"数据有多乱"时挺有用，但拿它来实际排序，性能上真的没有竞争力。我个人的态度是：冒泡排序是用来理解排序的教具，写业务代码时不要用它。

2.2 选择排序：为什么它天生不稳定

选择排序的思路是：每一轮在未排序区间里找最小值，和未排序区间的第一个元素交换。找最小值是 O(n)，做 n 轮，所以无论如何都是 O(n²)，最好最坏都一样，不受数据初始状态影响。代码大概是这样：

public static void selectionSort(int[] a) { int n = a.length; for (int i = 0; i < n - 1; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[minIdx]) { minIdx = j; } } if (minIdx != i) { int t = a[i]; a[i] = a[minIdx]; a[minIdx] = t; } } }

它不稳定的原因就藏在"交换"这个动作里。举个例子，数组是[5, 5, 2]，第一轮找到的最小值是 2，位置在索引 2，把它和索引 0 的 5 交换，数组变成[2, 5, 5]——原来的第一个 5 跑到后面去了，两个 5 的相对顺序变了。同样是 O(n²)，插入排序稳定而选择排序不稳定，差别就在于插入排序用的是"逐个后移"，后移不会改变相等元素的相对位置。

选择排序唯一的优势是交换次数最少，最多交换 n-1 次。如果排序对象的交换成本极高（比如大结构体），选择排序有它的用武之地。但这种场景现在基本被指针排序覆盖了，所以它的实际用途也很有限。

2.3 插入排序：小数组里的隐形冠军

插入排序的思路是把手里的牌一张张插到合适位置。它的复杂度分析特别有意思：元素如果离它最终位置很近，搬移量就小。数组越接近有序，插入排序越快，完全有序时它是 O(n)。

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

注意while里用的是a[j] > key而不是>=，这个符号直接决定了稳定性：用>时，相等的元素不会被搬走，插入到相等元素后面，保持稳定；用>=就会把相等元素往前插，破坏稳定性。这是个很小的细节，但面试里被问"你怎么保证插入排序是稳定的"，答案就是这个比较符号。

插入排序真正重要的地位在于，它是所有工业级排序算法的收尾选手。Python 的 TimSort、Java 的 TimSort、C++ 的 introsort，在数组被切到很小（通常是 16 到 32 个元素）之后，都会切换成插入排序。原因是插入排序常数项小，没有函数调用开销，对小数组比快速排序还快。这个阈值不是随便定的，常见取值是 16，可以在 JDK 源码里看到INSERTION_SORT_THRESHOLD = 32这样的常量。理解这一点，比单纯记住"插入排序是 O(n²)"有价值得多——在真实工程里，插入排序每天都在被高频调用。

3. 希尔与归并：两条跳出 O(n²) 的路

从这一节开始，我们进入真正有工程价值的算法。希尔排序是"插入排序的加强版"，归并排序是"分治思想的代表作"，它们代表了两种完全不同的破局思路。

3.1 希尔排序：给插入排序装上一个放大镜

插入排序慢在哪？慢在每次只能挪一格，如果一个小元素在数组末尾，它要挪 n 步才能到前面。希尔排序的想法就是：先用一个大的步长gap把元素分成若干组，组内做插入排序，让小的元素能跨大步往前走；然后逐步缩小 gap，最后 gap=1 时做一次普通插入排序。因为此时数组已经"基本有序"了，最后这一趟会非常快。

文字图解一下对[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]走 gap=5 的过程：

分组（下标相差 5 的在一组）: 组1: 8, 3 -> 3, 8 组2: 9, 5 -> 5, 9 组3: 1, 4 -> 1, 4 组4: 7, 6 -> 6, 7 组5: 2, 0 -> 0, 2 一轮后: [3, 5, 1, 6, 0, 8, 9, 4, 7, 2] 可以看到最小的 0 已经从末尾跑到第 5 位，一步跨了 5 格。

def shell_sort(a): n = len(a) gap = 1 while gap < n // 3: # Knuth 增量序列: 1, 4, 13, 40, ... gap = gap * 3 + 1 while gap >= 1: for i in range(gap, n): key = a[i] j = i - gap while j >= 0 and a[j] > key: a[j + gap] = a[j] j -= gap a[j + gap] = key gap //= 3 return a

增量序列的选择直接决定性能。经典的希尔增量n/2, n/4, ..., 1最坏能退化到 O(n²)；Knuth 的3h+1序列可以把平均复杂度压到 O(n^1.5) 左右；还有更激进的 Sedgewick 序列，能把最坏情况压到 O(n^(4/3))。我在笔记里习惯把希尔排序的复杂度写成"约 O(n^1.3)，取决于增量序列"，因为给一个确定的数字是不严谨的。

希尔排序不稳定，原因和插入排序一样——它是跨步长移动的，两个相等的元素可能因为分在不同的组里被调换顺序。这一点在面试里经常被追问，值得记住。

3.2 归并排序：先切再合，合并是灵魂

归并排序的分治三部曲：分解——把数组从中间切成两半；解决——递归地对两半分别排序；合并——把两个有序数组合并成一个有序数组。前两步是递归框架，真正干活的是第三步。

合并两个有序数组的过程，用文字图解最清楚。假设左半是[1, 5, 9]，右半是[2, 6, 7]：

i=0(指1) j=0(指2) 结果[] 比较 1 < 2 -> 取 1, i 后移 结果[1] 比较 5 > 2 -> 取 2, j 后移 结果[1,2] 比较 5 < 6 -> 取 5, i 后移 结果[1,2,5] 比较 9 > 6 -> 取 6, j 后移 结果[1,2,5,6] 比较 9 > 7 -> 取 7, j 后移 结果[1,2,5,6,7] 右边耗尽, 左半剩余整体接上 结果[1,2,5,6,7,9]

def merge_sort(a): if len(a) <= 1: return a mid = len(a) // 2 left = merge_sort(a[:mid]) right = merge_sort(a[mid:]) return merge(left, right) def merge(left, right): res = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: # 取等号时优先左边, 保证稳定性 res.append(left[i]) i += 1 else: res.append(right[j]) j += 1 res.extend(left[i:]) res.extend(right[j:]) return res

合并时left[i] <= right[j]里的等号是稳定性的关键：当两边元素相等时优先取左边的，左边本来就在前面，相对顺序得以保持。如果把等号去掉写成<，右半相等元素就会抢先，稳定性就没了。这个细节在很多教程里被省略，但恰恰是面试的常考点。

3.3 归并的空间换时间和它在链表、外部排序里的独特地位

归并排序的代价很直白：每次合并都要开一个临时数组，空间 O(n)。这是它输给快排的主要原因。但它在两个场景里无可替代。

第一个场景是链表排序。数组的归并需要额外空间，因为合并时要同时保存两段数据；而链表的节点可以随时改指针，合并两个有序链表只需要 O(1) 的额外空间，直接原地串起来就行。所以LeetCode 148. 排序链表的标准解法就是归并排序，快排反而不好写——链表没有随机访问，快排找基准和分区的效率都很差。

第二个场景是外部排序。当数据大到内存放不下时，思路是：把大文件切成若干能塞进内存的块，每块内部排序后写回磁盘，得到若干个有序的小文件；然后再用多路归并把它们合并成一个大文件。整个流程的核心就是归并，这是数据库和大数据处理里的基础操作。理解了这一层，你就能明白为什么归并排序在数据量超过内存的场景下依然不可替代。

还有一点值得提：归并排序是唯一一个稳定且最坏情况也是 O(n log n)的比较类排序。快排最坏是 O(n²)，堆排序不稳定，计数类排序有适用范围。要求"稳定 + 最坏 O(n log n) + 不挑数据"，只有归并满足。Java 里对对象排序用 TimSort 而不是快排，本质就是这个考量。

4. 快速排序：被用得最多，也被问得最细

快排是十个算法里被问得最多的一个，因为它的工程实践最复杂：分区怎么写、基准怎么取、重复元素怎么处理、什么时候会退化，每一个点都能展开讲半小时。它也是我见过的"代码看起来对、实际有 bug"发生率最高的算法。

4.1 分区的两种写法：挖坑法和双指针

快排的核心是分区（partition）：选一个基准值 pivot，把数组分成"左边全小于等于 pivot、右边全大于等于 pivot"两部分，然后对两部分递归。

挖坑法的思路是：先把基准值取出来存起来，基准位置就成了第一个"坑"；从右边找一个比基准小的数填进左边的坑，这个数的原位置变成新坑；再从左边找一个比基准大的数填进右边的坑；如此往复，直到左右指针相遇，把基准值填进最后的坑。

public static void quickSort(int[] a, int low, int high) { if (low >= high) return; int pivot = a[low]; // 挖出第一个坑 int i = low, j = high; while (i < j) { while (i < j && a[j] >= pivot) j--; // 从右往左找比基准小的 if (i < j) a[i++] = a[j]; // 填左坑, 右位置成新坑 while (i < j && a[i] <= pivot) i++; // 从左往右找比基准大的 if (i < j) a[j--] = a[i]; // 填右坑 } a[i] = pivot; // 基准归位 quickSort(a, low, i - 1); quickSort(a, i + 1, high); }

这段代码有两个高频错误点，我当年都踩过。第一个是右边先走还是左边先走的问题。用挖坑法且基准取最左边时，必须先动右指针。原因是如果先动左指针，最后相遇的位置可能是一个比基准大的元素，把它和基准交换后，左边就出现了比基准大的值，分区就错了。第二个是内层while里的i < j判断不能省，否则数组里有大量重复元素时指针会越界。

双指针法（也叫前后指针法）是另一种思路：用一个i表示"小于等于基准区域的右边界"，用j从左到右扫描，遇到比基准小的就把它换到i的位置并让i前进。

def partition(a, low, high): pivot = a[high] # 基准取最后 i = low for j in range(low, high): if a[j] < pivot: a[i], a[j] = a[j], a[i] i += 1 a[i], a[high] = a[high], a[i] return i

双指针法代码更短、边界更少、不容易写错，我个人更推荐这个版本作为手写模板。注意它用的是a[j] < pivot而不是<=，用<能让等于基准的元素留在右边，配合最后把基准换到中间，可以避免一部分极端情况。

4.2 基准选择、小区间优化和三路快排

基准选择决定了快排的下限。取第一个元素或最后一个元素为基准，代码最省事，但遇到已经有序的数组会立刻退化。取中间元素稍好一些，但也能被构造出退化用例。工业界的标准做法是三数取中：取low、mid、high三个位置的中位数作为基准。

def median_of_three(a, low, high): mid = low + (high - low) // 2 # 这样写避免 low+high 溢出 if a[low] > a[mid]: a[low], a[mid] = a[mid], a[low] if a[low] > a[high]: a[low], a[high] = a[high], a[low] if a[mid] > a[high]: a[mid], a[high] = a[high], a[mid] a[mid], a[high - 1] = a[high - 1], a[mid] # 把中位数藏到 high-1 位置 return a[high - 1]

这里有个小技巧值得记：把选好的中位数换到high - 1的位置，因为low一定比它小、high一定比它大，后续分区的循环边界就可以直接跳过这两端，减少比较次数。这是《数据结构与算法分析》里推荐的写法。

小区间优化。递归到子数组长度很小的时候，快排的函数调用开销开始超过排序本身的开销。所以标准做法是：当子数组长度小于某个阈值（常见是 16 或 32）时，直接调用插入排序，然后返回。

def quick_sort(a, low, high): while low < high: if high - low + 1 <= 16: insertion_sort_range(a, low, high) return p = partition(a, low, high) quick_sort(a, low, p - 1) low = p + 1 # 尾递归优化: 右半用循环处理, 减小递归深度

注意最后那行low = p + 1。这是尾递归优化：对右半部分不再递归调用，而是用循环继续处理，这样递归深度从最坏的 O(n) 降到了 O(log n) 量级。加上"每次先递归较短的一边"的写法，可以把栈深度稳定压在 O(log n)。这个优化在实际服务里很重要，我见过线上因为快排递归过深导致栈溢出的案例，日志里就是一堆重复的 quickSort 栈帧。

三路快排是为了解决"大量重复元素"这个场景。普通分区遇到一堆相同值时，分区做得极不平衡，可能退化成 O(n²)。三路快排把数组分成< pivot、== pivot、> pivot三段，等于基准的那段直接不用再排了。

def quick_sort_3way(a, low, high): if low >= high: return pivot = a[low] lt, i, gt = low, low + 1, high while i <= gt: if a[i] < pivot: a[lt], a[i] = a[i], a[lt] lt += 1 i += 1 elif a[i] > pivot: a[i], a[gt] = a[gt], a[i] gt -= 1 else: i += 1 quick_sort_3way(a, low, lt - 1) quick_sort_3way(a, gt + 1, high)

具体点说，如果数组是[3,3,3,3,...,3,1]这种形态，两路分区每次只能确定一个元素的位置，要递归 n 次；三路快排一趟就把所有 3 归位到中间，只需要处理那个 1，差距非常明显。这个算法也叫荷兰国旗问题，是算法题里的高频考点。

4.3 快排究竟在什么时候退化成 O(n²)

想清楚这个问题，比背结论重要。快排的复杂度取决于递归树的高度。如果每次分区都能把数组对半分，树高是 log n，每层总比较次数是 n，总复杂度 O(n log n)。如果每次都分成 1 和 n-1，树高就是 n，每层还是 n 次比较，总复杂度 O(n²)。

具体触发退化的场景有两个：一是数据已经有序或逆序，而基准取的是首元素或尾元素；二是数据里有大量重复元素，而用的是两路分区。第一个问题用三数取中或随机化基准解决，第二个问题用三路快排解决。另外还有一个隐蔽的坑：数据是"近似有序"的，比如已经排过一遍、只改了几个元素的数据，如果基准选得不好，也会触发退化。所以我现在写快排的默认配置是"三数取中 + 小区间插入 + 尾递归优化"，这三个加起来基本能挡住绝大多数退化场景。

5. 堆排序与桶族：一个靠结构，一个靠分布

剩下四个算法分两类。堆排序是比较类排序里唯一一个"最坏也是 O(n log n) 且空间 O(1)"的算法，很硬核；计数、桶、基数三个是"非比较排序"，它们能不能用完全取决于数据分布，用对了非常快，用错了比冒泡还惨。

5.1 堆的下标关系和"建堆为什么是 O(n)"

堆排序的基础是完全二叉树的数组表示。下标从 0 开始的话，节点 i 的左孩子是2i+1，右孩子是2i+2，父节点是(i-1)/2。这个映射关系一定要记牢，因为堆排序的代码全是下标运算，写错一个就全乱。

堆排序分两步。第一步建堆，从最后一个非叶子节点（下标n/2 - 1）开始，依次向前对每个节点做"下沉"操作，保证每个节点都不小于它的孩子。第二步排序，反复把堆顶（最大值）和末尾元素交换，然后缩小堆的范围，对堆顶做一次下沉。

public static void heapSort(int[] a) { int n = a.length; for (int i = n / 2 - 1; i >= 0; i--) { siftDown(a, i, n); } for (int i = n - 1; i > 0; i--) { int t = a[0]; a[0] = a[i]; a[i] = t; siftDown(a, 0, i); } } private static void siftDown(int[] a, int i, int size) { while (true) { int l = 2 * i + 1, r = 2 * i + 2, largest = i; if (l < size && a[l] > a[largest]) largest = l; if (r < size && a[r] > a[largest]) largest = r; if (largest == i) break; int t = a[i]; a[i] = a[largest]; a[largest] = t; i = largest; } }

"建堆是 O(n) 而不是 O(n log n)"这个结论经常被误解。每个节点下沉一次看起来最多 log n 步，n 个节点就是 O(n log n)。但真实情况是：越靠近底层的节点越多，而它们的下沉深度越浅。具体说，高度为 h 的节点大约有 n/2^(h+1) 个，每个最多下沉 h 步，把它们乘起来求和，结果收敛到 O(n)。这个推导过程值得自己动手算一遍，算过一次就再也不会忘。相反，如果是从空堆开始逐个插入元素（每次插入是 O(log n)），那才是真的 O(n log n)。

堆排序的工程价值在于：它是唯一没有最坏情况陷阱的原地比较排序。快排怕退化，归并要额外空间，堆排序两样都不怕，代价是常数因子偏大、缓存不友好（访问下标跳跃），实际跑起来常常比快排慢一截。另外，堆结构本身比堆排序更有价值：求 Top K 大元素用大小为 K 的小顶堆，求中位数用一个大顶堆加一个小顶堆，这些都是堆的应用，比手写堆排序要常用得多。

5.2 计数排序：范围小的时候它是降维打击

计数排序的思路是"用值当下标"。先扫一遍数组统计每个值出现的次数，然后按值的顺序把元素填回去。它不做任何比较，所以能突破 O(n log n) 的下限，达到 O(n + k)，k 是值的范围。

def counting_sort(a): if not a: return a lo, hi = min(a), max(a) size = hi - lo + 1 count = [0] * size for x in a: count[x - lo] += 1 for i in range(1, size): # 前缀和, 变成"最后一个位置" count[i] += count[i - 1] res = [0] * len(a) for x in reversed(a): # 倒序遍历, 保证稳定性 count[x - lo] -= 1 res[count[x - lo]] = x return res

代码里有三个容易错的地方。第一，偏移量的处理：数组里可能有负数，直接用值当下标会崩，所以统一减去最小值lo做偏移。这个问题在面试里很常见，很多人写完才发现负数处理不了。第二，倒序遍历保证稳定性：填回结果数组时从后往前扫，这样相同值的元素中，原数组里靠后的会放在后面，相对顺序保持不变。如果正序遍历，稳定性就没了。第三，空间是 O(k) 不是 O(n)，当值域 k 远大于 n 时，比如数组里只有 10 个数但是最大值是 10 亿，直接开 10 亿的数组显然不行。

所以计数排序的适用条件很明确：数据范围小且相对集中。比如统计考试成绩（0 到 100）、统计年龄（0 到 150）、统计某个区间内的整数，这种场景用计数排序比快排快一个数量级。值域大就不合适了，得换基数排序。

5.3 基数排序与桶排序：从低位到高位的分配收集

基数排序解决的就是"值域太大"的问题。它不直接按整个值排序，而是按每一位来排：先按个位排，再按十位排，再按百位排，直到最高位。因为每一轮用的都是稳定排序（通常是计数排序），所以低位排好的顺序会被高位保留，最终结果是正确的。

原始: [170, 45, 75, 90, 802, 24, 2, 66] 按个位分桶: 桶0: 170, 90 桶2: 802, 2 桶4: 24 桶5: 45, 75 桶6: 66 收集后: [170, 90, 802, 2, 24, 45, 75, 66] 按十位分桶: 桶0: 802, 2 桶4: 45 桶6: 66 桶7: 170, 75 桶9: 90 收集后: [802, 2, 24, 45, 66, 170, 75, 90] 按百位分桶: 桶0: 2, 24, 45, 66, 75, 90 桶1: 170 桶8: 802 收集后: [2, 24, 45, 66, 75, 90, 170, 802]

def radix_sort(a): if not a: return a max_val = max(a) exp = 1 while max_val // exp > 0: buckets = [[] for _ in range(10)] for x in a: buckets[(x // exp) % 10].append(x) a = [x for b in buckets for x in b] exp *= 10 return a

基数排序的稳定性要求是刚性的。因为低位排序的结果必须被保留，如果某一位的排序不稳定，前面几轮的工作就全白做了。它用的是 LSD（从低位到高位）方案，适合整数和定长字符串。复杂度 O(d(n+k))，d 是最大值的位数。

桶排序的思路介于归并和计数之间：按值域把数据分成若干个区间（桶），每个桶内部再用其他排序算法排，最后把桶按顺序拼起来。它的性能对数据分布极度敏感——数据均匀分布时每桶元素数量接近，复杂度接近 O(n)；数据全挤在一个桶里，就退化成桶内排序的复杂度，最坏 O(n²)。现实中桶排序用得不多，主要是它需要事先知道数据的分布，但基数排序可以看成桶排序的特例（桶的数量固定为 10，按位分配），理解了这层关系，两者的边界就清楚了。

6. 工程选型：把算法用对，比会写更重要

到这十个算法都讲完了，但真正的难点在于"什么场景用哪个"。我在实际项目里见过的排序相关性能问题，九成不是算法写错了，而是选错了。

6.1 主流语言内置排序用的都是混合算法

不要自己手写排序去处理业务数据，这是第一条经验。各大语言的标准库已经把混合算法的优势发挥到极致：

这里面的设计思路很值得琢磨。TimSort 的核心洞察是"真实数据往往已经部分有序"，它会先在数组里找连续递增或严格递减的段（叫 run），把递减段直接反转，然后用归并的方式把各个 run 合起来。对部分有序的真实数据，它比纯快排快很多。而introsort 的核心是"防退化"：先用快排，当递归深度超过2 * log n时自动切换成堆排序，避免最坏情况；小区间再切换成插入排序。三个算法各管一段，这才是工程级的答案。

6.2 手写排序时的高频坑清单

即便是为了面试或笔记手写，也有几个坑必须提前知道。我把它们在下面列全，这些都是我在实际调试中踩过的：

• mid的计算要防溢出。(low + high) / 2在 low 和 high 都很大时会溢出成负数，正确写法是low + (high - low) / 2。这个坑在归并排序和快排里都要注意。
• 递归的终止条件写错。快排里写if (low >= high) return;而不是if (low == high)，因为 low 有可能大于 high（空区间）。用>=更安全。
• 快排的左右先后顺序。挖坑法配最左基准时必须先动右指针，这一点前面强调过，是最高频的错误。
• 归并排序的临时数组反复创建。递归里每次都new int[n]会造成大量 GC 压力，正确做法是在递归外面创建一个和原数组等大的临时数组，通过参数传进去复用。
• 稳定性相关的比较符号。插入排序用a[j] > key，归并合并用left[i] <= right[j]，这两处符号写反就会破坏稳定性，而且排序结果看起来还是"对的"，极难发现。
• 要排序的是对象数组还是基本类型。如果排序的是自定义对象，一定要明确是否需要稳定排序，需要就用归并或者想办法把比较键扩展成"多级 key"，别指望不稳定的快排。

6.3 从排序延伸出去的几个高频考点

排序是很多算法的地基，往下延伸能牵出一串高频问题，这也是我建议把排序学扎实的原因。

求第 K 大元素用快排的分区思想，不需要完整排序。每次分区后看基准的位置 p：如果 p 正好是 K-1，答案就是它；如果 p 比 K-1 大，就在左半找；否则在右半找。平均复杂度 O(n)，这叫快速选择算法。

**求最大的 K 个元素（Top K）**用大小为 K 的小顶堆。遍历数组，堆不满就插入，堆满后比较堆顶，比堆顶大就替换堆顶再下沉。总复杂度 O(n log K)，比完整排序 O(n log n) 快，尤其在 n 很大 K 很小的时候优势明显。这个模式在处理海量日志、排行榜时非常常用。

统计逆序对数量用归并排序。在合并两个有序段时，如果右半的元素先被取出，说明它比左半剩下的所有元素都小，此时左半剩余元素个数就是这批逆序对的数量。这个技巧只在归并的合并步骤里加两行代码，非常巧妙。

外部排序前面提过，核心是多路归并，是处理超大数据集的基础套路。

我在实际使用中的体会是，这十个算法的真正价值不在于"能默写出来"，而在于它们提供了五套不同的思维工具：交换的思维、插入的思维、选择的思维、分治的思维、按分布组织的思维。后面遇到的很多问题，比如调度、聚合、去重，本质上都能映射回某一个排序的思路上去。最后分享一个练习方法：拿同一组十万条随机数据，把这十个算法都跑一遍并打印耗时，再换成"已经基本有序"和"大量重复"两种数据各跑一遍，你会对每一栏参数产生实感，这比看十遍表格都管用。