C++十大排序算法全解析：从原理到实战应用指南

1. 项目概述：为什么我们需要十种排序算法？

在C++开发者的日常工作中，排序是一个绕不开的基础操作。无论是处理用户数据、优化查询性能，还是作为更复杂算法（如图算法、搜索算法）的预处理步骤，一个高效的排序实现往往是性能的关键。你可能用过std::sort，它又快又好，但你是否曾好奇过它内部是如何工作的？或者，当面试官让你手写一个“稳定”的快速排序时，你是否能从容应对？

这个项目，就是一次对排序算法世界的系统性探索。我们不满足于仅仅调用库函数，而是要亲手用C++实现十种经典的排序算法。这不仅仅是“造轮子”，而是一次深刻理解计算机科学基础、锻炼编码能力、并为应对各种复杂场景储备“工具箱”的过程。不同的排序算法，如冒泡排序、快速排序、归并排序等，各有其独特的“性格”和适用场景。理解它们，意味着你能在数据几乎有序时选择插入排序以获得近乎线性的效率，能在内存紧张时使用堆排序，能在需要稳定排序且链表结构时选择归并排序。

对于初学者，这是理解算法思想、练习C++语法（如数组操作、递归、模板）的绝佳实践。对于有经验的开发者，这是一次温故知新、深入理解算法细节（如原地排序、稳定性、时间复杂度常数因子）的机会。我们将从最直观的算法开始，逐步深入到更高效、更精巧的实现，并会重点探讨在C++实现中的各种“坑”与技巧。

2. 排序算法核心概念与分类解析

在动手写代码之前，我们必须统一“语言”，理解几个核心概念。这些概念是评价和选择排序算法的标尺。

2.1 算法性能的度量：时间与空间复杂度

时间复杂度描述算法执行时间随数据规模增长的趋势。我们常用大O表示法。

• O(n²)：如冒泡、选择、插入排序。数据量翻倍，时间大约变为4倍。适用于小规模数据（如n<1000）或几乎有序的数据。
• O(n log n)：如快速、归并、堆排序。这是基于比较的排序算法理论上的最优时间复杂度。大规模数据下的首选。
• O(n + k)：如计数排序、桶排序、基数排序（线性排序）。它们不基于比较，而是利用数据的特定属性，在满足条件时效率极高。

空间复杂度描述算法运行所需额外内存空间。

• O(1)：原地排序。如冒泡、选择、插入、希尔、堆排序。只使用常数级别的额外空间。
• O(n)或O(log n)：非原地排序。如归并排序需要O(n)的辅助数组；递归实现的快速排序在递归调用栈上需要O(log n)的空间。

2.2 排序的稳定性：相等元素的相对次序

稳定性是排序算法一个非常重要的特性。如果排序后，相等元素的相对顺序保持不变，则该算法是稳定的；否则，是不稳定的。

为什么稳定性重要？考虑一个场景：我们先按学生成绩排序，再按班级排序。如果第二次排序是稳定的，那么同班学生的成绩顺序将得以保持，结果就是每个班级内学生按成绩高低排列。如果是不稳定的，班级内的成绩顺序就会被打乱。

• 稳定排序：冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序。
• 不稳定排序：选择排序、希尔排序、堆排序、快速排序（经典实现）。

注意：算法的稳定性取决于具体实现。例如，通过精心设计元素交换逻辑，快速排序也可以实现为稳定排序，但会牺牲部分效率或增加空间复杂度。我们通常讨论其最常见、最经典的实现。

2.3 基于比较 vs. 非基于比较

这是算法设计思想上的根本区别。

• 基于比较的排序：通过比较元素间的大小来决定次序。前述的冒泡、选择、插入、希尔、归并、快速、堆排序都属于此类。它们具有普适性，不关心数据的具体内容，但效率受限于O(n log n)的理论下限。
• 非基于比较的排序：利用数据本身的特性（如整数范围、字符串长度）来排序。计数排序、桶排序、基数排序属于此类。它们的时间复杂度可以达到O(n)，但对输入数据有特定要求（如范围已知、可分割为独立部分等）。

3. 十大排序算法C++实现与深度剖析

接下来，我们将逐一实现这十种算法。我会提供清晰的代码，并着重解释实现要点、易错点以及微调技巧。我们假设对整型数组vector<int>& arr进行升序排序。

3.1 冒泡排序：最直观的入门算法

冒泡排序通过重复“遍历数组，比较相邻元素，如果顺序错误就交换”这一过程来工作。每一轮遍历会将当前未排序部分的最大元素“冒泡”到正确位置。

void bubbleSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; ++i) { // 优化：标记本轮是否发生交换 bool swapped = false; // 最后i个元素已经有序，无需再比较 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; } }

实操心得：

1. 优化点：引入swapped标志是冒泡排序最重要的优化。对于近乎有序的数组，可以大幅提升效率。
2. 为什么是n-1-i？第i轮结束后，数组末尾的i个元素已经是全局最大的i个且已就位，所以内层循环无需再访问它们。
3. 稳定性：因为只有在前一个元素严格大于后一个时才交换，相等时不交换，所以是稳定的。

3.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; // 更新最小元素索引 } } // 将找到的最小元素与第i个位置交换 swap(arr[i], arr[minIdx]); } }

实操心得：

1. 不稳定性分析：这是典型的不稳定排序。例子：[5a, 8, 5b, 2, 9]。第一轮找到最小元素2，与第一个位置的5a交换，序列变为[2, 8, 5b, 5a, 9]。此时，两个5的相对顺序（5a在5b前）被破坏了。
2. 交换次数少：选择排序每轮只进行一次交换，交换次数为O(n)。对于交换成本很高的元素（比如大型结构体），这可能是一个优点，但通常其O(n²)的比较次数是主要瓶颈。

3.3 插入排序：像整理扑克牌

插入排序的工作方式像许多人排序一手扑克牌。开始时，左手为空，然后每次从桌上（未排序部分）拿起一张牌，并将其插入到左手已排序牌中的正确位置。

void insertionSort(vector<int>& arr) { int n = arr.size(); for (int i = 1; i < n; ++i) { // 从第二个元素开始 int key = arr[i]; // 待插入的元素 int j = i - 1; // 将arr[0..i-1]中大于key的元素向后移动一位 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; --j; } // 将key插入到正确位置 arr[j + 1] = key; } }

实操心得：

1. 近乎有序数据的王者：当数组基本有序时，内层的while循环很快会终止，时间复杂度接近O(n)。这是很多高级排序算法（如TimSort）在小区间转向插入排序的原因。
2. 原地与稳定：它是原地的，并且因为遇到相等元素时（arr[j] > key条件不成立）就停止移动，所以是稳定的。
3. 小数据集的优势：在数据量很小（比如n<50）时，由于其常数因子小，插入排序的实际运行时间可能优于O(n log n)的算法。

3.4 希尔排序：插入排序的威力增强版

希尔排序是插入排序的改进，它允许交换相距较远的元素。其核心思想是：将数组按一定间隔（增量）分组，对每组进行插入排序；随着增量逐渐减小，每组包含的元素越来越多，当增量减至1时，整个数组被当作一组进行最后一次插入排序，此时数组已基本有序，插入排序效率很高。

void shellSort(vector<int>& arr) { int n = arr.size(); // 使用Knuth增量序列：1, 4, 13, 40, 121... (3*h + 1) int h = 1; while (h < n / 3) h = 3 * h + 1; while (h >= 1) { // 对间隔为h的子数组进行插入排序 for (int i = h; i < n; ++i) { int key = arr[i]; int j = i; while (j >= h && arr[j - h] > key) { arr[j] = arr[j - h]; j -= h; } arr[j] = key; } h /= 3; // 缩小增量 } }

实操心得：

1. 增量序列是关键：希尔排序的性能严重依赖于增量序列的选择。Knuth序列(3^k-1)/2是实践中表现较好的一个。糟糕的增量序列（如原始希尔建议的n/2）可能导致性能退化。
2. 不稳定性的来源：由于是跨间隔的比较和移动，相等的元素可能分属不同的子序列并被调换顺序，因此希尔排序是不稳定的。
3. 理解其优势：它通过前期的大步长移动，使元素离最终位置更近，从而减少了后期小步长插入排序的工作量。其时间复杂度分析复杂，介于O(n log² n)和O(n^(3/2))之间，优于简单的O(n²)排序。

3.5 归并排序：分而治之的典范

归并排序采用经典的分治策略：将数组递归地分成两半，分别排序，然后将两个有序的子数组合并成一个有序数组。

// 合并两个有序子数组 arr[l..m] 和 arr[m+1..r] void merge(vector<int>& arr, int l, int m, int r) { vector<int> temp(r - l + 1); // 辅助数组 int i = l, j = m + 1, k = 0; while (i <= m && j <= r) { if (arr[i] <= arr[j]) { // 注意这里是 <=，保证了稳定性 temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // 拷贝剩余元素 while (i <= m) temp[k++] = arr[i++]; while (j <= r) temp[k++] = arr[j++]; // 将合并后的数组拷贝回原数组 for (int p = 0; p < k; ++p) { arr[l + p] = temp[p]; } } void mergeSortHelper(vector<int>& arr, int l, int r) { if (l >= r) return; // 递归基 int m = l + (r - l) / 2; // 防止溢出 mergeSortHelper(arr, l, m); mergeSortHelper(arr, m + 1, r); merge(arr, l, m, r); } void mergeSort(vector<int>& arr) { mergeSortHelper(arr, 0, arr.size() - 1); }

实操心得：

1. 稳定性的保证：在merge函数中，判断条件arr[i] <= arr[j]使用了<=。这意味着当左子数组和右子数组的元素相等时，我们优先取左子数组的元素。这严格保证了相等元素的原始相对顺序，因此归并排序是稳定的。
2. 空间复杂度O(n)：这是其主要缺点，需要与原始数组等大的额外空间。对于内存极其敏感的场景需谨慎。
3. 递归与迭代：上述是递归实现，清晰易懂。也可以使用迭代（自底向上）的方式实现，避免了递归调用栈的开销，但代码稍复杂。
4. 链表排序的最佳选择：由于合并两个有序链表可以在O(1)空间内完成，归并排序是排序链表数据结构时最常用且高效的方法。

3.6 快速排序：平均情况下的王者

快速排序同样使用分治，但策略不同：它选择一个“基准”元素，将数组划分为两部分，使得左边部分的所有元素都小于等于基准，右边部分的所有元素都大于基准，然后递归地对左右两部分进行排序。

// 分区函数：选择arr[r]作为基准，返回基准的最终位置 int partition(vector<int>& arr, int l, int r) { int pivot = arr[r]; // 选择最右侧元素为基准 int i = l - 1; // i指向小于基准区域的最后一个元素 for (int j = l; j < r; ++j) { if (arr[j] <= pivot) { ++i; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[r]); // 将基准放到正确位置 return i + 1; } void quickSortHelper(vector<int>& arr, int l, int r) { if (l < r) { int pi = partition(arr, l, r); // 分区索引 quickSortHelper(arr, l, pi - 1); quickSortHelper(arr, pi + 1, r); } } void quickSort(vector<int>& arr) { quickSortHelper(arr, 0, arr.size() - 1); }

实操心得：

1. 基准的选择是灵魂：选择最右元素作为基准是最简单的实现，但在数组已有序或逆序时，会导致分区极度不平衡，时间复杂度退化为O(n²)。优化方法：随机选择基准（swap(arr[r], arr[l + rand() % (r-l+1)])）或使用三数取中法。
2. 不稳定性：分区过程中的交换是跳跃式的，会打乱相等元素的顺序。例如[3a, 2, 3b, 1]，以3b为基准，分区后顺序可能改变。
3. 原地排序：虽然递归调用栈需要O(log n)空间，但排序过程本身是原地的。
4. 小数组优化：和插入排序结合，当子数组规模小于某个阈值（如10-20）时，改用插入排序，可以减少递归深度和函数调用开销。这就是很多工业级sort函数的做法。

3.7 堆排序：利用堆结构的智慧

堆排序利用“堆”这种数据结构。首先将数组构建成一个最大堆（父节点值 >= 子节点值），此时堆顶（arr[0]）是最大元素。将其与堆的最后一个元素交换，然后将堆的大小减1，并对新的堆顶元素进行“下沉”操作以恢复最大堆性质。重复此过程，直到堆中只剩一个元素。

// 下沉操作：确保以idx为根的子树满足最大堆性质 void heapify(vector<int>& arr, int n, int idx) { int largest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != idx) { swap(arr[idx], arr[largest]); heapify(arr, n, largest); // 递归下沉 } } void heapSort(vector<int>& arr) { int n = arr.size(); // 1. 构建最大堆：从最后一个非叶子节点开始向上调整 for (int i = n / 2 - 1; i >= 0; --i) { heapify(arr, n, i); } // 2. 逐个提取堆顶元素 for (int i = n - 1; i > 0; --i) { swap(arr[0], arr[i]); // 将当前最大元素移到末尾 heapify(arr, i, 0); // 对剩余i个元素重新堆化 } }

实操心得：

1. 建堆的起点：最后一个非叶子节点的索引是n/2 - 1。这是因为叶子节点本身可以看作是一个合法的堆，所以从它们的父节点开始调整即可。
2. 不稳定性：堆排序在交换和堆化过程中，元素的移动是跳跃的。例如序列[2a, 2b, 1]，建堆和交换过程很容易破坏两个2的相对顺序。
3. 优点：堆排序是原地排序，且最坏情况下的时间复杂度也是O(n log n)，这在需要保证最坏情况性能时比快速排序有优势。同时，堆数据结构本身（优先队列）在解决Top-K等问题时非常有用。

3.8 计数排序：当数据范围已知时

计数排序不是基于比较的排序。它适用于输入数据是有确定范围的整数（比如0到K）。其核心是统计每个整数出现的次数，然后根据计数结果直接计算出每个元素在输出数组中的位置。

void countingSort(vector<int>& arr) { if (arr.empty()) return; // 1. 找出数组中的最大值和最小值，确定范围 int maxVal = *max_element(arr.begin(), arr.end()); int minVal = *min_element(arr.begin(), arr.end()); int range = maxVal - minVal + 1; // 2. 创建计数数组并统计频率 vector<int> count(range, 0); for (int num : arr) { count[num - minVal]++; // 偏移，将最小值映射到0 } // 3. 将计数数组转换为前缀和数组，此时count[i]表示小于等于(i+minVal)的元素个数 for (int i = 1; i < range; ++i) { count[i] += count[i - 1]; } // 4. 从后向前遍历原数组，根据前缀和数组放置元素（从后向前保证了稳定性） vector<int> output(arr.size()); for (int i = arr.size() - 1; i >= 0; --i) { int idx = arr[i] - minVal; output[count[idx] - 1] = arr[i]; count[idx]--; } // 5. 将结果拷贝回原数组 arr = output; }

实操心得：

1. 处理负数与偏移：经典计数排序假设数据非负。通过先找到最小值minVal，将所有元素减去minVal映射到[0, range-1]的区间，就可以完美支持负数。
2. 稳定性的实现：关键在第4步，从后向前遍历原数组，并将元素放入输出数组count[num] - 1的位置，然后count[num]--。这样，后出现的相等元素会被放在更靠后的位置，保持了原始顺序。
3. 空间与时间的权衡：空间复杂度为O(n+k)，其中k是数据范围。当k很大（如排序[1, 1000000]）时，会消耗大量内存，此时反而不如O(n log n)的算法。

3.9 桶排序：将数据分到多个桶中

桶排序假设输入数据均匀分布在一个范围内。它将数据分到有限数量的“桶”里，每个桶再分别排序（通常使用插入排序等简单算法），最后按顺序连接所有桶的结果。

void bucketSort(vector<int>& arr) { if (arr.empty()) return; int n = arr.size(); int maxVal = *max_element(arr.begin(), arr.end()); int minVal = *min_element(arr.begin(), arr.end()); // 1. 确定桶的数量和范围 int bucketNum = 5; // 桶的数量，可根据数据量和分布调整 int bucketRange = (maxVal - minVal) / bucketNum + 1; // 每个桶的范围 vector<vector<int>> buckets(bucketNum); // 2. 将元素放入对应的桶中 for (int num : arr) { int bucketIdx = (num - minVal) / bucketRange; // 确保索引在有效范围内，处理最大值的情况 bucketIdx = min(bucketIdx, bucketNum - 1); buckets[bucketIdx].push_back(num); } // 3. 对每个桶内部进行排序（这里使用std::sort，实践中可用插入排序） for (auto& bucket : buckets) { sort(bucket.begin(), bucket.end()); } // 4. 合并所有桶 int idx = 0; for (const auto& bucket : buckets) { for (int num : bucket) { arr[idx++] = num; } } }

实操心得：

1. 桶的数量与范围：这是桶排序性能的关键。桶太少，退化为一个桶内的比较排序；桶太多，则空桶过多，浪费空间。通常桶数量设置为sqrt(n)或根据经验值。
2. 桶内排序算法：由于每个桶内数据量期望较小，使用插入排序这类对小数据高效的算法非常合适。
3. 适用场景：桶排序在数据均匀分布时效率最高，能达到接近O(n)的时间复杂度。如果数据集中分布在某几个桶内，性能会退化。

3.10 基数排序：按位进行排序

基数排序是一种非比较型整数排序算法。其原理是将整数按位数切割成不同的数字，然后按每个位数分别进行排序（通常使用稳定的计数排序作为子程序）。可以从最低位（LSD）或最高位（MSD）开始。

这里以实现LSD基数排序为例：

// 使用计数排序作为子程序，对数组arr按照某一位（exp）进行排序 void countingSortForRadix(vector<int>& arr, int exp) { int n = arr.size(); vector<int> output(n); vector<int> count(10, 0); // 0-9十个数字 // 统计当前位（exp位）上每个数字的出现次数 for (int i = 0; i < n; ++i) { int digit = (arr[i] / exp) % 10; count[digit]++; } // 将计数转换为前缀和 for (int i = 1; i < 10; ++i) { count[i] += count[i - 1]; } // 从后向前构建输出数组（保证稳定性） for (int i = n - 1; i >= 0; --i) { int digit = (arr[i] / exp) % 10; output[count[digit] - 1] = arr[i]; count[digit]--; } // 拷贝回原数组 arr = output; } void radixSort(vector<int>& arr) { if (arr.empty()) return; int maxVal = *max_element(arr.begin(), arr.end()); // 从最低位开始，对每一位进行计数排序 for (int exp = 1; maxVal / exp > 0; exp *= 10) { countingSortForRadix(arr, exp); } }

实操心得：

1. 稳定性要求：基数排序的每一轮排序必须是稳定的，否则低位的排序结果会在高位排序时被破坏。这就是为什么我们使用稳定的计数排序作为子程序。
2. 处理负数：标准的LSD基数排序不能直接处理负数。常见的处理方法是：将数组分为负数和非负数两部分，对负数部分取绝对值后排序再反转，对非负数部分正常排序，最后合并。
3. 时间复杂度：O(d*(n+k))，其中d是最大数字的位数，k是进制数（这里是10）。当d较小，n较大时，效率很高。对于32位整数，d最大为10（十进制），所以可以看作是线性复杂度。
4. 空间复杂度：O(n + k)，主要来自计数数组和输出数组。

4. 算法对比与选型实战指南

纸上得来终觉浅，绝知此事要躬行。理解了原理和实现，我们更需要知道在什么场景下该用哪种算法。下面这个表格和后续分析，是我在实际项目中选择排序算法时的决策思路。

选型决策树：

1. 数据规模很小（n < 50）？是 → 使用插入排序。常数因子小，代码简单，且对有序数据友好。
2. 数据是整数，且范围很小（如0-100）？是 → 使用计数排序。线性时间，简单高效。
3. 数据是整数，范围大但位数不多（如手机号、身份证号）？是 → 使用基数排序。
4. 数据是浮点数，且均匀分布？是 → 考虑桶排序。
5. 需要稳定排序？是 → 在归并排序、计数排序、桶排序、基数排序中选择。
6. 内存非常紧张，必须原地排序？是 → 在快速排序、堆排序、希尔排序中选择。若担心快排最坏情况，选堆排序。
7. 排序链表？是 →归并排序是天然选择。
8. 以上都不是，通用场景？→ 使用快速排序（或标准库的std::sort）。它经过高度优化，在绝大多数情况下都是最佳实践。

关于std::sort：C++标准库的sort函数通常是一种混合排序算法（如IntroSort），它结合了快速排序、堆排序和插入排序的优点。在数据量大时使用快速排序，在递归深度过深（可能退化为O(n²)）时切换到堆排序保证最坏情况，在小区间时切换到插入排序。所以，在工程中，首选std::sort。

5. 常见问题与性能调优陷阱

在实际编码和面试中，会遇到一些典型问题。这里记录几个我踩过的坑和对应的解决方案。

5.1 递归深度与栈溢出

快速排序和归并排序的递归实现在处理大规模数据时，如果递归树不平衡，可能导致递归调用过深，引发栈溢出。

• 快速排序的应对：

  1. 随机化基准：这是避免最坏情况（已排序数组）的最有效方法。
  2. 尾递归优化：递归调用较小的那个分区，对较大的分区使用循环。这能将最坏情况下的栈深度限制在O(log n)。

  void quickSortTailOpt(vector<int>& arr, int l, int r) { while (l < r) { int pi = partition(arr, l, r); // 总是先递归处理较短的部分 if (pi - l < r - pi) { quickSortTailOpt(arr, l, pi - 1); l = pi + 1; // 用循环处理长的部分 } else { quickSortTailOpt(arr, pi + 1, r); r = pi - 1; } } }

  3. 迭代实现：使用显式栈来模拟递归过程，完全避免递归。

• 归并排序的应对：

  1. 迭代实现：自底向上的归并排序是天然的迭代过程，没有栈溢出风险。
  2. 限制递归：当子数组规模小于一定阈值时，改用插入排序，减少递归调用次数。

5.2 快速排序分区函数的边界问题

写partition函数是快速排序最容易出错的地方。常见的错误包括无限循环、索引越界、不能正确处理重复元素。

一个健壮的分区实现（Lomuto分区法，如上文所用）逻辑清晰，但交换次数较多。Hoare分区法通常更高效，但实现细节更微妙。

// Hoare分区法（初始版本，需注意细节） int partitionHoare(vector<int>& arr, int l, int r) { int pivot = arr[l + (r - l) / 2]; // 选择中间元素作为基准 int i = l - 1, j = r + 1; while (true) { do { i++; } while (arr[i] < pivot); do { j--; } while (arr[j] > pivot); if (i >= j) return j; // 注意返回的是j swap(arr[i], arr[j]); } } // 调用方式需改为 quickSortHelper(arr, l, pi); quickSortHelper(arr, pi+1, r);

注意：Hoare分区法返回的j是右子数组的起始索引减1，递归边界处理与Lomuto法不同，容易出错。建议初学者先掌握Lomuto法。

5.3 排序稳定性被意外破坏

当你需要稳定排序时，必须确保算法实现是稳定的。一个常见的陷阱是在“优化”时破坏了稳定性。

• 在冒泡/插入排序中：比较条件必须是>而不是>=。使用>=会在相等时也进行交换或移动，从而破坏稳定性。
• 在归并排序中：合并时，当左右元素相等，必须优先取左子数组的元素（即判断条件为left[i] <= right[j]）。
• 自己实现std::sort的比较函数：如果比较函数没有实现严格的弱序，或者对于相等元素返回true，会导致未定义行为，排序结果可能不稳定甚至错误。确保你的比较函数在a == b时返回false。

5.4 非比较排序的适用条件误解

计数排序、桶排序、基数排序不是万能的。我曾见过有人试图用计数排序对浮点数或范围极大的整数排序，结果内存爆掉。

• 计数排序：必须知道数据的范围，且范围不能太大。适用于年龄、分数等场景。
• 桶排序：依赖于数据均匀分布的假设。如果所有数据都落在一个桶里，就退化为O(n²)。
• 基数排序：只能用于可以按位分割的数据类型，如整数、字符串。对于浮点数，需要特殊的处理将其转换为整数形式。

5.5 性能测试与常数因子

时间复杂度的大O表示法忽略了常数因子。但在实际中，常数因子影响巨大。例如，虽然快速排序和堆排序都是O(n log n)，但由于缓存局部性更好（顺序访问多），快速排序通常比堆排序快2-3倍。这也是为什么std::sort以快速排序为主。

在对自己实现的算法进行性能测试时，要注意：

1. 使用足够大的随机数据（如100万条）。
2. 关闭编译器优化进行调试，打开优化进行性能测试（-O2或/O2）。
3. 计时时排除数组初始化、内存分配的时间。
4. 对比基准始终是std::sort，它是性能的黄金标准。

亲手实现这十种排序算法，就像一位木匠熟悉了他的每一件工具。你不会在任何时候都用上所有工具，但你知道当需要处理一块纹理特殊的木料时，该从工具箱的哪个角落取出哪件。在C++的世界里，std::sort是你最常用、最可靠的电动刨，但理解其背后的原理以及备选方案，能让你在遇到“特殊木料”——比如需要稳定排序的链表、范围有限的整数、或者对内存有极致要求的嵌入式环境——时，依然能游刃有余。这份实现的代码和其中的思考，就是你的算法工具箱。