C++十大排序算法全解析：从冒泡到基数，原理、实现与实战指南

1. 项目概述：为什么排序算法是程序员的必修课？

如果你正在学习C++，或者准备面试，那么“排序算法”这个词你肯定不陌生。它就像编程世界里的“九九乘法表”，看似基础，却无处不在，是衡量一个程序员基本功是否扎实的试金石。我见过太多简历上写着“精通C++”的候选人，在面试时被要求手写一个快速排序，结果要么边界条件处理得一塌糊涂，要么对时间复杂度支支吾吾。所以，今天我们不谈空泛的理论，就实实在在地用C++，把最经典的十大排序算法从头到尾实现一遍，并掰开揉碎了讲清楚每一个细节。

这十大算法，我将其分为两大类：比较类排序和非比较类排序。比较类排序，如冒泡、选择、插入、希尔、归并、快速、堆排序，它们通过元素间的比较来决定次序；非比较类排序，如计数、桶、基数排序，则利用元素的特定属性（如整数值、位数）来排序，在某些场景下能达到惊人的O(n)时间复杂度。本教程的目标是：让你不仅能写出正确的代码，更能理解每种算法背后的思想、适用场景以及那些教科书上不会写的“坑”。我们会从最直观的算法开始，逐步深入到更高效的实现，并提供可直接复制、编译运行的完整代码。

2. 排序算法核心思想与分类总览

在动手写代码之前，我们必须建立一个清晰的认知框架。排序算法的核心评价指标有三个：时间复杂度、空间复杂度和稳定性。

• 时间复杂度：衡量算法执行时间随数据量增长的趋势。O(n²)的算法在小数据量时尚可，数据量一大就力不从心；O(n log n)则是通用高效排序的标杆。
• 空间复杂度：衡量算法运行所需额外内存空间。有的算法是“原地排序”（In-place），只需常数级O(1)额外空间；有的则需要额外开辟与数据量成比例的O(n)空间。
• 稳定性：如果待排序序列中有两个相等的元素，排序后它们的相对次序保持不变，则称该算法是稳定的。这在多关键字排序时至关重要。例如，先按成绩排序，再按学号排序，稳定的排序算法能保证相同成绩的学生依然按学号有序。

基于这些概念，我们可以将十大算法归类如下表。这张表是你选择算法的快速决策指南：

注意：希尔排序的时间复杂度与增量序列的选取密切相关，这里给出的是常见增量序列下的经验值。快速排序的最坏情况（如序列已有序且基准选取不当）会退化为O(n²)，但其在随机数据上的平均性能极佳。

3. 基础排序算法：理解排序的起点

这一部分我们将实现三个最基础的O(n²)算法。它们效率不高，但思想直观，是理解更复杂算法的基石。我强烈建议初学者不要死记硬背代码，而是跟着注释，在纸上画一画每一步数据的变化。

3.1 冒泡排序：最直观的排序方式

冒泡排序就像它的名字一样，每一轮遍历，相邻的两个元素比较，如果顺序错误就交换，这样每一轮都会将当前未排序部分的最大元素“冒泡”到正确位置。

C++实现与解析：

void bubbleSort(vector<int>& arr) { int n = arr.size(); // 外层循环控制排序的轮数，n个元素最多需要n-1轮 for (int i = 0; i < n - 1; ++i) { // 添加一个标志位，用于优化（如果某一轮没有发生交换，说明已有序） bool swapped = false; // 内层循环进行相邻比较。注意边界是 `n-1-i`，因为最后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. 边界条件：内层循环的终止条件是j < n - 1 - i。-1是因为我们比较的是arr[j]和arr[j+1]，防止数组越界。-i是因为经过i轮后，数组末尾的i个元素已经是全局最大的且排好序了，无需再比较。
2. 优化技巧：swapped标志位是一个经典优化。对于近乎有序的序列，可能在中间某一轮就已经完全有序，后续的遍历是徒劳的。这个优化能将最好情况（已有序序列）的时间复杂度降到 O(n)。
3. 稳定性：因为只有在arr[j] > arr[j+1]时才交换，等于时不交换，所以相等元素的相对位置不会改变，冒泡排序是稳定的。

3.2 选择排序：每次找到最小的那个

选择排序的思路非常简单直接：在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾，以此类推。

C++实现与解析：

void selectionSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; ++i) { // i 代表已排序序列的末尾，也是当前要放置最小元素的位置 int minIndex = i; // 假设当前位置的元素就是最小的 // 在 i+1 到 n-1 的范围内寻找真正的最小元素 for (int j = i + 1; j < n; ++j) { if (arr[j] < arr[minIndex]) { minIndex = j; // 更新最小元素的索引 } } // 将找到的最小元素与位置 i 的元素交换 swap(arr[i], arr[minIndex]); } }

实操心得：

1. 不稳定性分析：选择排序是不稳定的。考虑序列[5, 8, 5, 2, 9]。第一轮，最小元素是2，与第一个5交换，序列变为[2, 8, 5, 5, 9]。此时，原来位于索引0的5被交换到了索引2，而原来位于索引2的5留在了后面，两个5的相对顺序被破坏了。
2. 与冒泡排序的区别：冒泡排序每轮可能进行多次交换，而选择排序每轮只进行一次交换。在交换成本很高的场景下（比如排序的元素是非常大的结构体），选择排序可能稍好，但总体而言两者都是低效的O(n²)算法。
3. “原地”排序：它只使用了常数个额外变量（i,j,minIndex），是原地排序。

3.3 插入排序：扑克牌理牌法

插入排序是我们在整理扑克牌时本能使用的方法。将序列的第一个元素看作已排序序列，然后依次将后面的元素插入到前面已排序序列的适当位置。

C++实现与解析：

void insertionSort(vector<int>& arr) { int n = arr.size(); // 从第二个元素开始（索引1），因为第一个元素默认已排序 for (int i = 1; i < n; ++i) { int key = arr[i]; // 当前待插入的元素 int j = i - 1; // 从当前元素的前一个位置开始比较 // 将比 key 大的元素都向后移动一位，为 key 腾出插入位置 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; --j; } // 找到插入位置，放入 key arr[j + 1] = key; } }

实操心得：

1. 近乎有序数据的王者：插入排序在序列“近乎有序”时效率极高，甚至接近O(n)。因为内层的while循环很快会终止。这使得它在一些高级算法（如快速排序、归并排序）处理小子序列时，常被用作优化手段。
2. 稳定排序：在while循环的条件arr[j] > key中，我们只在前面元素大于待插入元素时才移动，等于时不移动。这保证了相等元素的相对顺序，因此插入排序是稳定的。
3. 移动而非交换：注意代码中是arr[j + 1] = arr[j]进行移动，最后才arr[j + 1] = key插入。这比频繁的swap操作（一次swap通常需要三次赋值）效率更高。

4. 进阶比较排序：突破O(n²)的屏障

掌握了基础算法后，我们向更高效的O(n log n)算法进军。这些算法是实际工程中（当数据量较大且没有特殊范围时）的绝对主力。

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

希尔排序是插入排序的改进，由Donald Shell提出。它通过一个逐渐减小的“增量”（gap）将序列分割成若干子序列，分别进行插入排序。随着增量减小，序列整体越来越有序，最后当增量为1时，就是一次标准的插入排序，此时因为序列已基本有序，所以最后一次插入排序会非常快。

C++实现与解析（使用Knuth增量序列）：

void shellSort(vector<int>& arr) { int n = arr.size(); // 1. 计算初始增量（Knuth序列：h = 3*h + 1， 直到 h > n/3） int h = 1; while (h < n / 3) { h = 3 * h + 1; // 1, 4, 13, 40, 121, ... } // 2. 逐步缩小增量进行排序 while (h >= 1) { // 对每个子序列进行插入排序，从第h个元素开始 for (int i = h; i < n; ++i) { // 对 arr[i], arr[i-h], arr[i-2h]... 进行插入排序 int key = arr[i]; int j = i; // 注意这里比较的是 j-h 和 key，移动步长是 h while (j >= h && arr[j - h] > key) { arr[j] = arr[j - h]; j -= h; } arr[j] = key; } // 缩小增量 h /= 3; } }

实操心得：

1. 增量序列的选择：增量序列的选择直接影响算法效率。Knuth序列是实践中效果较好的一个。希尔排序的时间复杂度分析非常复杂，依赖于增量序列，介于O(n log² n)到O(n²)之间，在中等规模数据上表现优异。
2. 不稳定性：希尔排序是不稳定的。因为相同的元素可能被划分到不同的子序列中，在各自的子序列排序时，它们的相对位置可能被打乱。
3. 理解“子序列”：当h=4时，并不是把数组分成4个独立的块分别排序。而是对索引为0,4,8,...、1,5,9,...、2,6,10,...、3,7,11,...的四个子序列分别进行插入排序。代码中的for循环巧妙地实现了这一点，它遍历每个元素，但内层while循环是以h为步长向前比较。

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

归并排序完美体现了“分治法”思想：将一个大问题分解成若干个小问题（递归地将数组分成两半），分别解决小问题（递归排序两个子数组），最后合并小问题的解得到原问题的解（合并两个有序子数组）。

C++实现与解析：

// 合并两个有序子数组 arr[l..m] 和 arr[m+1..r] void merge(vector<int>& arr, int l, int m, int r) { int n1 = m - l + 1; // 左子数组长度 int n2 = r - m; // 右子数组长度 // 创建临时数组 vector<int> L(n1), R(n2); for (int i = 0; i < n1; ++i) L[i] = arr[l + i]; for (int j = 0; j < n2; ++j) R[j] = arr[m + 1 + j]; // 合并回原数组 arr int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { // 注意这里是 <=，保证了稳定性 arr[k] = L[i]; ++i; } else { arr[k] = R[j]; ++j; } ++k; } // 拷贝剩余元素 while (i < n1) { arr[k] = L[i]; ++i; ++k; } while (j < n2) { arr[k] = R[j]; ++j; ++k; } } // 递归排序函数 void mergeSortHelper(vector<int>& arr, int l, int r) { if (l >= r) return; // 递归基：子数组只有一个元素或为空 int m = l + (r - l) / 2; // 防止 (l+r)/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函数的比较条件if (L[i] <= R[j])中，我们使用了<=而不是<。这意味着当左右子数组的元素相等时，我们优先取左子数组的元素。这保证了相等元素的原始相对顺序，因此归并排序是稳定的。
2. 空间复杂度：归并排序需要O(n)的额外空间来存储临时数组L和R。这是它最大的缺点。在实际实现中，可以只分配一个全局的临时数组，避免在递归中反复分配释放，以提升性能。
3. 递归与迭代：上述实现是递归的（自顶向下）。归并排序也可以写成迭代版本（自底向上），避免了递归调用的开销，但代码稍复杂。递归版本更易于理解和教学。
4. 计算中点防溢出：int m = l + (r - l) / 2;是计算中点的安全写法。当l和r都是很大的正数时，(l + r)可能超出int的范围导致溢出，而l + (r - l) / 2则不会。

4.3 快速排序：平均性能的王者

快速排序同样采用分治法，但策略与归并不同。它选择一个元素作为“基准”（pivot），将序列重新排列，所有比基准小的放在前面，比基准大的放在后面（这个过程称为分区）。然后递归地对前后两个子序列进行排序。

C++实现与解析（Lomuto分区法）：

// Lomuto 分区方案 int partition(vector<int>& arr, int low, int high) { int pivot = arr[high]; // 选择最后一个元素作为基准 int i = low - 1; // i 指向小于pivot区域的最后一个元素 for (int j = low; j < high; ++j) { // 如果当前元素小于等于基准，将其交换到小于区域 if (arr[j] <= pivot) { ++i; swap(arr[i], arr[j]); } } // 将基准元素放到正确位置（i+1） swap(arr[i + 1], arr[high]); return i + 1; // 返回基准的最终位置 } void quickSortHelper(vector<int>& arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); // 获取分区点 quickSortHelper(arr, low, pi - 1); // 递归排序左半部分 quickSortHelper(arr, pi + 1, high); // 递归排序右半部分 } } void quickSort(vector<int>& arr) { quickSortHelper(arr, 0, arr.size() - 1); }

实操心得：

1. 基准（Pivot）的选择是灵魂：选择最后一个元素作为基准是最简单的实现，但存在严重问题：如果数组已经有序或逆序，每次分区都会极度不平衡（一个子数组为空），导致递归树退化为链表，时间复杂度恶化到O(n²)。工程实践中，通常采用“三数取中”法：取数组头、中、尾三个元素的中位数作为基准，能有效避免最坏情况。
2. 不稳定性：快速排序在分区过程中会进行非相邻元素的交换，这很容易破坏稳定性。例如序列[3, 2, 2, 1]，以最后一个元素1为基准，分区后两个2的相对顺序可能改变。因此快速排序是不稳定的。
3. Lomuto vs Hoare分区法：上述代码使用的是Lomuto分区法，逻辑清晰但交换次数可能较多。Hoare分区法（使用两个指针从两端向中间扫描）通常效率更高，但边界条件更复杂。面试时能写出Lomuto法通常就够了，但要知道Hoare法的存在。
4. 空间复杂度：快速排序是原地排序，但递归调用需要栈空间。平均情况下栈深度为O(log n)，最坏情况下为O(n)。

4.4 堆排序：利用堆这种数据结构

堆排序利用了“二叉堆”这种数据结构的特性。它首先将待排序序列构造成一个大顶堆（父节点的值大于或等于子节点的值）。此时，整个序列的最大值就是堆顶的根节点。将其与堆数组的末尾元素交换，此时末尾就是最大值。然后将剩余的n-1个序列重新构造成一个堆，如此反复执行，便能得到一个有序序列。

C++实现与解析：

// 调整以节点i为根的子树，使其满足大顶堆性质。n是当前堆的大小。 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(); // 1. 构建大顶堆 (从最后一个非叶子节点开始向上调整) // 最后一个非叶子节点的索引是 n/2 - 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); } }

实操心得：

1. 理解heapify：heapify操作是堆排序的核心，它假设以节点i的左右子树都已经是堆，但i可能小于其子节点。该操作通过“下沉”节点i，使其所在的子树重新满足堆性质。时间复杂度是O(log n)。
2. 建堆的起点：为什么从n/2 - 1开始？因为完全二叉树中，索引从n/2到n-1的节点都是叶子节点（没有子节点），它们本身就是一个合法的堆。所以我们只需要从最后一个非叶子节点开始，自底向上、自右向左地调用heapify即可。
3. 不稳定性：堆排序在交换堆顶和末尾元素时，可能破坏相等元素的相对顺序。例如序列[2, 4, 4]，建堆和交换过程可能导致两个4的相对顺序变化，因此是不稳定的。
4. 优点与缺点：堆排序的时间复杂度稳定在O(n log n)，并且是原地排序，空间复杂度O(1)。但它对缓存（Cache）不友好，因为其跳跃式的访问模式（父子节点索引相差较大），导致在实际运行中通常比快速排序和归并排序慢。

5. 非比较排序：当数据有特殊范围时

当待排序的数据是整数，并且范围（最大值与最小值的差值）不是特别大时，非比较排序算法可以突破O(n log n)的理论下限，达到线性时间复杂度O(n)。

5.1 计数排序：统计频率的艺术

计数排序不是通过比较来排序，而是通过统计每个元素出现的次数（频率），然后根据频率直接计算出每个元素在输出数组中的最终位置。

C++实现与解析：

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]++; // 将值映射到计数数组的索引 } // 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; // 当前元素在计数数组中的索引 // count[idx] - 1 就是该元素在输出数组中的正确位置 output[count[idx] - 1] = arr[i]; count[idx]--; // 放置一个元素后，该位置计数减一 } // 5. 将排序结果拷贝回原数组 arr = output; }

实操心得：

1. 处理负数与偏移量：经典计数排序假设元素是非负整数。为了支持负数，我们通过num - minVal将所有元素映射到从0开始的范围。这是处理任意整数（包括负数）的关键技巧。
2. 稳定性与反向遍历：计数排序是稳定的，这归功于第4步的反向遍历。当我们从后向前遍历原数组时，对于值相同的元素，后出现的会被放在输出数组中靠后的位置（因为count[idx]在递减），从而保持了它们原有的相对顺序。如果正向遍历，稳定性会被破坏。
3. 空间消耗：计数排序需要两个额外数组：count数组（大小=值范围range）和output数组（大小=n）。当值范围range远大于数据量n时（例如排序[1, 1000000]两个数），空间浪费极大，此时不适合使用计数排序。
4. 只能用于整数：计数排序直接操作元素的值作为数组索引，因此只能用于排序整数（或可映射为整数的类型，如字符）。

5.2 桶排序：分而治之的线性尝试

桶排序是计数排序的推广。它假设输入数据均匀分布在一个范围内，然后将该范围划分为若干个大小相同的子区间，称为“桶”。将数据分到各个桶中，每个桶再单独排序（可以使用其他排序算法，如插入排序），最后按顺序将各个桶中的元素连接起来。

C++实现与解析：

void bucketSort(vector<float>& arr) { // 桶排序常用于浮点数 if (arr.empty()) return; int n = arr.size(); float maxVal = *max_element(arr.begin(), arr.end()); float minVal = *min_element(arr.begin(), arr.end()); // 1. 初始化桶。桶的数量通常等于元素数量。 int bucketNum = n; vector<vector<float>> buckets(bucketNum); // 2. 将元素放入对应的桶中 float bucketRange = (maxVal - minVal) / bucketNum; for (float num : arr) { // 计算元素应该放入哪个桶 int bucketIdx = (int)((num - minVal) / bucketRange); // 防止最大值被放到最后一个桶之外 if (bucketIdx == bucketNum) bucketIdx = bucketNum - 1; buckets[bucketIdx].push_back(num); } // 3. 对每个桶内部进行排序（这里使用标准库的排序，实践中可用插入排序） for (auto& bucket : buckets) { sort(bucket.begin(), bucket.end()); // 稳定排序保证整体稳定 } // 4. 将排序后的桶依次连接起来 int index = 0; for (const auto& bucket : buckets) { for (float num : bucket) { arr[index++] = num; } } }

实操心得：

1. 适用场景：桶排序在数据均匀分布时效率最高，能达到O(n)。如果所有数据都集中在一个桶里，则退化为桶内使用的排序算法（如O(n log n)的排序），性能变差。
2. 桶的数量与大小：桶的数量通常取元素个数n，这样平均每个桶有一个元素。桶的范围bucketRange根据数据范围动态计算。
3. 稳定性：桶排序的稳定性取决于桶内排序所使用的算法。如果使用稳定的排序算法（如插入排序、归并排序）对每个桶排序，并且元素放入桶中的顺序是稳定的（代码中按遍历顺序放入，是稳定的），那么整个桶排序就是稳定的。
4. 浮点数排序：桶排序非常适合用于在[0, 1)范围内均匀分布的浮点数排序。此时，可以直接用int(num * n)作为桶索引，非常高效。

5.3 基数排序：按位排序的巧思

基数排序是一种非比较的整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别进行排序。通常使用最低位优先（LSD）法：先从最低位开始排序，然后依次向高位进行。每一位的排序必须是稳定的，否则整个算法无效。

C++实现与解析（LSD，基于计数排序）：

// 获取数组中最大元素的位数 int getMaxDigits(vector<int>& arr) { int maxVal = *max_element(arr.begin(), arr.end()); int digits = 0; while (maxVal > 0) { digits++; maxVal /= 10; } return digits; } // 对数组arr按照某一位（exp=1,10,100...）进行计数排序 void countingSortForRadix(vector<int>& arr, int exp) { int n = arr.size(); vector<int> output(n); int count[10] = {0}; // 十进制数字，范围0-9 // 统计当前位（(arr[i]/exp)%10）上每个数字的出现次数 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]; } // 反向遍历，根据当前位将元素放入output数组（保证稳定性） 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 maxDigits = getMaxDigits(arr); // 从最低位（个位）开始，依次向高位排序 for (int exp = 1; exp <= pow(10, maxDigits - 1); exp *= 10) { countingSortForRadix(arr, exp); } }

实操心得：

1. 稳定性是生命线：基数排序要求每一位的排序算法必须是稳定的。代码中使用了稳定的计数排序作为子程序。如果子排序不稳定，高位的排序会打乱低位已排好的顺序，导致整个排序失败。
2. LSD vs MSD：我们实现的是LSD（Least Significant Digit first）方法，从最低位开始排序。还有MSD（Most Significant Digit first）方法，从最高位开始，采用分治递归的思想，类似于字符串的字典序排序。LSD实现更简单直观。
3. 时间复杂度：设最大数字有k位，每轮计数排序是O(n+10) ≈ O(n)，总共k轮，所以时间复杂度是O(k*n)。当k远小于log n时（例如排序一百万以内的数字，k<=6），基数排序比O(n log n)的比较排序更快。
4. 适用范围：基数排序只能用于可以按位分割的类型，如整数、字符串（按字符排序）。对于负数，需要先将所有数加上一个偏移量变为非负数，排序后再减回去，或者修改计数排序的逻辑以支持负数索引。

6. 算法对比与实战选择指南

学完了所有算法，我们最终要回答一个问题：在实际项目中，我该用哪个？死记硬背结论没用，我们要理解选择背后的逻辑。

性能对比总结表：

C++ STL中的排序：

• std::sort： 通常是一种混合排序算法（IntroSort），结合了快速排序、堆排序和插入排序，在大部分情况下是最佳选择。它不是稳定的。
• std::stable_sort： 保证稳定性的排序，通常基于归并排序实现。当需要保持相等元素相对顺序时使用它。
• std::partial_sort： 部分排序，例如只找出前k个最小的元素，基于堆排序实现。

面试手撕代码高频点：

1. 快速排序： 必须掌握。能写出分区函数，并清楚最坏情况如何避免（随机化基准或三数取中）。
2. 归并排序： 必须掌握。能写出合并两个有序数组的函数，理解递归和迭代两种写法。
3. 堆排序： 必须掌握。能写出heapify函数和建堆过程。
4. 冒泡/选择/插入排序： 虽然简单，但常作为考察对基础算法理解程度的题目。

7. 常见问题与调试技巧实录

在实际实现和面试中，总会遇到一些坑。这里记录了我踩过的一些雷和解决方法。

问题1：快速排序递归栈溢出

• 现象： 对大型有序数组排序时程序崩溃。
• 原因： 基准选择不当（如总是选第一个或最后一个），导致递归树极度不平衡，深度接近n，栈溢出。
• 解决：
  1. 三数取中法选择基准。
  2. 尾递归优化： 先递归处理较短的那部分子数组。

  void quickSortHelper(vector<int>& arr, int low, int high) { while (low < high) { int pi = partition(arr, low, high); // 总是先处理小的那部分，大的部分通过循环迭代 if (pi - low < high - pi) { quickSortHelper(arr, low, pi - 1); low = pi + 1; } else { quickSortHelper(arr, pi + 1, high); high = pi - 1; } } }

  3. 当子数组规模小于某个阈值（如16）时，切换到插入排序。

问题2：归并排序空间复杂度优化

• 现象： 每次合并都创建新数组，内存分配开销大。
• 解决： 在整个排序过程中只使用一个全局的临时数组temp，避免反复分配。

  void mergeSortHelper(vector<int>& arr, vector<int>& temp, int l, int r) { if (l >= r) return; int m = l + (r - l) / 2; mergeSortHelper(arr, temp, l, m); mergeSortHelper(arr, temp, m + 1, r); // 合并时使用temp数组 merge(arr, temp, l, m, r); } void mergeSort(vector<int>& arr) { vector<int> temp(arr.size()); // 一次性分配 mergeSortHelper(arr, temp, 0, arr.size() - 1); } // merge函数也需要修改，将结果先存入temp，再拷贝回arr

问题3：堆排序中heapify的循环条件

• 易错点： 在heapify函数中，判断子节点是否存在时，条件是left < n和right < n，这里的n是当前堆的有效大小，而不是原数组大小。在排序的第二阶段，n是逐渐减小的（i）。

问题4：非比较排序的边界处理

• 计数排序： 计算range = maxVal - minVal + 1时，+1很容易被忽略，导致数组大小少1。
• 桶排序： 计算桶索引int((num - minVal) / bucketRange)时，对于最大值maxVal，计算结果可能等于bucketNum，需要特殊处理if (bucketIdx == bucketNum) bucketIdx = bucketNum - 1;。
• 基数排序： 获取最大位数时，如果数组中有0，getMaxDigits函数会返回0，导致循环不执行。需要处理maxVal == 0的情况，直接返回1。

调试技巧：

1. 单元测试： 为每个排序函数编写测试用例，包括：空数组、单元素数组、已排序数组、逆序数组、包含重复元素的数组、随机数组。
2. 可视化： 对于小数组，在关键步骤（如交换、插入、合并）后打印数组状态，能最直观地发现逻辑错误。
3. 使用STL验证： 在测试时，可以用std::sort对同一份数据排序，然后与你实现的函数结果逐元素比较。
4. 性能对比： 生成大规模随机数据，用<chrono>库计时，对比不同算法的实际运行时间，加深对时间复杂度的理解。

最后，我的建议是，不要满足于“写出能跑的代码”。多问几个为什么：为什么这个算法不稳定？为什么这里要反向遍历？这个边界条件是怎么来的？当你把这些问题都搞清楚了，这些算法才真正属于你。在面试中，面试官也恰恰是通过这些细节来考察你的理解深度。把这些代码和原理吃透，无论是应对面试，还是在实际开发中做出正确的技术选型，你都会更有底气。