企业官网建设流程全解析

简介：一份面向编程学习者的C++排序算法实践资源，聚焦随机生成1000个整数后分别用冒泡、插入、选择、快速、归并、堆排序处理，并统计各算法赋值次数以对比效率，适合正在学习数据结构与算法、希望从操作层面理解排序性能的人群。压缩包内仅含1个C++源文件，大小约3KB，代码结构清晰，包含随机数生成、多种排序函数实现以及统计赋值次数的逻辑，便于直接运行和修改。目前已有1627人浏览学习。通过该代码可直观观察不同排序算法在相同数据下的赋值次数差异，同时复习 库用法及算法复杂度等知识点，也可作为扩展实验模板，尝试增加算法变体或数据规模继续测试，是一份紧凑实用的算法练习材料。

1. 为什么排序算法的赋值次数比比较次数更值得看

排序算法课上讲复杂度只看比较次数，但真到压测和选型阶段，赋值次数才是最让人意外的黑匣子。同样是随机生成的 1000 个数字，冒泡和快排都能排完，赋值次数却能差出一个量级：选择排序比较次数固定在 O(n²)，赋值却只有 O(n)；插入排序的赋值随数据有序度剧烈摆动；归并排序比较次数不算少，赋值反而是最稳定的。下面我用固定种子随机生成 1000 个数字，分别跑冒泡、选择、插入、快排、归并五种排序算法，在每次元素赋值的位置插入计数，把赋值次数一点点拆给你看：统计口径怎么定、埋点埋在哪、结果怎么解读，以及统计过程中最容易翻车的五个细节。

2. 准备可复现的随机数据：1000 个数字的三种测试集

2.1 固定种子与唯一值：让每次实验都能重放

排序对比实验的第一步是生成数据。很多人的习惯是rand()裸奔跑一遍，但这样每次拿到的序列都不一样，冒泡这次快、快排下次慢，根本没法归因。我一般会先固定随机种子，保证同一个输入在所有算法面前是完全一致的。

#include <stdio.h> #include <stdlib.h> #define N 1000 void generate_int_array(int arr[], int n, unsigned int seed, int bound) { srand(seed); for (int i = 0; i < n; i++) { arr[i] = rand() % bound; } }

seed是随机种子，bound是取值范围上限。这里arr[i] = rand() % bound是最常见的生成方式，但有个隐患：1000 个数落进 10000 个槽位时，期望重复约 50 个，重复数据会让逆序对数量缩水，赋值次数也跟着缩水。为了得到更干净的随机分布，我倾向于直接生成唯一值。

void generate_unique_array(int arr[], int n) { int pool[10000]; for (int i = 0; i < 10000; i++) pool[i] = i; srand(2024001); for (int i = 9999; i > 0; i--) { int j = rand() % (i + 1); int t = pool[i]; pool[i] = pool[j]; pool[j] = t; } for (int i = 0; i < n; i++) arr[i] = pool[i]; }

这是 Fisher-Yates 洗牌：先把 0 到 9999 的完整序列放进池子，从后往前随机交换，最后取前 1000 个。这样得到的 1000 个数两两不同，随机分布也均匀，逆序对期望值大约在 25 万附近。注意洗牌过程本身也有交换，但那是测试数据生成阶段，不计入排序算法的赋值统计。

2.2 三种测试集：随机、近有序、逆序各考察什么

只测一组随机数据是不够的。赋值次数跟初始有序度高度相关，生产环境里数据往往是局部有序的，所以我会同时准备三组数据：随机、近有序、完全逆序。

近有序数据不是简单地把数组大部分排序，而是让绝大多数元素保持在正确位置上。用代码生成更直观：

void generate_nearly_sorted(int arr[], int n) { for (int i = 0; i < n; i++) arr[i] = i; srand(2024002); for (int k = 0; k < 50; k++) { int a = rand() % n, b = rand() % n; int t = arr[a]; arr[a] = arr[b]; arr[b] = t; } }

先填一个完全有序的数组，再随机挑 50 对位置交换。1000 个元素里只有 100 个左右的位置被扰动，整体逆序对数量很少。这个形态非常接近实际业务里的日志表、按主键插入后少量更新的数据。

2.3 统计口径：什么算一次赋值，什么不算

赋值次数这个指标最容易翻车的地方是口径不一致。我采用的统计口径是：只有「一个数组元素的值被写入另一个位置」才算一次赋值。

具体来说：

• swap(a, b)算三次赋值：tmp = a、a = b、b = tmp。
• 插入排序里的腾挪a[j + 1] = a[j]算一次。
• 归并排序里把元素从临时数组拷回a[l + k] = tmp[k]算一次。
• i++、j--、k++这类循环游标自增不算。
• 快排里pivot = a[r]算一次，因为读取元素并存入局部变量也是一次值传递。

这个口径定下来之后，所有算法才有可比性。

3. 五种排序算法的赋值来源：计数埋点应该放哪

数据结构排序算法课里统计的是比较次数，八大排序算法总结比来比去也比的是比较次数，但赋值次数反映的是元素搬运成本，埋点位置和比较次数的埋点完全不同。下面的代码片段统一用COUNT()表示一次计数，完整的宏定义和可编译版本在下一章给出。

3.1 冒泡与选择排序：交换次数决定赋值总量

冒泡排序的核心操作是相邻交换，一次交换计三次赋值：

// 冒泡排序核心段（示意） if (a[j] > a[j + 1]) { int tmp = a[j]; COUNT(); a[j] = a[j + 1]; COUNT(); a[j + 1] = tmp; COUNT(); }

内层比较总次数是n(n-1)/2，也就是约 49.95 万次，但交换次数并没有那么多。每一次交换会消除恰好一个逆序对，随机数据下交换次数约等于逆序对数 25 万，赋值次数约 75 万；逆序数据直接翻倍到 150 万量级。

选择排序完全是另一副面孔：

// 选择排序核心段（示意） if (min != i) { int tmp = a[i]; COUNT(); a[i] = a[min]; COUNT(); a[min] = tmp; COUNT(); }

每轮外层循环最多触发一次交换，所以 1000 个数据的赋值次数上界就是3 * (n-1) = 2997。不管数据是随机还是逆序，这个数都不变。这就是赋值次数视角和比较次数视角最典型的冲突：选择排序比较次数固定接近 50 万，但赋值次数极低，在元素拷贝成本高的场景里反而可能是赢家。

3.2 插入排序：搬移次数直接等于逆序对数量

插入排序的赋值点有两处：读取当前元素、腾挪时右移元素。

// 插入排序核心段（示意） int key = a[i]; COUNT(); while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; COUNT(); j--; } a[j + 1] = key; COUNT();

key = a[i]算一次，a[j + 1] = a[j]每次右移算一次，最后把 key 写回去再算一次。总赋值次数恰好等于n + 逆序对数。随机数据的逆序对期望值约 25 万，赋值次数大约 25.1 万；逆序数据约 50.1 万；而近有序数据只要几百个逆序对，赋值次数可能只有 1000 出头。插入排序是五种算法里对初始有序度最敏感的，数据越整齐它的赋值成本越低。

这个特性让插入排序在很多工业实现里不是主角，而是快排的小数组收尾工具。当递归切分到 20 个元素以内时，数据已经接近局部有序，插入排序的赋值次数进入线性区间，反而比继续分区更快。

3.3 快排与归并：分治思想把赋值成本摊进递归过程

快排的赋值集中在partition的交换动作上。以最右元素为枢轴的经典写法：

// 快速排序分区段（示意） int pivot = a[r]; COUNT(); for (int j = l; j < r; j++) { if (a[j] < pivot) { i++; int tmp = a[i]; COUNT(); a[i] = a[j]; COUNT(); a[j] = tmp; COUNT(); } } int tmp = a[i + 1]; COUNT(); a[i + 1] = a[r]; COUNT(); a[r] = tmp; COUNT();

pivot = a[r]是一次赋值，分区中的每一次交换是三次。随机数据下交换总次数在十万量级，整体赋值次数大约在 10 万到 30 万之间浮动。但如果数据本身是逆序的，直接用最右元素做枢轴会让递归树退化成链，交换次数逼近n²/2，赋值次数会冲到百万量级，和冒泡一个水平。三数取中能缓解退化，但赋值次数的波动依然远大于归并。

归并排序的赋值是一笔确定性的账：

// 归并排序合并段（示意） while (i <= m && j <= r) { if (a[i] <= a[j]) { tmp[k] = a[i]; COUNT(); k++; i++; } else { tmp[k] = a[j]; COUNT(); k++; j++; } } for (k = 0; k < r - l + 1; k++) { a[l + k] = tmp[k]; COUNT(); }

每层递归大约做n次赋值，总层数是log2(n)，所以 1000 个数据的归并赋值次数稳定在1000 * 10 = 10000左右，几乎不随数据初始有序度变化。分治思想在这里的价值特别明显：归并用确定的搬运次数换来了最稳定的赋值行为，代价是额外的 O(n) 临时空间。堆排序也走交换路线，建堆加 n 次下沉约产生 2n log2 n 量级的赋值，比归并多一些，但胜在空间复杂度 O(1)。

4. 跑通对比实验：C 语言代码与赋值计数输出解读

4.1 评测框架：统一计数器与交换宏

先把计数基础设施搭好。我用一个static long做全局计数器，用宏把赋值语句包装起来。

#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 1000 static long assign_count; #define COUNT() (assign_count++) #define SWAP(x, y) do { \ int tmp = (x); COUNT(); \ (x) = (y); COUNT(); \ (y) = tmp; COUNT(); \ } while (0)

COUNT()是空参数宏，每次调用让assign_count加一。SWAP宏展开后正好三次赋值三次计数。用宏而不是函数，是为了保证计数能落在调用处，而不是躲在函数内部看不见。assign_count用long是因为最坏情况下冒泡赋值接近 150 万，普通int虽然也装得下，但养成用long的习惯更稳妥。

4.2 五个排序函数的完整埋点实现

冒泡排序：

void bubble_sort(int a[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { int tmp = a[j]; COUNT(); a[j] = a[j + 1]; COUNT(); a[j + 1] = tmp; COUNT(); } } } }

这里没有直接用SWAP宏，而是把三次赋值展开写，便于看清楚每个COUNT()到底对应哪个赋值动作。内层循环的比较次数是固定的，但只有比较成立时才触发赋值，所以计数结果能直接反映数据的逆序程度。

选择排序：

void selection_sort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int min = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[min]) min = j; } if (min != i) { int tmp = a[i]; COUNT(); a[i] = a[min]; COUNT(); a[min] = tmp; COUNT(); } } }

注意min = i和min = j是索引赋值，不是元素值搬运，不计数。只有当min != i时才产生一次交换、三次计数。这是选择排序赋值次数远低于其他简单排序的关键。

插入排序：

void insertion_sort(int a[], int n) { for (int i = 1; i < n; i++) { int key = a[i]; COUNT(); int j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; COUNT(); j--; } a[j + 1] = key; COUNT(); } }

key = a[i]是一次赋值，右移腾挪每次计一次，最后写回一次。j--是游标移动，不计数。这个函数埋点后统计出来的赋值次数，理论上等于n + 逆序对数，可以直接用逆序对理论值交叉验证。

快速排序：

int partition(int a[], int l, int r) { int pivot = a[r]; COUNT(); int i = l - 1; for (int j = l; j < r; j++) { if (a[j] < pivot) { i++; int tmp = a[i]; COUNT(); a[i] = a[j]; COUNT(); a[j] = tmp; COUNT(); } } int tmp = a[i + 1]; COUNT(); a[i + 1] = a[r]; COUNT(); a[r] = tmp; COUNT(); return i + 1; } void quick_sort(int a[], int l, int r) { if (l >= r) return; int p = partition(a, l, r); quick_sort(a, l, p - 1); quick_sort(a, p + 1, r); }

枢轴选取会影响partition的交换次数。这里取a[r]计一次赋值，后续每次交换计三次。逆序输入时递归深度退化为 n，交换次数会陡增，这是后面避坑章节要展开的重点。

归并排序，临时数组一次性分配：

void merge(int a[], int l, int m, int r, int tmp[]) { int i = l, j = m + 1, k = 0; while (i <= m && j <= r) { if (a[i] <= a[j]) { tmp[k] = a[i]; COUNT(); k++; i++; } else { tmp[k] = a[j]; COUNT(); k++; j++; } } while (i <= m) { tmp[k] = a[i]; COUNT(); k++; i++; } while (j <= r) { tmp[k] = a[j]; COUNT(); k++; j++; } for (k = 0; k < r - l + 1; k++) { a[l + k] = tmp[k]; COUNT(); } } void merge_sort(int a[], int l, int r, int tmp[]) { if (l >= r) return; int m = (l + r) / 2; merge_sort(a, l, m, tmp); merge_sort(a, m + 1, r, tmp); merge(a, l, m, r, tmp); }

tmp在最外层统一分配，避免在递归里反复malloc。合并阶段每次写入tmp[k]计一次，回拷时每次写入a[l + k]再计一次，所以归并的赋值次数天然是确定性的，分成「写进临时数组」和「写回原数组」两笔账。

4.3 统一入口：每次排序前恢复原始副本

主函数的职责是生成一组随机数据，然后让五个算法分别在这组数据的副本上运行。

void quick_sort_wrapper(int a[], int n) { quick_sort(a, 0, n - 1); } void merge_sort_wrapper(int a[], int n) { int *tmp = malloc(n * sizeof(int)); merge_sort(a, 0, n - 1, tmp); free(tmp); } void run_case(const char *name, int src[], int n, void (*sort_fn)(int[], int)) { int copy[N]; memcpy(copy, src, n * sizeof(int)); assign_count = 0; sort_fn(copy, n); printf("%-12s : %ld\n", name, assign_count); } int main(void) { int base[N]; generate_unique_array(base, N); run_case("bubble", base, N, bubble_sort); run_case("selection", base, N, selection_sort); run_case("insertion", base, N, insertion_sort); run_case("quick", base, N, quick_sort_wrapper); run_case("merge", base, N, merge_sort_wrapper); return 0; }

run_case每次都从base复制一份副本再排序，保证五个算法面对完全相同的初始数组。memcpy和assign_count = 0的执行顺序不能颠倒，否则计数器清零会把上次结果覆盖。generate_unique_array来自第 2.1 节，编译时放到main之前即可。

4.4 结果解读：数量级比精确值更重要

按上述代码和种子跑出来的数值会有细微波动，但数量级是确定的，可以用理论推导交叉验证。

随机数据下最扎眼的是选择排序：比较次数接近 50 万，赋值次数却只有 3000，正因为每轮最多交换一次。插入排序在近有序时只有 1000 次左右的赋值，比选择排序还低，这是它适合做快排收尾的原因。归并排序三列数值都稳定在 1 万附近，如果不关心空间只求稳定，它是首选。快排的赋值次数波动最大，最坏情况下和冒泡同级，所以「快排一定快」这种印象在赋值成本和逆序输入面前并不成立。

5. 赋值次数统计的避坑记录：五个让结论翻车的细节

5.1 计数口径被循环自增加污染

现象：归并排序统计出来的赋值次数超过 10 万，比插入排序还高，和理论完全对不上。

原因：把COUNT()直接放在tmp[k++] = a[i++]这类复合语句后面，k++和i++也会触发计数器累加。归并排序的读写动作都带着游标自增，游标移动被误当成元素赋值，计数瞬间虚高。

解决：赋值表达式单独成行，COUNT()紧跟其后，游标自增放在计数器之后的下一条语句。例如先写tmp[k] = a[i]; COUNT(); k++; i++;，而不是把三条操作挤在一行里。

5.2 排序前没有恢复原始数组

现象：先跑冒泡再跑选择，两组赋值次数几乎一样，而且都明显偏小。

原因：run_case里memcpy的源数据已经被上一次排序改成了有序数组，后续每个算法都在排好序的副本上跑，赋值事件自然变少。最典型的是冒泡跑完把数组排成升序，选择排序再跑一遍几乎不触发交换。

解决：程序里维护一个只生成一次的base主数组，run_case每次排序前从base用memcpy恢复副本，排序只改副本，不改主数组。这也是 4.3 节框架存在的意义。

5.3 随机数范围太小导致重复值泛滥

现象：把rand() % 10000改成rand() % 100生成 1000 个数后，冒泡的赋值次数从 75 万掉到 20 万左右。

原因：值域太小，1000 个数挤在 100 个取值里，大量重复元素让a[j] > a[j + 1]成立的概率大幅降低，交换次数和逆序对数量同时缩水，实验测的其实是「重复数据」而不是「随机数据」。

解决：要么把值域扩大到远大于 n，要么直接采用洗牌生成唯一值。从实验严谨性角度，我建议直接上唯一值方案，避免重复值对后续所有算法造成不可控影响。

5.4 把 swap 封装成函数后计数被隔离在函数体外

现象：冒泡排序的赋值次数恰好是预期值的三分之一，比如 25 万而不是 75 万。

原因：为了代码整洁，把交换抽成了void swap(int *a, int *b)函数，函数内部的三次赋值没有放COUNT()，只在调用swap的地方计了一次数。一次交换本该计三次，却只计了一次，总数自然缩水成三分之一。

解决：交换用宏在调用处展开，保证三次赋值全部落在计数器可见的范围里；或者把COUNT()放进swap函数体内部。前者更直观，也是本章采用的方式。

5.5 归并排序的临时数组在递归里反复分配

现象：同一个种子、同一组数据，归并排序的赋值次数连续跑几次不一致，有时多出几百次波动。

原因：第一版merge_sort把malloc写进递归函数，每个递归层级都申请释放临时数组，堆状态不稳定，而且malloc返回的临时数组内容不确定，调试时容易分不清哪一次赋值是排序本身产生的。

解决：在merge_sort_wrapper里一次性malloc一块长度为 n 的tmp，通过参数一路传进递归，排序结束后统一free。这样临时数组只分配一次，归并的计数完全反映排序逻辑本身，不受内存分配影响。

6. 用赋值次数做选型：不同数据画像下的排序算法取舍

赋值次数统计出来不是用来发论文的，是用来做选型判断的。我的习惯是拿比较次数和赋值次数两张表一起看，数据画像决定算法选择。

随机数据下，快排的比较次数和赋值次数都在可接受区间，选快排没有悬念。近有序数据下，插入排序的赋值次数只有 1000 左右，远低于快排和归并的万级成本，所以遇到「整体有序、局部微调」的数据，插入排序不该被轻视。逆序数据是最有意思的：插入排序和快排同时翻车，赋值次数冲到百万量级，归并排序依然稳稳停在 1 万附近，所以如果系统里会出现大段逆序数据，又不在意那点内存，直接上归并比冒险优化快排的枢轴靠谱得多。

还有一个常被忽略的场景：排序对象不是int，而是几十字节的大结构体。赋值次数在这种场景下直接等于内存拷贝次数，快排的交换操作会把结构体整个搬来搬去，一次交换搬几十字节，代价远高于比较两个整数。这时候选择排序虽然比较了 50 万次，但赋值只有 3000 次，实际跑起来可能比快排还快。程序员不会拿它排大数组，但排百来个小结构体时，它是值得考虑的廉价方案。更通用的做法是对索引或指针排序，排序过程只搬指针，最后再按指针重排原数组，本质上就是把「搬大对象」降级成「搬小指针」。

这是我踩过坑之后留下的习惯：以前选排序只看教科书上的比较次数，后来用一个几十 KB 的结构体数组做压测，快排比归并慢了将近一倍，翻了赋值次数才明白是大量结构体拷贝拖了后腿。现在每次评估排序方案，我一定会把赋值次数当成第二硬指标，和比较次数放在同一张表里看。希望帮到你。

本文还有配套的精品资源，点击获取