企业官网建设流程全解析

排序算法是C++学习路上绕不开的一堵墙：校招笔试会考，日常开发中排序也几乎是最高频的基础操作。但十大排序算法放在一起，原理容易混、代码容易记串、复杂度更容易背错。这篇内容我把十大经典排序算法用C++重写了一遍，并逐项分析它们的原理、完整代码实现、时间复杂度推导和排序稳定性，最后附上工程实践中的选型经验与排查技巧，希望能帮你把这套知识真正串起来。

1. 先有个整体框架：分类、复杂度与稳定性总览

在学习每个算法之前，我建议先把十大排序算法按“时间复杂度阵营”和“稳定性”这两个维度分层，这样后面读代码时脑子才不乱。

1.1 按时间复杂度划分的三个阵营

第一个阵营是O(n²)的基础排序，包含冒泡排序、选择排序、插入排序。它们的实现最简单，适合小规模数据、教学示范，以及作为其他算法的内层辅助。

第二个阵营是O(n log n)的进阶排序，包含希尔排序、归并排序、快速排序、堆排序。它们利用分治或树结构，数据量越大优势越明显，是工程中的主力。

第三个阵营是线性时间排序，包含计数排序、桶排序、基数排序。它们不是通过比较元素大小来排序，而是利用数据本身的取值范围、分布规律或位特征，以空间换时间，但限制条件也最多。

1.2 稳定性到底指什么，为什么重要

判定一个排序算法是否稳定，只需要看一个问题：如果两个元素的值相等，排序前谁在前，排序后是否仍然谁在前。如果顺序不变，就称该算法是稳定的；如果可能变化，就是不稳定的。

为什么要特别在意稳定性？举个实际开发场景：你有一张学生成绩表，先按总分排序，再按班级排序。如果第二次排序算法是不稳定的，那么同一班级内部的总分顺序就会被“打乱”；而稳定排序能保证第二次排序完成后，每个班级内部仍然保留着按总分从高到低的相对顺序。这就是为什么很多数据库索引、多关键字排序场景对稳定性有硬性要求。

1.3 一张表记住全部关键参数

下面是十种排序算法的核心参数总览，建议先通读一遍，再逐个看细节。

其中k表示数据范围或桶的数量，d表示最大数字的位数。快排的平均空间复杂度为O(log n)，原因是递归栈深度。把这些参数放在一起对比，选型和笔试答题时一目了然。

2. O(n²)序列：冒泡、选择、插入，谁才是基础里的王者

三个算法都简单，但各自的特征和使用场景完全不同。我把它们的代码和易错点一起放上来。

2.1 冒泡排序：不停交换的“气泡浮升”

冒泡排序的核心思想是每一轮都从前往后扫描相邻元素，如果前一个比后一个大，就交换。一轮扫描结束后，最大的元素会像气泡一样“浮”到末尾；下一轮继续对剩余部分的n-1个元素进行同样操作。

void bubbleSort(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]) { std::swap(arr[j], arr[j + 1]); swapped = true; } } if (!swapped) { break; } } }

这里有一个很容易被忽略的优化点：swapped标志位。如果某一轮扫描过程中没有任何交换发生，说明整个序列已经有序，可以提前终止。这个优化让冒泡排序在“近乎有序”的数据上可以降到O(n)的复杂度。

冒泡排序只有在arr[j] > arr[j+1]时才交换，相等元素不会被交换位置，所以它是稳定的。时间复杂度方面，最坏情况和平均情况都是O(n²)，但加了提前退出标志后，最好情况是O(n)，空间复杂度O(1)。

注意：冒泡排序在n较小时性能尚可，但数据量超过几千就会明显变慢。它在工程中的主要价值只剩教学和简单场景，比如面试手写、小规模数据排序。

2.2 选择排序：每一轮挑出最值放到前面

选择排序的思想比冒泡更“直接”：每轮找到未排序部分的最小值，和未排序部分的第一个元素交换。第i轮结束后，前i个元素就是全局最小的i个元素。

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) { std::swap(arr[i], arr[minIdx]); } } }

注意代码里的minIdx记录的是最小值下标，而不是直接把值交换过来。这样每轮只做一次交换，比冒泡排序的频繁交换要省操作。

但选择排序的关键问题在于：它不是稳定的。举个反例，数组[5, 3, 5, 1]，第一轮找到最小值1，下标为3，交换arr[0]和arr[3]后，数组变成[1, 3, 5, 5]，原本在前面的第一个5已经被挪到了后面，两个5的相对顺序还是保持的。但换成[3, 5, 3, 1]，第一轮交换后数组变为[1, 5, 3, 3]，原本在前面的3被换到后面，两个3的相对顺序被破坏了。交换操作会把较远的元素移位，所以稳定性不成立。

选择排序的时间复杂度无论数据是否有序都是O(n²)，空间复杂度O(1)，但在数据“已经有序”的输入上没有额外收益。

2.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; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; --j; } arr[j + 1] = key; } }

我写插入排序时常见的一个误区是把arr[j] > key写成>=。一旦写成>=，相等元素会被提前插入到更前面的位置，算法就变得不稳定了。所以稳定性完全取决于比较符号。

插入排序的时间复杂度：最好的情况是数据几乎有序，内层循环基本不执行，整体降到O(n)；最坏和平均情况是O(n²)。这也是为什么许多高级排序算法会在数据规模很小时，或者递归分区后的小数组上改用插入排序——因为小规模下它的常数极小，甚至可以超过部分O(n log n)算法。

2.4 三个O(n²)算法的横向对比

三个基础排序里，最值得用的其实是插入排序，因为它具备两个优势：一是数据基本有序时性能优秀，二是稳定。选择排序虽然比较次数少，但稳定性差，性能也没有比插入排序好；冒泡排序除了实现简单，其他方面基本没有明显优势。

实操心得：手写排序题如果允许选任意排序，我一般选插入排序或快速排序。插入排序代码冗余度最低，不容易写错；快排则有“平均最优”的理论口碑，但细节多，容易在partition边界上踩坑。

3. 进阶排序：希尔、归并、快排、堆排

这部分是笔试和开发中的重头戏，每个算法都值得花时间拆解。

3.1 希尔排序：插入排序的跳跃式增强

希尔排序的出发点是：插入排序在数据基本有序时效率很高。那么能不能先让数据“大致有序”，再逐次缩小增量，最终变成插入排序？希尔排序正是这样做的：设定一个增量gap序列，对相隔gap的元素进行插入排序；不断缩小gap，直到gap为1进行一次标准插入排序。

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 key = arr[i]; int j = i - gap; while (j >= 0 && arr[j] > key) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = key; } } }

上面的写法采用最简单的n/2折半增量序列，code里每轮实际上做了gap路并行的插入排序。希尔排序的时间复杂度分析比较繁琐，因为取决于gap序列的选取。常用的折半序列平均约为O(n^1.3)，某些精心设计的序列可以达到O(n^{3/2})甚至更低，但最坏情况仍是O(n²)。空间复杂度O(1)。

希尔排序是不稳定的。原因在于相等元素距离gap较远时会被移动到不同批次的插入序列中，交换过程可能跨越多个位置，相等的两个数可能被“插”到对方前面。记住：任何“跳跃交换”型排序，稳定性基本都保不住。

3.2 归并排序：分治思想的经典样板

归并排序有两步：先把数组对半拆，直到每个子区间只有一个元素；再不断合并两个有序子区间，让上层区间重新有序。这种“先拆后合”的思路是典型的分治法。

void merge(vector<int>& arr, int left, int mid, int right) { vector<int> temp(right - left + 1); int i = left, j = mid + 1, p = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[p++] = arr[i++]; } else { temp[p++] = arr[j++]; } } while (i <= mid) temp[p++] = arr[i++]; while (j <= right) temp[p++] = arr[j++]; for (int p = 0; p < temp.size(); ++p) { arr[left + p] = temp[p]; } } 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); }

合并操作里判断条件必须用<=，也就是当左半部分的元素等于右半部分时，优先取左半部分。这是归并排序保持稳定性的关键点。如果写成<，相等元素就会优先取右侧元素，稳定性被破坏。

时间复杂度分析：每一轮递归合并需要扫描整个数组，代价为O(n)；递归深度是O(log n)，所以整体是O(n log n)。无论是最好、最坏还是平均情况，都是O(n log n)，这是归并排序最大的优点——不存在快排最坏情况退化的风险。代价是需要额外的O(n)辅助数组。

归并排序在解决“链表排序”以及“外部排序”场景时极其有用，因为它的数据访问是顺序的，不需要随机访问索引，天然适合链表结构和磁盘块顺序读。这也是我建议重点掌握它的原因。

3.3 快速排序：平均最快的随机化版本

快排的思想是：选一个基准值pivot，把数组分成两部分，左边都小于pivot，右边都大于pivot；再对左右两个部分递归地执行同样操作。

快速排序的实现方式非常多，我推荐使用“挖坑法”或“Lomuto分区”。下面这个版本是用“挖坑法”实现的单次partition：

int partition(vector<int>& arr, int left, int right) { int pivot = arr[left]; int i = left, j = right; while (i < j) { while (i < j && arr[j] >= pivot) --j; if (i < j) arr[i++] = arr[j]; while (i < j && arr[i] <= pivot) ++i; if (i < j) arr[j--] = arr[i]; } arr[i] = pivot; return i; } void quickSort(vector<int>& arr, int left, int right) { if (left >= right) return; int pos = partition(arr, left, right); quickSort(arr, left, pos - 1); quickSort(arr, pos + 1, right); }

这段代码有一个极其关键的细节：两个内层while循环里使用的是>=和<=，确保pivot值相等的元素不会无限交换。另一个细节是在递归前可以加入“小区间插入排序”优化：当区间长度小于某个阈值（比如16）时，直接调用插入排序。

快排平均时间复杂度为O(n log n)，空间复杂度为递归栈深度O(log n)。最坏情况发生在每次选择的pivot恰好是区间最小值或最大值，例如对完全有序的数组且每次取最左侧为pivot，这时递归深度退化为O(n)，总时间为O(n²)。解决最坏退化的常规手段是引入随机化：在partition前，把区间内随机一个位置和left位置元素交换后再取pivot。

稳定性方面，快排明显是不稳定的。partition过程会把大量元素跨区间交换，等值元素的位置完全无法保证。

实操心得：手写快排最容易出bug的位置是partition里的边界条件。我见过很多次while (i < j && arr[j] >= pivot)和while (i < j && arr[i] <= pivot)写反，或者忘了在内层加i < j，导致函数陷入死循环或越界。建议写完后用包含大量重复元素和完全有序数组的测试用例验证。

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) { std::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) { std::swap(arr[0], arr[i]); heapify(arr, i, 0); } }

i = n / 2 - 1是从最后一个非叶子节点开始建堆。建堆过程是倒序下沉，复杂度分析起来比表面看起来有趣：每次heapify都从倒数第二层开始，越往上的节点下沉次数越少，但需要下沉最远的节点位于较高的层。整体建堆代价为O(n)，n次取出堆顶后每次需要O(log n)的下沉，总复杂度O(n log n)。堆排序的最坏、平均、最好情况都是O(n log n)，空间复杂度O(1)，这是它最大的优势，适合嵌入式环境或对最坏情况有严格要求的场景。

堆排序也是不稳定的。堆顶与堆尾交换等值元素时，会大幅度改变它们的位置关系，稳定性实在无法保证。

3.5 四种进阶排序怎么选

如果按工程场景选型，规律如下：

• 平均性能最优、常数小：快速排序。数据随机性好时首选。
• 稳定性有硬要求：归并排序，代价是额外O(n)内存。
• 内存受限或不允许额外空间：堆排序。虽然实际常数可能比快排稍大，但最坏情况下依然是O(n log n)。
• 排序链表：归并排序，因为链表不需要额外移动大量数组元素，只需要改指针。

4. 线性时间排序：计数、桶、基数，用空间换时间

如果数据范围整齐、分布有规律，比较排序的O(n log n)下界其实可以被突破。这三个算法就是不走“比较”这条路。

4.1 计数排序：统计每个值出现的次数

计数排序的原理很简单：如果所有数据都是整数且范围在[min, max]内，那么统计每个值出现的次数，再按从小到大的顺序把值依次“放回”数组即可。

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

上面的实现是“简化版”，适合数值范围较小、只需要排序值的场景。但它有一个问题：只排序了值，丢失了稳定性。如需保持稳定（例如对结构体按某个整型字段排序），则需要使用“累加计数+倒序遍历置位”的标准稳定版本：

void stableCountingSort(vector<pair<int, string>>& arr) { int maxVal = 0, minVal = INT_MAX; for (auto& p : arr) { maxVal = max(maxVal, p.first); minVal = min(minVal, p.first); } int range = maxVal - minVal + 1; vector<int> count(range, 0); for (auto& p : arr) { count[p.first - minVal]++; } for (int i = 1; i < range; ++i) { count[i] += count[i - 1]; } vector<pair<int, string>> output(arr.size()); for (int i = arr.size() - 1; i >= 0; --i) { int key = arr[i].first - minVal; output[count[key] - 1] = arr[i]; count[key]--; } arr = output; }

第二段代码的原理是：先累加count数组，让count[key]表示“小于等于该值的元素个数”；然后从原数组末尾倒序遍历，每遇到一个元素就把它放到output的指定位置，同时把对应计数值减一。倒序遍历保证了后面出现的等值元素先放在较后的位置，从而维持原来的相对顺序。

计数排序的时间复杂度是O(n + k)，k是range大小，空间复杂度O(k)。需要注意如果k远大于n，比如n=100但值范围是0到10亿，这个算法就不适用了。

4.2 桶排序：把数据分进多个桶再排

桶排序假设数据在某个范围内均匀分布：把范围切成若干个桶，遍历一遍数据把元素分到对应的桶中，每个桶再用插入排序或其他方法单独排序，最后按桶顺序合并。

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

上面的代码适用于[0,1)区间均匀分布的浮点数。桶的数量和映射规则必须根据数据分布定制，这是桶排序的核心难点：如果数据分布严重不均匀，某些桶中元素数量会很大，排序复杂度就会退化。最坏情况下所有数据都进同一个桶，桶内排序复杂度就是O(n²)。平均情况下每个桶中的元素数量近似n/k，总复杂度为O(n + k)，空间复杂度O(n + k)。

桶排序在一个合理的范围内是稳定的，取决于桶内使用的排序算法是否稳定，以及桶合并时是否保持顺序。只要桶内排序用稳定算法且按桶顺序合并，它就是稳定排序。

实操心得：桶排序写起来不复杂，真正需要花心思的是“界定桶的边界”。比如排序一组年龄数据（18-60岁），可以直接把18到60映射成43个桶；但如果是排序压缩图片的像素值，桶数就要根据灰度范围重新设计。桶排序不是一个“固定代码”，更像一种分治策略。

4.3 基数排序：按位分批处理

基数排序的思路是按数字的每一位从低到高（或从高到低）依次排序。如果每一位都使用稳定的计数排序作为内部排序，那么低位排完之后，高位排的时候会保留低位的有序性，最终整体有序。

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

这里必须强调：基数排序内部依赖的count过程必须是稳定的，倒序遍历put回output是关键，这正是上一小节“稳定版计数排序”的思路。

基数排序的时间复杂度是O(d(n + k))，其中d是最大数字的位数，k=10为每一位可能的取值数量。空间复杂度O(n + k)。基数排序对固定长度的数字类型（如int、long）效果不错，但由于现代处理器的分支和内存访问成本，实际运行效率并不一定比快排高。另外它不能直接排序负数，需要做偏移处理：先把所有数字加上最小值的绝对值，排完再减回去。

4.4 线性排序的适用边界

线性排序是否比O(n log n)更快，取决于k相对于n的大小。当值域大而数据量小时，如n=1000而数字范围是0到20亿，计数排序完全不可用；当n很大但值域很小时（如排序全校几万名学生的年纪，范围只有几十），计数排序是绝佳选择。桶排序则适合处理均匀分布的浮点数据，基数排序适合等宽整数序列。

5. 工程实战：C++里怎么选排序，以及避坑经验

写完手写排序之后，更重要的是知道在真实项目里怎么选现成的排序能力。

5.1 系统自带sort、stable_sort内部机制

实际开发中不要重复造轮子。C++标准库提供了std::sort、std::stable_sort和std::partial_sort，它们通常混用了多种排序策略。std::sort在数据量较大时使用快速排序的变体，在元素较少或分区小于某一阈值时切换到插入排序，在递归深度过深时会切换到堆排序防止退化。这些细节标准没有强制规定，但对大多数实现而言，“快排+插入排序+堆排”的组合已经非常稳健。

std::stable_sort表面上看是归并排序的包装，实际上实现时往往使用“分块+插入排序+归并”的混合策略，在空间充足时使用O(n)额外空间，空间不足时退化为O(n log² n)或更复杂的原地归并方案。

实操心得：如果只是给vector排序，直接用std::sort(v.begin(), v.end())即可；如果要保持相等元素的原始顺序，必须用std::stable_sort。我看到不少项目为了“稳定”把std::sort替换成手写排序，完全没必要，标准库的稳定版本已经足够成熟。

5.2 稳定性是“严重”还是“锦上添花”？多重排序实战

稳定性只有在进行“多重排序”时才真正体现价值。假设需要先按用户等级降序排列，再按注册时间升序排列。正确做法是使用稳定排序，先按注册时间排一次，再按等级排序：因为第二次排序不会打乱注册时间的关系。如果使用不稳定排序，就必须把两个字段打包成一个复合比较函数在单次排序中完成。这时复合比较函数才是更稳妥的方案。

vector<User> users; std::sort(users.begin(), users.end(), [](const User& a, const User& b) { if (a.level != b.level) return a.level > b.level; return a.registerTime < b.registerTime; });

所以在工程里，我更推荐直接用复合比较函数替代对稳定性的依赖。稳定性更多是算法知识层面的要求，而不是所有场景都用得上。

5.3 大数据量场景的取舍与实测建议

当数据量超过几百万时，内存访问模式比时间复杂度更影响真实速度。快速排序虽然平均复杂度在三种O(n log n)算法中不算最优，但它的局部性较好，缓存命中率高，实际表现通常优于堆排序。归并排序需要额外的内存分配与复制，在大数组中会被内存带宽限制，运行时间往往高于快排。建议用随机数据集、有序数据集、重复元素数据集分别测试，不要只依赖理论复杂度下结论。

6. 常见问题与排查技巧实录

结合我实际写排序和带团队时遇到的坑，这里汇总几个高频问题。

6.1 快速排序栈溢出

递归快排处理百万级有序数组时，如果partition选到的pivot总是极端值，递归深度达到O(n)，很容易栈溢出。解决办法有三个：一是用随机pivot降低最坏情况概率；二是递归时先处理短区间，再处理长区间，强制把最坏递归深度限制在O(log n)级别；三是数据量大时改用std::sort，内部实现已经做过深度保护。

6.2 计数排序负数与数据范围问题

直接拿arr[i]作为count下标处理负数是行不通的。处理办法是先遍历一遍数组获取min和max，把所有元素映射到value - min后再统计。另一方面要警惕range过大导致内存爆炸，例如排序10个int且值域达到2³¹，这时不能使用计数排序。

6.3 桶排序桶内排序选择

桶排序里的每个桶用std::sort处理是最省事的。但如果你在写一个对性能要求极高的模块，而且桶内数据近似均匀且元素数量很少，用插入排序反而更快，因为插入排序常数极小。记住：不要为了“高级”盲目选择复杂算法，桶内排序选择insertion并不是矛盾的事。

6.4 用断言和随机测试来验证排序正确性

写完一个排序算法，不要只看少量用例。我习惯写一个测试函数：生成随机数组，先用std::sort得到基准答案，再用自写排序得到结果，逐元素对比；同时额外生成大量重复元素的数组来测试稳定性。这个流程能暴露绝大多数边界问题。以下是简化的验证思路：

bool isValid(vector<int>& data, const vector<int>& expected) { if (data.size() != expected.size()) return false; for (size_t i = 0; i < data.size(); ++i) { if (data[i] != expected[i]) return false; } return true; }

稳定性验证可以借助pair结构：给每个元素附带原始下标，排序后检查等值元素的下标是否递增。这个测试非常重要，因为很多排序算法的“不稳定”问题只有在重复元素较多的场景才会暴露。

6.5 性能对比的注意点

做性能对比时要防止编译器优化掉排序函数。实际测试中建议传入不恒定的随机数列，并把排序结果累加到一个volatile全局变量，避免编译器“看穿”结果后直接把排序代码删掉。数据量级至少准备一万、十万、一百万三档，每档跑多轮取中位数。只跑一两轮受系统调度影响很大，无法反映稳定性能。

我个人在实际操作中的体会是：排序算法不能只背代码，一定要动手实现每一版，再用随机用例做正确性校验。十个算法写一遍的时间不超过两小时，但带来的理解深度远超看十遍。后续如果继续深入，可以研究并行排序、稳定快排的原地实现，或者把排序知识迁移到拓扑排序、K路归并这些扩展方向上。