企业官网建设流程全解析

如果让我列一份程序员最熟悉的陌生算法清单，排序绝对排第一。你会调Arrays.sort，能背出冒泡和快排的流程，但一旦真让你在白板上把八大排序一个一个写出来，很多人当场就会露馅——快排分区写成死循环、归并的临时数组开错位置、稳定的排序被写得不稳定、有序数组直接让快排退化成平方级。八大排序这个题目，看起来是面试八股，实际上是把递归、分治、数据结构、复杂度推导和工程取舍一次性全考一遍，这也是为什么它永远出现在面试题和算法课里。

这篇文章我打算从实现角度把八大排序逐个拆开，用 Java 给出可以直接跑的版本，把每个算法的复杂度来源讲清楚，再补一张直观的对比表和一组工程选型建议，最后聊聊我自己手写排序时踩过的坑。你如果正在准备算法面试，或者被要求手写排序但心里没底，这篇应该能帮你把"背代码"变成"真的懂"。

1. 八大排序是哪八个，以及理解它们的三把尺子

1.1 这八个成员都是谁

八大排序并不是按同一流派统一归纳出来的组合，它是面试、算法课和工程实践中高频出现的一集散装算法：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序。

这八个算法覆盖了完全不同的三种思路：前三个是朴素的"比较 + 交换/移动"，靠两两比较逐步把序列排好；希尔是插入排序的进阶版，通过大步长分组让序列先接近有序；归并、快排、堆是分治思想或堆数据结构在排序上的典型应用；计数排序则彻底跳出"比较"的框架，直接统计值出现的次数。

把这八个混在一起学容易乱，但只要你抓住每类算法"解决什么问题、用什么代价解决"，它们之间的关系就清楚了。这也是我下面第 2 章要做的分档。

1.2 评价排序算法的三把尺子

任何排序算法，工程上就看三个维度。

时间复杂度：算法在大规模数据下跑得快不快，通常看平均复杂度和最坏复杂度。比如快排平均 O(n log n)，但最坏会退化到 O(n²)，这是选型时必须知道的隐患。

空间复杂度：排序过程额外占多少内存。原地排序（比如快排、堆排）几乎不占额外空间，归并排序每次要开一块长度等同于区间的临时数组，处理海量数据时内存开销不可忽略。

稳定性：如果两个相等元素在排序后保持原有先后顺序，这个排序就是稳定的。很多人觉得稳定性没卵用，但等你做多关键字排序的时候就会发现，不稳定算法会在你完全没意识到的情况下打乱之前排好的顺序。这一点我在第 4 章专门展开。

这三把尺子，对应你到底该在什么场景用哪种排序。背下所有实现不代表会选型，但理解这三个维度之后，选型就是自然的事。

2. 先按复杂度把八大排序分成三档，思路就顺了

抛开具体代码不谈，八大排序的复杂度分布在三个层级上，按层级学习会比逐个死记高效得多。

2.1 O(n²) 档：冒泡、选择、插入

这三个算法都是两重循环的"老实人"，平均复杂度 O(n²)，适合小规模数据和教学入门。

冒泡的价值在于它是"相邻比较"最直观的写法，而且带提前终止优化后，对基本有序的数组能降到 O(n)。选择的特殊点在于它的交换次数是所有排序中最少的——无论如何，最多交换 n-1 次就能把整个数组排好，写起来也最不容易出错。

插入排序则是三个里面工程价值最高的。它实现简单、常数极小，对近乎有序的数组可以跑到 O(n)，所以 Timsort 和 JDK 的对象排序里，对小规模子序列用的就是插入排序。很多新手低估它，实际上它是 O(n²) 档里唯一值得在正式代码里出现的算法。

2.2 希尔排序的位置有点特殊

希尔排序是插入排序的升级版：先按大步长分组做插入排序，不断缩小步长，最后一趟步长为 1 时整个数组已经接近有序，插入排序退化为近乎 O(n)。

理论上它没有稳定地进入 O(n log n) 档，平均复杂度取决于步长序列的选择，常见实现约在 O(n^1.3) 左右。它属于"比 O(n²) 快一截、但很难说清确切复杂度"的中间派。考虑到它代码量只比插入排序多一层循环，实战里想原地排序又不想写归并的时候，希尔是个不错的折中。

2.3 O(n log n) 档：归并、快排、堆

这是工业界的绝对主角，三种算法都能达到 O(n log n)，但性格完全不同。

归并排序稳定、复杂度恒定，代价是额外 O(n) 空间，实现是典型的分治流程。它对链表尤其友好——链表归并不需要额外空间，只要调整指针。

快排是综合常数最小的原地排序，JDK 对基本类型的排序就是基于快排（双轴快排），但它最怕有序数组和固定选 pivot 的组合，会退化到 O(n²)。

堆排序用最大堆的堆顶必然是最大值这一点，每次把堆顶挪到末尾，最坏也是 O(n log n) 且原地，但常数偏大，实际速度通常不如快排。

我自己的经验是：三个 O(n log n) 里最需要手写熟练的是快排和归并，因为它们的分治模板在其它算法题里也大量复用，堆排序更多考察你对堆这个数据结构的理解。

2.4 计数排序：跳出"比较"框架的另类

计数排序的时间是 O(n+k)，k 是数据范围，它压根不比较元素大小，而是把每个值出现的次数统计到数组里，再按次数回填。正因为不做比较，它突破了"比较排序最好 O(n log n)"的下界。

当然它有前置条件：数据必须是有确定范围、比较密集的整数。你给一组小数或者范围大到 2^31 的数据，计数排序立刻原地爆炸。它更大的意义是作为基数排序的地基。

3. 逐个手写实现：代码、复杂度推导和易错点都放在这

下面按从简单到复杂的顺序给实现。所有代码我都是用 Java 写的，用其它语言也完全能对上思路。

3.1 冒泡与选择：两种"老实人"写法

冒泡排序的代码非常好懂：

public static void bubbleSort(int[] a) { for (int i = 0; i < a.length - 1; i++) { boolean swapped = false; for (int j = 0; j < a.length - 1 - i; j++) { if (a[j] > a[j + 1]) { swap(a, j, j + 1); swapped = true; } } if (!swapped) break; // 这一轮没交换，说明已经有序 } }

复杂度推导很简单：最外层跑 n-1 轮，第 i 轮内层比较 n-1-i 次，总比较次数约 n(n-1)/2，所以平均和最坏都是 O(n²)。加了swapped提前中断后，输入已经有序时外层只跑一轮，最好变成 O(n)。

注意两个细节：相等时不要交换，否则稳定被破坏；内层循环的i是已经冒到末尾的元素个数，j的上限要减掉它。

选择排序则是每轮找到剩下部分的最小值，放到当前位置：

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

它的复杂度是严格的 O(n²)，因为无论输入是否有序，内层比较一次都不能省。但它的交换次数不多于 n-1 次，适合"交换成本远高于比较成本"的极端场景。

选择排序为什么不稳定？举个例子：[5a, 5b, 1]，第一轮找到最小值 1，和位置 0 的 5a 交换，5a 就跑到 5b 后面去了。这个例子我在面试里被问到过，希望你也记住。

3.2 插入与希尔：从局部有序到大步逼近

插入排序的核心思想跟打扑克理牌完全一样——把新摸到的牌，插到手里已经排好序的牌里。

public static void insertionSort(int[] a) { for (int i = 1; i < a.length; i++) { int cur = a[i]; int j = i - 1; while (j >= 0 && a[j] > cur) { a[j + 1] = a[j]; j--; } a[j + 1] = cur; } }

每次把cur前面的元素逐个右移，找到它的正确位置放回去。最好情况是数组已经有序，while 循环一次都不进，整体只有一层循环，复杂度 O(n)。最坏和平均都是 O(n²)。

实现时最容易犯的错是把a[j] > cur写成a[j] >= cur。后者会让相等元素也产生移动，破坏稳定性。另外j >= 0和a[j] > cur的顺序不能反过来，否则 j 已经变成 -1 时会抛数组越界。

希尔排序就是在插入排序外套一层递减的 gap：

public static void shellSort(int[] a) { for (int gap = a.length / 2; gap >= 1; gap /= 2) { for (int i = gap; i < a.length; i++) { int cur = a[i]; int j = i - gap; while (j >= 0 && a[j] > cur) { a[j + gap] = a[j]; j -= gap; } a[j + gap] = cur; } } }

gap 从 n/2 开始每次减半，每一轮把相距 gap 的元素看作一组做插入排序。因为插入排序对"接近有序"的序列很快，希尔就是先通过大步长让序列快速趋向有序，最后一轮 gap=1 时已经省了大量移动。

希尔的不稳定性来自分组：两个相等的 key 可能被分到不同的 gap 组里，跨越多个位置交换，相对顺序就没法保证。复杂度推导比较麻烦，常见实现约在 O(n^1.3) 附近，不同的 gap 序列会产生不同的复杂度表现。

3.3 归并与快排：分而治之的两条路线

归并排序的分治逻辑很干净：先让左半边有序，再让右半边有序，最后两个有序子序列合并成一个。递归终止条件是区间只剩一个元素。

public static void mergeSort(int[] a, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(a, left, mid); mergeSort(a, mid + 1, right); merge(a, left, mid, right); } private static void merge(int[] a, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { temp[k++] = a[i] <= a[j] ? a[i++] : a[j++]; } while (i <= mid) temp[k++] = a[i++]; while (j <= right) temp[k++] = a[j++]; System.arraycopy(temp, 0, a, left, temp.length); }

复杂度推导：每次对半分，递归深度是 log n 层，每层合并的总代价是 O(n)，所以总时间是 O(n log n)，最好最坏都一样。空间复杂度是 O(n)，因为每层合并都需要临时数组存放有序结果。

注意int mid = left + (right - left) / 2而不是(left + right) / 2，后者在 left 和 right 都很大的时候可能溢出。这块代码我在第 6 章还会提到它的一个性能坑。

快速排序则是另一个思路：先选一个 pivot，把小于 pivot 的元素放到它左边、大于的放右边，这样 pivot 在本次分区后位置就固定了，再递归排两侧。

public static void quickSort(int[] a, int left, int right) { if (left >= right) return; int idx = partition(a, left, right); quickSort(a, left, idx - 1); quickSort(a, idx + 1, right); } private static int partition(int[] a, int left, int right) { int pivot = a[right]; int i = left; for (int j = left; j < right; j++) { if (a[j] < pivot) { swap(a, i, j); i++; } } swap(a, i, right); return i; }

partition 的逻辑是：用i记录"小于 pivot 的元素应该放到的位置"，遍历j，发现a[j]小于 pivot 就把它换到 i 位置并 i++。最后把 pivot 从 right 换到 i，i 就是 pivot 的最终位置，同时也是左右分区的分界线。

复杂度上，理想情况每次对半分，递归 log n 层，每层遍历 n 个元素，平均 O(n log n)。最坏情况比如数组已经有序且每次都选最后一个元素当 pivot，每次分区只能消掉一个元素，递归深度变成 n，总时间退化 O(n²)。

快排的不稳定性来自交换跨越：相等的元素在分区时可能被 swap 到另一个相等元素后面，相对顺序无法保留。这些内容我在避坑章节还会再展开。

3.4 堆排序：用堆这个数据结构换来的 O(n log n)

堆排序的思路浓缩成一句：同一个数组，先把它整理成一个大顶堆，然后每次把堆顶（也就是当前最大值）和数组末尾交换，再把剩余部分重新调整成堆。每轮确定一个最大值到末尾，n 轮搞定。

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--) { swap(a, 0, i); siftDown(a, 0, i); } } private static void siftDown(int[] a, int i, int n) { while (i < n / 2) { int child = 2 * i + 1; if (child + 1 < n && a[child + 1] > a[child]) child++; if (a[child] <= a[i]) break; swap(a, i, child); i = child; } }

n / 2 - 1是最后一个非叶子节点的下标，从它开始往前逐个 siftDown，才能在 O(n) 时间里完成建堆。这个 O(n) 很多人不理解：直觉以为每次 siftDown 是 O(log n)，n/2 个节点是 O(n log n)，但叶子更多、非叶子更少，且越靠近堆顶节点越少，算总账后是 O(n)。后面每轮交换堆顶和末尾，再对堆顶 siftDown 一次是 O(log n)，n-1 轮加起来 O(n log n)，所以整体 O(n log n)。

空间上完全原地，只有递归/循环里的常数开销，这是它和归并本质的区别。

堆排序不稳定很好解释：堆顶元素会与数组末尾元素交换，这个"远距离交换"会把相等元素的相对顺序打乱。比如两个相等的最大值，一个在堆顶一个在堆里，堆顶先被换到末尾，另一个后来才被换到它前面。

3.5 计数排序：跳出"比较"框架的另类

计数排序用一句话说就是：先数出每个值出现了多少次，再根据次数把值填回数组。

public static void countingSort(int[] a) { int min = a[0], max = a[0]; for (int v : a) { if (v < min) min = v; if (v > max) max = v; } int[] count = new int[max - min + 1]; for (int v : a) count[v - min]++; for (int i = 1; i < count.length; i++) count[i] += count[i - 1]; int[] temp = new int[a.length]; for (int i = a.length - 1; i >= 0; i--) { temp[--count[a[i] - min]] = a[i]; } System.arraycopy(temp, 0, a, 0, a.length); }

这个版本做了两件事：第一，偏移处理——用min把数据映射到从 0 开始的下标，所以支持负数，也不浪费太长的数组；第二，前缀和保证稳定——count做完前缀和后，count[v - min]表示"小于等于 v 的元素有多少个"，从后往前填是为了让相同值的元素按原顺序填入最终位置，这样计数排序就是稳定的。

复杂度上，找最值 O(n)，统计 O(n)，前缀和 O(k)，回填 O(n)，总时间 O(n+k)。空间用了count和temp两个数组，O(n+k)。

如果你不需要稳定，可以直接遍历 count 数组覆盖回原数组，空间能省掉 temp。但既然计数排序常用的地方是基数排序的底层，稳定版本更有用，所以这里给的是稳定版实现。

4. 稳定性：排序算法里最容易被低估、却在业务里最致命的一环

4.1 什么是稳定排序

稳定性说的是：两个相等的元素，排序前 a 在 b 前面，排序后如果 a 仍然在 b 前面，这个排序就是稳定的；如果位置反了就是不稳定的。

注意，稳定的定义只针对相等元素，不相等元素的顺序本来就要改变，跟稳定性无关。

为什么要关心这个？最常见的场景是多关键字排序。比如系统里订单列表，业务方要求"先按创建时间升序，同一时间内再按订单金额降序"。你的自然做法是先按金额排序，再按时间排序。如果第二步按时间排序用的是不稳定算法，那么同一时间里的订单金额顺序就被打乱了，结果跟着错。这就是"上一个排序的结果被下一个不稳定排序破坏"的典型踩坑现场。

4.2 八大排序稳定性一览

我把八大排序的稳定性整理一下：

十个字总结：稳的是冒泡、插入、归并、计数；不稳的是选择、希尔、快排、堆。

这里有个面试常考点：归并排序为什么稳定？因为在合并时，如果左右两边的元素相等，我们总是先拿左边的，所以相等元素的相对顺序被保留。代码里那句a[i] <= a[j] ? a[i++] : a[j++]就是稳定的关键——用<=而不是<。

4.3 一个会真实发生的业务事故

我记得有次做一个对账报表，线上导出数据后用户反馈"同一天的记录顺序和页面上不一致"。排查到最后，发现是同事在组装报表时用了快排做二次排序，而它把之前按时间排好的顺序打乱了。

这类 bug 非常隐蔽，因为它不是崩溃，也不是数据错误，而是"顺序看起来不对"。如果刚好遇上需要严格顺序的导出场景（比如银行流水、批次对账、按时间追溯），一次不稳定排序足以让整份报表返工。从那之后我写排序代码，第一反应就是确认这个问题：要不要稳定？要稳定就选归并，或直接给对象加一个序号字段做 tie breaker。

5. 一张总表加一个选型思路：别背"快排最快"这种口诀

5.1 八大排序全参数对比

把第 3 章的复杂度推导汇总成一张表，方便你面试前快速过：

几个容易记错的点：快排空间复杂度是递归栈的 O(log n)，不是 O(1)；希尔最坏复杂度不固定，取决于 gap 序列；计数排序空间如果只要稳定版就是 O(n+k)，纯遍历覆盖可以只留 O(k)。

5.2 选型准则

按工程经验，我会按下面几条走，基本已经覆盖绝大多数场景。

数据量很小（几十个以内）：直接插入排序。代码最短、常数最小，快排这种带递归调度的算法在小数据上反而吃亏。

数据接近有序：插入排序，它能在 O(n) 里完成，其它 O(n log n) 算法在这种场景下跑不过它。

必须稳定：选归并（对象排序场景通常也是 Timsort 的活）。如果做链表排序，归并更是首选，因为链表归并不需要额外空间。

内存受限：选堆排序或快排。堆排序最坏也是 O(n log n)，但常数大；快排正常更快，但要处理好 pivot 才能避免最坏退化。

数据范围已知且 k 远小于 n：计数排序，比如对 10 万个 0~100 的分数排序，O(n+k) 直接秒杀所有比较排序。

没有特殊要求：直接用 JDK 的Arrays.sort。它对 int 等基本类型用双轴快排，对对象用 TimSort，库函数已经针对各种场景做过深度优化。面试之外，手写排序的机会其实很少，选型的意义更多在于你知道库里在用什么，以及为什么。

6. 手写排序时最容易踩的五个坑

这一章是我实际写代码、看同事代码、帮别人查 bug 过程中踩过和见过的坑，拿出来集中说一遍，省得大家再走弯路。

6.1 快排固定 pivot 遇上有序数组

上面 3.3 的快排实现里，pivot 固定取最后一个元素。数组有序时，每次分区后 pivot 正好是最大值，右侧分不到元素，问题退化成 n + (n-1) + ... 次比较，就是 O(n²)。更糟的是递归深度变成 n，甚至可能栈溢出。

我见过不少人拿这个实现去跑大数据量，结果直接 StackOverflow，还以为是代码写错了。工程上最常见的解法是"三数取中"：取 left、mid、right 三个位置的中位数作为 pivot，这样最坏情况基本不会出现在现实数据上。也可以用随机 pivot，避免恶意构造有序序列。

面试时如果你把这个优化说出来，含金量会明显高于只写一个基础 partition。

6.2 归并排序反复 new 临时数组

3.3 的写法里，每次merge都new int[right - left + 1]。从功能上看没有任何问题，但从性能上看，一次排序要创建 O(n log n) 个不同大小的临时数组，GC 压力巨大。数据量到几十万就明显可以看到耗时飙升。

优化是排序开始前一次性创建好一个长度等于原数组的temp，层层传入 merge：

public static void mergeSort(int[] a) { mergeSort(a, new int[a.length], 0, a.length - 1); } private static void mergeSort(int[] a, int[] temp, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(a, temp, left, mid); mergeSort(a, temp, mid + 1, right); merge(a, temp, left, mid, right); }

merge 里不再 new，只往temp里写对应区间。JDK 对象排序的底层也是这个套路，你可以把它当作标准答案。

6.3 堆排序的 siftDown 写错方向

堆排序最容易错的地方是把siftDown（下沉）写成向上冒泡。建堆和堆顶交换后的调整，逻辑都是"从某个节点往下看，把较大的子节点换上来"，方向必须是向下的。我第一次写堆排序时把调整写成 while 向上循环，结果建出来的堆根本不成形，排序结果乱成一团。

另外child + 1 < n && a[child + 1] > a[child]这行的顺序也有讲究：先假设左孩子更大，再看右孩子存不存在且更大，如果存在就切换到右孩子。漏掉child + 1 < n，越界了才知道错。

6.4 计数排序忘了偏移和负数

直接拿数组元素当下标，遇到负数会立刻炸，因为下标不能是负数。遇到最大值特别大的数据，比如 100 万和 100，直接开new int[max]，内存也会被白白浪费一大截。

正确做法是先扫描一遍找 min 和 max，所有下标都减去 min。这样负数变成了非负索引，数组长度也压缩到max - min + 1，两全其美。我在前面 3.5 的实现里已经把这个处理写进去了。

6.5 插入排序的边界和稳定性细节

插入排序里，我见过有人把while (j >= 0 && a[j] > cur)写成while (a[j] > cur && j >= 0)。看起来只是顺序不同，但j减到 -1 时，前者因为短路根本不会执行a[-1]，后者会直接数组越界。

还有一个隐藏细节：>和>=决定了稳定性。用>=，相等元素也会被往右移，新元素会跑到相等元素前面，排序结果就不稳定了。用严格大于>，相等时不动，新元素插入到它们后面，稳定性就保住了。两字符的差别，很多人写完了根本不知道自己写错了排序的稳定性。

最后分享一个个人经验。我以前带一个学弟做导出功能，他图省事把 Redis 里取出来的数据直接用Arrays.sort排了一遍，却忽略了业务要求"先按时间升序、再按优先级降序"的多关键字顺序。Arrays.sort对对象用的是 TimSort，稳定，所以结果碰巧是对的。但如果他换成对基本类型数组排序，或者语言/库的排序不稳定，整份报表顺序就会对不上。从那以后我写任何排序，都会先问三个问题：数据量多大？要不要稳定？键的分布是什么样？这三个问题问完，选型根本不用背口诀。排序这个东西，真正难的从来不是写出来一种，而是知道在哪种场合用哪一种，并且能说出为什么。