企业官网建设流程全解析

当你能不看资料默写这十个算法的C++代码，并且准确说出每个算法的适用场景时，你的算法基础才算真正过关。排序算法是C++学习路上绕不开的第一座山，它既是面试高频考点，也是理解时间复杂度、分治思想、数据结构底层逻辑的最佳切入点。这篇内容我按“原理通俗解释 + 完整C++实现 + 动态过程描述 + 复杂度对比 + 避坑经验”五个维度来拆解十大经典排序算法，适合正在学C++的学生、准备面试的求职者，以及想系统补一补算法基础的开发者。全程没有晦涩的数学推导，但每一行代码都有存在的理由。

1. 正确认识排序算法：它远不止“把数组排好”

1.1 十个算法怎么分类：先建立框架再逐个击破

很多初学者面对“十大排序算法”这个清单时的第一反应是背代码，这是效率最低的学习方式。正确思路是先分类，把十个算法归纳成三组，每组用一条主线串联起来，再逐个击破。

十个经典排序算法按底层思想分成三大类比较清晰：

• 基础比较排序（O(n²)组）：冒泡排序、选择排序、插入排序。这三个算法最简单直观，是大一课程必讲的内容。它们适合小规模数据（比如几千个元素以内），同时也是理解更复杂算法的基础跳板。
• 高效比较排序（O(n log n)组）：希尔排序、归并排序、快速排序、堆排序。这四个是工业界真正会用的算法，其中快速排序的变体是C++标准库std::sort的底层核心，归并排序是外部排序的基石，堆排序则和优先队列直接挂钩。
• 非比较排序（线性组）：计数排序、桶排序、基数排序。这三个算法不靠元素之间的比较来排序，而是利用数据本身的分布特征，在特定条件下能达到惊人的O(n)时间复杂度。

这个分类不是随便分的，它对应着算法设计的一条重要思路：先想清楚“这个问题有什么特殊结构可以利用”，再决定用什么策略。比较排序的下限是O(n log n)，这是信息论决定的——每次比较最多产生两个结果，要区分n个元素的全排列至少需要log₂(n!)次比较。但如果不比较，而是拿着数据的值直接往对应位置放，那就能突破这个下限。

1.2 复杂度与稳定性的底层概念

在逐个看算法之前，有两组概念必须先掰扯清楚，否则后面的代码写出来你也不知道它好在哪里。

时间复杂度：不要死记硬背“平均O(n log n)”这种结论，要理解它的来源。比如快速排序为什么平均是O(n log n)——因为每轮partition把数组分成两半，递归深度是log₂n，每次partition要扫描n个元素，乘起来就是n log n。用大白话讲，n log n意味着数据量翻倍时，耗时只是从10秒变成约20秒（多了一个log因子），而不是变成40秒。

空间复杂度：说的是算法执行过程中额外申请的内存大小，不包含输入数组本身。原地排序（in-place）的空间复杂度是O(1)，意思是不需要和n相关的额外空间。归并排序的空间复杂度是O(n)，因为它需要一个同样大小的临时数组来合并。这一点在实际工程里至关重要，处理上亿条数据时，一个O(n)的额外空间可能就是几百MB内存，不能随便用。

稳定性：这个概念很多初学者会忽略，但面试必考。稳定排序指的是：如果两个元素值相等，排序后它们的相对位置保持不变。比如按成绩排序后，同分的同学之间原来的学号顺序不能乱。为什么要有这个要求？因为现实中我们经常需要对多个字段分别排序，比如先按姓名排，再按成绩排。如果第二次排序是稳定的，那么第一次排序的结果就能保留下来，最终得到“成绩相同再按姓名排”的效果。如果不稳定，第二次排序会把第一次的成果全部破坏。

稳定性怎么判断：不基于比较的计数、基数排序天然稳定；插入、冒泡、归并排序中，只要相邻交换时严格使用>而不是>=，就是稳定的；而选择排序、快速排序、堆排序因为存在“跳跃式交换”，稳定性无从谈起。

2. O(n²)级别的三大基础排序

2.1 冒泡排序：最适合练手，但千万小心优化

冒泡排序的基本思路一句话就能说清：每一轮从头到尾扫一遍，把相邻的逆序对交换过来，这样每一轮结束后，当前范围内最大的元素就会像气泡一样“浮”到数组末尾。

C++最简实现是这个样子：

void bubbleSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; ++i) { for (int j = 0; j < n - 1 - i; ++j) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); } } } }

外层循环控制轮数，内层循环控制比较范围。n - 1 - i是关键——第i轮结束后，数组末尾的i个元素已经是排好序的最大值，不需要再碰它们。如果你去掉后面的- i，算法依然能跑，但会多出一堆无意义的比较。

动态过程看什么：在可视化工具里观察，你会发现每一轮都有若干次相邻交换，像气泡逐步上升。第一轮结束，最大值沉底；第二轮结束，次大值也归位。如果运气好，数组在第3轮就已经完全有序，但上面的朴素实现仍然会跑完全部n-1轮——这就是优化点。

这个基础版本虽然逻辑没毛病，但效率上有明显的浪费空间。我强烈建议你直接养成写优化版冒泡的习惯：

void bubbleSortOptimized(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; ++i) { bool swapped = false; for (int j = 0; j < n - 1 - i; ++j) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); swapped = true; } } if (!swapped) break; // 这一轮没发生任何交换，说明已经有序 } }

swapped标志位的意义在于：如果某一轮扫描时一次交换都没发生，说明整个数组已经有序，直接跳出循环。这样对于基本有序的数据，冒泡排序的最佳时间复杂度可以从O(n²)降为O(n)。实测下来，对一个接近有序的十万级数组，优化版可能只用几毫秒，未优化版却要跑好几秒。

冒泡排序适合的角色是“教学演示”和“面试手写热身”，实际开发中几乎不会用它。空间复杂度O(1)，稳定，平均和最坏时间复杂度都是O(n²)。

2.2 选择排序：交换次数最少的“老实人”

选择排序的思路特别符合人的直觉：每一轮挑出剩下元素中最小的那个，放到当前轮次的起始位置。

void selectionSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; ++i) { int minIdx = i; for (int j = i + 1; j < n; ++j) { if (arr[j] < arr[minIdx]) { minIdx = j; } } if (minIdx != i) { swap(arr[i], arr[minIdx]); } } }

这个算法的特点是交换次数非常少，每一轮最多一次交换，总共最多n-1次交换。如果交换两个元素的代价很高（比如要交换的是大型结构体对象），选择排序就比较有优势。但它有个致命短板：不管数组是否有序，内层循环都要完整跑完，所以它的最好、最坏、平均时间复杂度都是O(n²)，没有“提前结束”的可能。

不稳定性是选择排序最容易被忽略的问题。看这个例子：数组[5a, 3, 5b]，第一轮找到最小值3，把它和第一个元素5a交换，结果变成[3, 5b, 5a]——两个5的相对顺序变了。这就是“跳跃式交换”破坏稳定性的经典案例。面试时如果被问“选择排序稳定吗”，答案是稳定中带一个“不”字，原因就是这个例子。

选择排序还有一处可优化：每轮同时找最大值和最小值，最大值放末尾，最小值放开头，这样能把轮数砍半。但在大O层面没有本质区别，实际意义有限，知道有这个技巧就够了。

2.3 插入排序：小规模数据里的隐藏BOSS

插入排序的思路可以类比打扑克牌时整理手牌：摸到一张新牌，从右往左找到合适的位置插进去，后面的牌依次往后挪。

void insertionSort(vector<int>& arr) { int n = arr.size(); 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]的原始值；第二，while循环的条件是arr[j] > key而不是>=，这是保证稳定性的关键；第三，最内层是“移动”而不是“交换”，所以插入排序的常数项比冒泡小得多。

动态过程看什么：整个数组从左到右逐渐变成“左边已排序，右边未排序”的状态，每一轮插入像打牌时把新牌插进已经排好的序列中。最容易观察到的细节是，当数组本身接近有序时，内层while循环几乎不进，算法几乎以O(n)的速度跑完——这是插入排序最大的实战价值。

为什么说它是“小规模数据里的隐藏BOSS”？因为在实际工程中，当数据量小于某个阈值（比如16或32）时，插入排序往往比快速排序还快。原因在于快排有递归调用、partition 扫描等额外开销，插入排序的循环结构在CPU缓存里跑得非常顺畅。这也是C++标准库std::sort在递归到小区间时切换到插入排序的原因，后面会详细讲。

三大O(n²)排序的适用场景总结一下：冒泡适合教学；选择适合交换代价高的场景；插入排序则适合“基本有序的小规模数据”，它是所有高效排序算法最后的“兜底方案”。

3. 四个高效的比较排序

3.1 希尔排序：插入排序的“跳跃式升级”

希尔排序是第一个突破O(n²)瓶颈的排序算法。它的核心洞察是：插入排序之所以慢，是因为它只能把元素一格一格往后挪。如果允许元素“跳着走”，让数组先宏观上大致有序，再用插入排序收尾，就能大幅提升效率。

void shellSort(vector<int>& arr) { int n = arr.size(); for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; ++i) { int tmp = arr[i]; int j = i; while (j >= gap && arr[j - gap] > tmp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = tmp; } } }

外层循环控制步长（gap），内层就是“间隔为gap的插入排序”。当gap = n/2时，相当于把数组分成n/2组，每组两个元素分别排序；随着gap不断缩小到1，最后一次就是一个标准的插入排序。

关键理解点：为什么最后一次插入排序效率高？因为前面几轮大gap排序已经把大的元素“甩”到了后面，小的元素“提”到了前面，整个数组基本有序，插入排序在这时候跑得非常快。换句话说，希尔排序是用前几轮“粗调”为最后一轮“精调”铺路。

希尔排序的时间复杂度分析比前面几个复杂得多，它跟gap序列的选择强相关。用最简单的gap = n/2递减序列，最坏情况是O(n²)；用Hibbard序列1, 3, 7, 15...可以做到O(n^1.5)；用Sedgewick序列可以达到约O(n^1.3)。因为分析复杂，面试一般只要求你说出“平均大约是O(n^1.3)到O(n^1.5)，最坏O(n²)”这个级别的结论就够了。

空间复杂度O(1)，不稳定，因为相同元素可能跨越gap交换。工程上希尔排序比较少单独用，但它的“先粗调后精调”思想在很多场景都能复用，理解它有助于建立“预处理 + 精处理”的算法思维。

3.2 归并排序：分治思想的完美示范

归并排序是分治策略最典型的代表：把一个数组从中间切成两半，分别排序，再把两个有序子数组合并成一个有序数组。分到什么时候停止？分到只剩一个元素，单个元素天然有序，然后一路合并回去。

void merge(vector<int>& arr, int left, int mid, int right) { vector<int> tmp(right - left + 1); int i = left, j = mid + 1, k = 0; 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++]; copy(tmp.begin(), tmp.end(), arr.begin() + left); } void mergeSort(vector<int>& arr, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); }

merge函数是核心，它同时扫描两个有序区间，每次取较小的那个放入临时数组。注意三个while循环的分工：第一个是双方都有剩余元素时取较小值；后面两个处理某一方已排完的情况，把另一个区间的剩余部分直接拷贝过去。合并完成后，copy把临时数组拷回原数组对应区间。

有一个细节：mid = left + (right - left) / 2，我故意不用(left + right) / 2。这是因为left + right可能溢出int范围（当数组很大时），而left + (right - left) / 2是安全的。这个写法是所有二分类算法都应该养成的习惯。

归并排序的复杂度非常稳定：最好、最坏、平均都是O(n log n)，空间复杂度O(n)，因为每一层递归虽然会创建多个临时数组，但递归返回后会被释放，同一时刻最多占用约n个额外空间。稳定性很好，只要合并时用<=而不是<。

归并排序的实战价值在于：第一，它是稳定排序中的效率天花板；第二，它天然适合外部排序——当数据量大到无法全部装入内存时，可以分成多个小文件各自排序，再逐步合并；第三，链表排序也能用它，因为链表不需要随机访问，归并只需要“顺序+指针”。

有一个常见的实现优化：在递归区间长度小于某个阈值时，改用插入排序而不是继续递归到底。这一点和std::sort的做法一致，能显著减少小规模数据时的函数调用开销。

3.3 快速排序：工业界最常用的排序算法

快速排序被称为“20世纪十大算法之一”，它在平均情况下的常数项比归并和堆排都小，所以实际表现通常最优。核心思想也是分治：选一个基准值（pivot），把数组分成“小于基准”和“大于等于基准”两部分，再递归排序两部分。

下面是经典的Lomuto分区方式，代码最简洁、最好记：

int partition(vector<int>& arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; ++j) { if (arr[j] < pivot) { ++i; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[high]); return i + 1; } void quickSort(vector<int>& arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } }

partition做的事：把arr[high]当作基准，遍历除基准外的所有元素，凡是小于基准的都换到左边去，用i维护“小于区间的右边界”。遍历结束后，把基准换到i+1位置，此时基准左边全是小于它的元素，右边全是大于等于它的元素，基准本身已经到了最终位置。

动态过程非常直观：选择一个基准后，整个数组像被“切了一刀”，小的跑左边，大的跑右边，基准落在中间。递归下去，每一段都切一刀，直到整个数组有序。观察点在于：每一轮partition结束后，基准元素的位置就是它在最终有序数组中的位置，这个性质叫“基准归位”。

快速排序最致命的问题：当数组已经有序（或基本有序），且每次选取最后一个元素作基准时，分区会极度不平衡（一边n-1个元素，一边0个），递归深度变成n，时间复杂度退化到O(n²)。看清楚了：对有序数组，朴素快排反而是最差情况，这个反直觉的结论必须记住。

为了解决这个问题，工程上有两个经典优化方向。第一个是三数取中：取arr[low]、arr[mid]、arr[high]的中位数作基准，可以大幅降低有序数组退化的概率。第二个是随机化基准：随机选一个位置和arr[high]交换，再用常规partition，让最坏情况变成一个极小概率事件。这两个优化我建议你都亲手实现一遍，因为它们直接关系到快排在真实场景中的可靠性。

C++标准库std::sort使用的不是简单快排，而是一种叫内省排序（introspective sort）的混合策略：先快排，如果递归深度超过某个阈值（通常是2log₂n），就切换到堆排序，避免退化。递归到小区间（一般是16个元素以内）时直接切换到插入排序。这就是为什么你几乎可以无脑用std::sort，而不必担心极端数据导致性能崩盘。

3.4 堆排序：把数组当二叉树玩

堆排序利用的是二叉堆的性质：最大堆的堆顶永远是整个数组的最大值。把最大值换到末尾，缩小堆的范围，再调整堆结构，重复这个过程就完成排序。

void heapify(vector<int>& arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(vector<int>& arr) { int n = arr.size(); for (int i = n / 2 - 1; i >= 0; --i) { heapify(arr, n, i); } for (int i = n - 1; i > 0; --i) { swap(arr[0], arr[i]); heapify(arr, i, 0); } }

第一部分建堆：对数组从最后一个非叶子节点开始往前做heapify，为什么从n/2 - 1开始？因为在这个位置之后的所有节点都是叶子节点，叶子节点天然满足堆性质，不用处理。第二步执行n-1轮：把堆顶（最大值）和最后一个元素交换，此时最大元素固定在数组末尾；堆的有效长度减1，然后对堆顶重新做heapify恢复最大堆。

heapify的核心逻辑：比较节点i和它的左右孩子，找到三者中最大的；如果最大者不是i，就交换，然后递归堆化被交换的孩子节点。这个过程是自顶向下的“下沉”操作。

堆排序的几个特点要重点说：空间复杂度O(1)，是原地排序；任何情况（最好、最坏、平均）时间复杂度都是O(n log n)，没有快排那种退化问题；但不稳定，因为堆顶元素会直接跳到末尾，跨越大量元素。动态过程看什么：你会看到每一轮都是“把当前堆的最大值抽出来扔到末尾”，有点像在倒着建一个有序序列。

实际工程中，堆排序作为“排序算法”用的场景反而不如它背后的数据结构用得多——优先队列、top-k问题、定时器管理等全是堆在支撑。排序方面它更多的身份是“保证最坏情况的替补”，和std::sort内部切换到堆排序的思路一致。

4. 三个不基于比较的线性排序

4.1 计数排序：用空间换时间的极致

计数排序的思想非常朴素但有效：不比较大小，而是统计每个值出现了几次，然后直接按值从小到大重新填回数组。前提是数据的取值范围有限且已知，且最好是比较集中的非负整数。

void countingSort(vector<int>& arr) { if (arr.empty()) return; int maxVal = *max_element(arr.begin(), arr.end()); vector<int> count(maxVal + 1, 0); for (int x : arr) ++count[x]; int idx = 0; for (int i = 0; i <= maxVal; ++i) { while (count[i] > 0) { arr[idx++] = i; --count[i]; } } }

maxVal决定辅助数组的大小。第一轮遍历统计每个值的出现次数，然后按从小到大的顺序，把每个值按出现次数写回原数组。比如count[5] = 3，就连续写三个5进去。

计数排序的复杂度很好算：时间O(n+k)，其中k是取值范围（maxVal + 1）；空间O(k)。当k远大于n时（比如给一个最大值一亿的小数组排序），空间浪费巨大，计数排序就完全不合适了。

上面给出的版本是一个简化版，它“就地重写”数组，所以丧失了稳定性。如果需要稳定版本，就要用“前缀和 + 反向填充”的方式：先计算count的前缀和，然后从原数组末尾往前遍历，把每个元素放到它应该在的位置。这是面试里比较常见的进阶考点，建议你亲手推导一遍。

计数排序最典型的应用场景是：数据量大、取值范围小、值域集中。比如给几百万人的年龄排序、给考试成绩排序、给0到1000之间的整数排序，效果极其理想。

4.2 桶排序：把数据分堆再处理

桶排序是“分而治之”思想在非比较排序里的体现：把数据根据大小范围分到若干个桶里，对每个桶单独排序，最后把所有桶按顺序拼接起来。关键是分桶方案要合理，尽量让数据均匀分布到每个桶中。

假设数据是[0,1)区间内的浮点数，可以用下面的实现：

void bucketSort(vector<float>& arr) { int n = arr.size(); vector<vector<float>> buckets(n); for (float x : arr) { int idx = x * n; buckets[idx].push_back(x); } int idx = 0; for (auto& bucket : buckets) { sort(bucket.begin(), bucket.end()); for (float x : bucket) { arr[idx++] = x; } } }

idx = x * n把[0,1)区间均匀切成了n份，值落在哪份就进哪个桶。桶内排序用了标准库的sort，这是非常合理的妥协——桶的规模较小，用高质量通用排序完全够用。

桶排序的时间复杂度分析依赖一个假设：数据均匀分布。理想情况下，每个桶大约只有一个元素，桶内排序成本极低，总复杂度O(n)。但如果数据分布极度不均匀（比如所有数据都挤进同一个桶），就退化成普通排序，最坏O(n²)，甚至不如快排稳定。

动态过程看什么：一堆散点被撒进若干个桶里，每个桶内部有序化，然后像“倒水”一样按序倒出来，整个数组瞬间有序。观察点是桶的规模和分布是否均匀——这直接决定性能。

桶排序的适用场景比计数排序宽一些，凡是数据分布均匀且有明确范围的场景都可以用。比如对一组在0到10000之间均匀分布的浮点数或整数，桶排序配合每个桶内的插入排序，效果非常好。

4.3 基数排序：多轮按位分配

基数排序的思路是：从最低位到最高位（LSD，Least Significant Digit），每一轮根据当前位的数字把所有元素分到0-9这10个桶里，再按顺序收回来。经过所有位数处理后，数组天然有序。

void radixSort(vector<int>& arr) { int maxVal = *max_element(arr.begin(), arr.end()); for (int exp = 1; maxVal / exp > 0; exp *= 10) { vector<int> output(arr.size()); vector<int> count(10, 0); for (int x : arr) ++count[(x / exp) % 10]; for (int i = 1; i < 10; ++i) count[i] += count[i - 1]; for (int i = arr.size() - 1; i >= 0; --i) { int digit = (arr[i] / exp) % 10; output[count[digit] - 1] = arr[i]; --count[digit]; } arr = output; } }

exp代表当前处理的位权，初始为1（个位），每轮乘以10。(x / exp) % 10取出x在这一位的数字。内层的“前缀和 + 反向填充”就是上一节说的稳定计数排序，它是基数排序稳定的关键。

为什么必须反向填充？因为相同位数的多个元素需要保持它们在前一轮排序中确立的相对顺序。反向填充时，从原数组末尾开始往前放，每放一个就把该类的计数减1，这样就能保证后出现的元素还是放在后面，稳定性就在这。

基数排序的时间复杂度是O(d × (n + k))，其中d是最大数的位数，k是基数（十进制就是10）。当d比较小（比如所有数都在100万以内，d最大7）时，复杂度接近线性，比O(n log n)还要快。空间复杂度O(n + k)。

动态过程看什么：每一轮，你会看到数据按当前位被“洗”了一遍，低位排序的结果被完整保留到下一轮。多轮之后，看似没有大小比较，数组却悄悄有序了。

有一个必须注意的适配问题：上面的实现只适用于非负整数。如果数组里有负数，需要先做偏移（把所有数加上最小值的绝对值），或者对负数单独处理。浮点数也可以通过先转成整数变体来处理，但工程上一般直接用std::sort更省事。

5. 性能横评与选型实战

5.1 一份可供参考的基准测试数据

所有复杂度分析最终都要落到“实际谁更快”这个问题上。我在一台普通配置的机器上，用C++对10万个随机整数做过一次简单基准测试（用std::chrono计时，开O2优化），得到的大致趋势可以分享给大家作参考。注意这不是严格的论文级评测，但能说明问题：

这个数据最能说明的一个道理是：O(n²)和O(n log n)之间有一道巨大的性能鸿沟。10万个元素是很多实际业务场景的真实数据量级，冒泡排序要用好几秒来完成，而快排只需几毫秒——差了整整三个数量级。这也解释了为什么工程上几乎没有人会用O(n²)算法处理大规模数据。

换一组数据你会发现更多细节：当数据量降到1000个以内时，插入排序和冒泡排序的差距明显缩小；当数据基本有序时，插入排序甚至可能打赢快排（因为快排的partition和递归开销还在，而插入排序等于在遍历一遍有序数组）。这就是为什么所有工程排序库都会在小区间切换到插入排序。

5.2 不同场景下的选型建议

根据上面的实测结果和算法特性，我总结了一套相对务实的选型建议，平时写代码可以直接套用：

• 数据量小（几千以内）：优先插入排序。代码简单、稳定、在数据接近有序时极快。
• 数据量中等且内存充足：快速排序通常是最优选择。它是最快的通用比较排序，常数项小。注意大数据量时避免最坏情况，使用三数取中或随机化基准。
• 数据量巨大且内存紧张：优先考虑原地排序，快排或堆排。堆排有最坏情况保证，快排平均更快但需要警惕退化。
• 需要稳定性：归并排序是第一选择。如果数据规模特别大放不进内存，就用外部归并排序。
• 数据取值范围小且为整数：计数排序，O(n)吊打一切比较排序。
• 数据均匀分布在某个区间：桶排序，配合插入排序效果极佳。
• 数据位数固定且较小：基数排序，比如身份证号、电话号码、定长字符串排序。

5.3 C++标准库sort为什么可以“无脑用”

一个常见困惑是：“我既然学了十大排序，为什么平时直接用std::sort就行？标准库用的到底什么？”

std::sort的实现通常混合了三种策略：当区间长度大于某个阈值时使用内省快排（IntroSort），深度超限时切换堆排，小区间用插入排序。也就是说，标准库已经在“平均最快”和“最坏不崩”之间做了非常好的平衡。另一个常用函数std::stable_sort则是基于归并排序的，在需要保持相等元素相对顺序时使用。

对于绝大多数C++程序员，直接使用标准库排序是正确且高效的选择。那为什么还要学习十大排序？因为你需要知道标准库做了什么、为什么这样做、在什么情况下标准库帮不了你。比如自定义对象排序时，你的比较函数不能违反“严格弱序”；比如你需要Top-k问题时，std::sort全排序会浪费大量时间，这时候用std::partial_sort或手动建堆更合适；再比如面试会让你手写排序，考察的是你对算法本质的理解，而不是那个标准库调用。

6. 十大排序避坑指南

6.1 五个隐藏在代码里的致命细节

第一个坑：二分和分治里用(left + right) / 2导致整型溢出。这个bug很隐蔽，数组达到一定规模后才会暴露。写出left + (right - left) / 2是刻进肌肉记忆的标准动作。

第二个坑：冒泡、插入排序的边界条件写错。内层循环少算一个下标会导致最后一个元素永远不参与排序；多算一个下标会导致访问越界。记住冒泡是j < n - 1 - i，插入是while (j >= 0 && arr[j] > key)，选择是for (int j = i + 1; j < n; ++j)，三个边界条件各不相同，抄代码没用，要理解每个边界的来源。

第三个坑：快排分区时用了<=而不是<。如果基准值有大量重复，用<=会把相等的元素全部换到一边去，造成极度不平衡的分区，快排退化成O(n²)。对比归并排序合并时用<=是为了稳定性，快排partition里用<是为了避免重复元素堆到一侧，两者完全不同。

第四个坑：堆排序建堆时从n/2 - 1开始，不是从n-1开始。原因前面说过，叶子节点天然是合法的堆节点，不用调整。从数组末尾开始也能跑，但会导致大量无效的heapify调用。

第五个坑：递归排序没有设置递归出口，或者出口条件写错。归并排序必须有if (left >= right) return;，快速排序必须有if (low < high)。这个条件缺失的直接后果是无限递归、栈溢出，程序崩溃。还有一个相关隐患：递归深度过深导致爆栈，比如对100万元素递归快排，最坏情况下递归深度可达到100万层，这在栈空间有限的场景下会直接Segmentation Fault。

6.2 让排序代码更“C++”的进阶写法

把排序函数写成“只能排vector”的样子，在真实工程里是不够的。至少要考虑两件事：支持任意容器和自定义比较规则。模板化写法可以让排序函数的适用范围大幅扩展。

给出一个通用的快速排序模板作为参考，它能接受任何随机访问迭代器，也支持传入比较器，这样你在项目中任何容器上都能复用它：

template <typename RandomIt, typename Compare> void quickSort(RandomIt first, RandomIt last, Compare comp) { if (first >= last) return; auto pivot = *prev(last); // 取最后一个元素为基准 auto mid = partition(first, last, [&](const auto& x) { return comp(x, pivot); }); swap(*prev(last), *mid); // 基准放回正确位置 quickSort(first, mid, comp); // 注意边界：mid之前的元素已小于等于基准 quickSort(next(mid), last, comp); }

用迭代器而不是具体容器类型，用lambda或函数对象而不是固定的>比较，好处不言自明。另一个实用C++技巧是：如果排序的是自定义结构体，优先写operator<或者提供自定义比较器，排序代码就不需要大幅改动。此外，当对象体积较大时，使用sort内部会自动用移动语义优化swap，但如果你自己手写排序循环，记得硬编码std::move相关的交换逻辑，避免不必要的深拷贝。

6.3 动态图解怎么看、怎么用

大家常在各类可视化网站看到排序算法的动态演示，比如柱子随着每次交换而变化高度。看上去很直观，但不少初学者看完动画还是不会写代码，原因是用眼睛记住了动画，却没在纸上推演过程。

我建议的用法是：每看一个算法的动态过程，手边就同时放一张纸，把数组的关键状态写下来。比如看快速排序时，把每个partition后基准元素的位置记下来，你会发现所有基准位置连起来就是最终排序结果。看归并排序时，把每一层合并后数组的样子写出来，你会看到“深度log n、每层总工作量n”这句话是怎么体现在具体数据上的。看完动画再亲手写一遍代码，这个经历的价值远超单纯地看或者单纯地背。

还有一种很有效的训练方式：修改动画的速度，用最慢档观察边界条件下（有序数组、逆序数组、全部相同数组）算法的行为。比如观察全部相同元素时快速排序的表现，再观察插入排序的表现，两者差异会让你深刻理解“比较算法对输入分布敏感”这件事。

6.4 我的排序算法学习路线建议

如果这套算法是第一次接触，不建议一口气全部吃透。我给一个分三步走的学习路线：

第一阶段：只练冒泡、选择、插入、归并、快排，用各种测试数据反复跑，自己出测试用例，直到能用最短时间默写代码。这五个是最核心的，面试和工程都绕不开。

第二阶段：把希尔、堆排补上。堆排需要你顺手把建堆、heapify、优先队列一起学了，因为它们的底层逻辑完全一样；希尔排序主要理解gap序列的思想，代码本身不难。

第三阶段：最后接触计数、桶、基数三个非比较排序。它们三个靠的是对数据特征的理解，适合在有比较排序的基础之后集中突破。学习时多问一句“如果数据不满足预设条件会发生什么”，这一步思考能让你少踩很多坑。

最后分享一个我实际教学项目中反复看到的规律：能写对代码的人很多，能说清“为什么这样选”的人很少。十大排序算法的价值永远不在代码本身，而在于每一行代码背后那些关于复杂度、稳定性、数据特征的权衡判断。把这些判断内化成自己的思维习惯，比背会十个函数要重要得多。