企业官网建设流程全解析

欢迎阅读本篇学习笔记。
本篇作为个人计算机专业的学习记录，这里将系统梳理关于各类排序的相关知识点，从基础概念到代码实现逐步展开，已便于后续的复习巩固。如有不足，欢迎大家在评论区交流指正，感谢大家的阅读与支持！

一、什么是排序？

排序，说白了就是给一群乱糟糟的数据选手安排名次。 就像班级考试排成绩、游戏天梯算段位，给定一个规则（升序或者降序），让无序序列变得井然有序。

别小看这个操作，它几乎是所有数据处理里最常用的操作。数据库查询、排行榜、电商商品筛选，背后都藏着排序算法在默默打工。

1.1 排序的稳定性

稳定性算是期末、考研选择题的常驻考点，也是很多人容易记混的地方。

大白话解释：

如果两个元素关键字的值相等，排序之后，它们原本的先后顺序不变，这个算法就是稳定排序。反之就是不稳定。

举个生活化例子帮助理解： 现在有两个同分的考生，甲排在乙前面。 稳定排序：排完名次，甲依旧在乙前面，不会随便调换两人位置。 不稳定排序：哪怕分数相同，算法也有可能把乙换到甲前面，打乱原本的相对顺序。

✨小提醒：稳定性不是代表算法更好，只是它的一个特性，不同场景有不同需求。

1.2 内部排序 和 外部排序

这一对概念区分起来很简单，核心看数据能不能全部塞进内存。

• 内部排序所有待排序的数据全部加载进内存，所有比较、交换操作都在内存完成。我们待会学习的八大排序，全部属于内部排序。内存读写速度飞快，处理起来酣畅淋漓。
• 外部排序当数据量过于庞大，内存放不下全部数据，数据主体保存在硬盘。排序时需要不断在外存和内存之间来回搬运数据。 海量日志、超大文件排序就会用到它，代价就是速度会慢不少。

1.3常见的排序算法

这张思维导图一次性亮出了本次排位赛里所有算法选手。 排序算法分为四大门派：插入、选择、交换、归并。门下每位选手各有独门心法，行事风格迥然不同，有的循序渐进、稳妥内敛，有的大刀阔斧、效率惊人。 我们将围绕着几个排序展开。

二、插入排序

插入排序是四大门派里最朴实的一支，理解起来就像我们打牌理牌的过程。门下共有两位选手：直接插入排序与希尔排序。

2.1直接插入排序

2.1.1基本思想

直接插入排序的思路十分贴近生活：逐个取出待排序元素，将它插入前方已经排好的有序序列中，反复操作，直到全部元素插入完成，整个序列也就有序。最经典的类比就是摸扑克牌，手里保留已经理好的牌，每拿到一张新牌，就找到合适位置插入。

2.1.2执行逻辑

假设数组前 i 个元素已经构成有序区间。取出第 i+1 个元素，从后往前依次和有序区间元素对比。如果有序区间的元素更大，就将元素向后挪动，腾出空位；不断向前查找，直到找到插入位置，把元素放入。循环往复，完成全部排序。

2.1.3特性总结

1. 数组越接近有序，直接插入排序效率越高，近乎有序是它的优势场景。
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，原地排序，额外空间开销极小。
4. 稳定性：稳定排序，相同关键字元素不会打乱原有相对次序。

小评：代码简洁好实现，在数据基本有序时表现亮眼。但面对高度无序数组，大量元素移动会严重拖慢效率。

// 直接插入排序 C语言实现 void InsertSort(int* arr, int n) { for (int i = 1; i < n; i++) { int tmp = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > tmp) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = tmp; } }

好比arr[0 ~i-1]是已经理好的有序手牌；arr[i]是新摸来的牌。 我们拿新牌tmp，从手牌末尾往前挨个比较，把所有比新牌大的牌往后挪，直到找到位置把新牌插进去。

2.2 希尔排序（缩小增量排序）

希尔排序是直接插入排序的改良进阶版，解决了原版插入排序在乱序数组中大量移动元素的短板。

2.2.1基本思想

希尔排序不再一次性对整个数组做插入排序。它先选定间隔gap，将下标相差gap的元素划为一组，在组内执行插入排序；随后不断缩小gap，重复分组排序。当gap最终缩减至 1 时，等价于一次全局直接插入排序。经过前面多轮预排序，数组已经趋近有序，最后一轮排序的开销会大幅降低。

2.2.2执行逻辑

例如初始gap = 5，间隔为 5 的元素分为一组，组内做插入排序；再缩小gap = 2，继续分组排序；直到gap = 1，完成最后的插入排序，数组整体有序。

2.2.3特性总结

1. 核心思路：通过多轮分组预排序，让数组逐步接近有序，优化直接插入排序的效率。
2. 时间复杂度不固定，和增量序列强相关；Knuth 增量序列下约 O(n^1.25）。
3. 空间复杂度：O(1)
4. 稳定性：不稳定排序。

💡小提醒：

希尔排序的时间复杂度分析是一大难点，其性能高度依赖增量序列gap的选取，至今没有通用的严谨数学推导，属于数据结构里尚未完全解决的数学问题。

gap存在多种经典取法：Shell 最初提出每次取gap = ⌊n/2⌋，不断折半直到gap=1；Knuth 则推荐gap = ⌊gap/3⌋ + 1。不同方案各有支持者，但没有哪一种能够被严格证明为最优。

采用 Knuth 增量序列时，大量实验统计表明，当数据规模n很大，关键字平均比较与移动次数约在 n^1.25 ~ 1.6n^1.25 区间，我们一般记时间复杂度为O(n^1.25)。

// 希尔排序 C语言实现（Knuth增量序列） void ShellSort(int* arr, int n) { int gap = n; while(gap > 1) { gap = gap / 3 + 1; for(int i = gap; i < n; i++) { int tmp = arr[i]; int j = i - gap; while(j >= 0 && arr[j] > tmp) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = tmp; } } }

代码简析： 外层循环不断更新增量 gap；从下标 gap 开始遍历数组，取出待插入元素tmp。向前跨 gap 距离比较，更大的元素向后挪动，最后将元素插入对应位置。

门派小结 直接插入排序是根基，简单稳妥，偏爱有序数组；希尔排序借助分组预排序提速，代价是丢失了稳定性。插入门派两位选手到此介绍完毕。

三、交换排序

交换排序的核心，在于通过元素之间的两两比较与交换，逐步把序列调整为有序。

它和插入、选择的思路不同：插入排序强调 “找到位置插入”，选择排序强调 “选出最值放到指定位置”，而交换排序更像是让元素在不断比较中 “碰撞换位”，一路交换到自己该在的地方。

交换排序门下最典型的两位选手，分别是冒泡排序与快速排序。

3.1 冒泡排序

3.3.1基本思想

冒泡排序是交换排序中最直观的一种。

它重复遍历待排序序列，依次比较相邻两个元素。如果前面的元素比后面的元素更大，就交换二者位置。这样一来，每一轮遍历结束后，当前未排序区间中的最大值就会像气泡一样 “浮” 到序列末尾。

这个过程不断重复，直到某一轮遍历中没有发生任何交换，说明序列已经有序，可以提前结束。

3.3.2执行逻辑

以升序排序为例：

1. 从下标 0 开始，依次比较相邻元素arr[j]和arr[j + 1]。
2. 若arr[j] > arr[j + 1]，交换两者。
3. 每一轮结束后，当前未排序部分的最大值会被推到末尾。
4. 下一轮只需在前n - 1个元素中继续比较。
5. 若某一轮没有发生交换，说明数组已有序，直接退出。

代码实现

void BubbleSort(int* arr, int n) { for (int i = 0; i < n - 1; i++) { int flag = 0; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = 1; } } if (flag == 0) break; } }

代码简析

• i表示已经完成排序的轮数。
• 每一轮中，j从前往后比较相邻元素。
• n - 1 - i表示后面i个元素已经有序，无需再比较。
• flag用于标记本轮是否发生交换；若没有交换，说明数组已有序，提前结束。

3.3.3特性总结

1. 每一轮都会把当前未排序区间的最大值放到末尾。
2. 加入flag提前判断后，最好情况为O(N)。
3. 最坏时间复杂度：O(N^2)。
4. 平均时间复杂度：O(N^2)。
5. 空间复杂度：O(1)。
6. 稳定性：稳定排序。

💡小提醒：冒泡排序最好情况是数组已有序，此时只需扫描一轮即可结束；但如果没有提前判断，即使数组有序也会执行完整的O(N^2)。

3.2快速排序

门派小引：交换门派的王牌选手来了！和冒泡那种一点点挪元素的笨办法不同，快排靠着分治大法，一次划分就能让基准元素直接坐到它最终的正确位置，也是工程代码里出场率最高的排序算法。

3.2.1 基本思想

快速排序由 Hoare 在 1962 年提出，是基于分治思想的交换排序。核心逻辑：在待排序区间选取一个基准值pivot，划分区间，让基准左边所有元素 ≤ pivot，基准右边所有元素 ≥ pivot；基准元素归位后，再递归对左右两个子区间重复划分，直到子区间元素个数≤1，整体有序。

3.2.2 执行逻辑

递归主框架

// 对array数组[left, right]区间升序排序 void QuickSort(int array[], int left, int right) { if(right - left <= 1) return; // 划分，得到分割点div int div = partion(array, left, right); // 递归排左区间 [left, div] QuickSort(array, left, div); // 递归排右区间 [div+1, right] QuickSort(array, div+1, right); }

代码简析

递归框架和二叉树前序遍历高度相似。先做划分（根节点处理），再递归处理左子区间、右子区间。快速排序的难点不在递归框架，而在partion划分函数。

三种经典划分方式

1. Hoare 版本（原始左右双指针法）思路：左指针 L 从区间最左向右走，找大于基准的元素；右指针 R 从区间最右向左走，找小于基准的元素。两个指针停下后交换元素，持续直到两指针相遇，相遇位置就是基准的落脚点。

• 基准一般取区间最左端
• R 先移动，L 后移动
• 相遇点的值一定 ≤ pivot，交换基准与相遇位置，完成划分2.

2.挖坑法将区间第一个元素存入临时变量key，原位置变成坑位。 右指针 R 向左查找，找到小于key的元素，填入坑内，该元素原来位置变成新坑。 左指针 L 向右查找，找到大于key的元素，填入当前坑，更新坑位。 循环往复直到 L、R 相遇，最后将key填入最后的坑中，基准归位。

直观理解：不断移动坑的位置，把不符合大小规则的元素填进坑里，最终基准落在坑点。

3.前后指针版本（prev/cur）prev指向小于 pivot 区域的末尾；cur作为探索指针，从头向后遍历。cur找到比 pivot 小的元素时，prev++，交换prev和cur位置元素。cur持续向前扫描，遍历结束后，交换prev与基准元素，基准就位。

优点：代码逻辑简单，适合链表实现快速排序。

快速排序优化方案

原生快排如果每次选到极差基准（有序数组取端点），时间复杂度退化到O(N^2)，工程上常用下面两种优化：

1. 三数取中法选基准：取区间左端、右端、中间位置三个数，选三者的中位数作为 pivot。避免选到最大 / 最小值，防止划分极度不均衡。
2. 小区间改用直接插入排序递归拆分到子区间长度很小的时候，递归调用的开销大于排序开销。当区间长度小于阈值（一般取 7），直接使用插入排序代替快排。

#define MAX_LENGTH_INSERT_SORT 7 // 数组长度阈值 void QSort(SqList &L, int low, int high) { int pivot; if ((high-low) > MAX_LENGTH_INSERT_SORT) { pivot=Partition(L,low,high); QSort(L, low, pivot-1); QSort(L, pivot+1, high); } else InsertSort(L); //小区间，插入排序 }

快速排序 非递归版本

递归会使用函数调用栈，数据量极大时有栈溢出风险。可以手动用栈模拟递归，保存待排序区间[left,right]，循环取出区间进行划分，再把划分后的子区间入栈。

void QuickSortNonR(int* a, int left, int right) { Stack st; StackInit(&st); StackPush(&st, left); StackPush(&st, right); while (StackEmpty(&st) != 0) { right = StackTop(&st); StackPop(&st); left = StackTop(&st); StackPop(&st); if(right - left <= 1) continue; int div = PartSort1(a, left, right); //右区间入栈 StackPush(&st, div+1); StackPush(&st, right); //左区间入栈 StackPush(&st, left); StackPush(&st, div); } StackDestroy(&st); }

代码简析

栈用来存储待处理区间边界。每次弹出一组左右边界，执行划分；再把划分得到的左右子区间继续压栈，循环直到栈空，完成排序。

3.2.3 特性总结

• 核心思想：分治，选取基准划分区间，基准元素直接落到最终位置，递归处理左右子区间。
• 最好时间复杂度：O(Nlog N)
• 平均时间复杂度：O(Nlog N)
• 最坏时间复杂度：O(N^2)
• 空间复杂度：O(log N)，来自递归调用栈；非递归版本同样需要栈保存区间边界。
• 稳定性：不稳定排序。

💡小提醒：快速排序虽然平均效率很高，但如果每次划分都极不均衡，例如数组已有序且固定取端点作为 pivot，时间复杂度会退化到 O(N^2)。

📜门派小结 ：冒泡排序是交换排序里的基础选手，依靠相邻元素两两交换，像气泡一样把大数逐步推到尾部；而快速排序是交换门派的王牌，依靠分治划分，一次划分就能让基准一步到位归位，平均性能远高于冒泡。交换排序两位选手，就介绍到这里。

四、归并排序

门派小引：如果说快排是分治门派的激进派，那归并排序就是分治门派的稳健派。它不搞基准划分的 “一步归位”，而是走先拆后合的路线，用最稳妥的方式完成排序，也是外排序场景的首选选手。

4.1 基本思想

归并排序（MERGE-SORT）是建立在归并操作上的排序算法，是分治法（Divide and Conquer）的典型应用。 核心逻辑：先让每个子序列各自有序，再将两个有序子序列合并成一个完整的有序序列，这个两两合并的操作称为二路归并。整个过程分为两大核心步骤：先分解、后合并。

4.2执行逻辑

整个归并过程分为「分解」和「合并」两个阶段：

• 分解阶段从原始数组开始，不断从中间位置对半切分，拆分为左右两个子区间；递归执行拆分，直到每个子区间内只剩 1 个元素（单个元素天然就是有序的）。
• 合并阶段从最小的有序单元开始，将两个有序小数组合并成一个更长的有序数组；逐层向上重复合并操作，最终合并为完整的有序数组。我们就用图里的例子[10, 6, 7, 1, 3, 9, 4, 2]，完整走一遍流程。

1. 第一步：分解（从上往下拆）

   从原始数组开始，每次从中间切开，一分为二：

2. 第 1 层：[10,6,7,1,3,9,4,2]→ 拆成[10,6,7,1]和[3,9,4,2]
3. 第 2 层：继续拆 →[10,6]、[7,1]、[3,9]、[4,2]
4. 第 3 层：再拆 →[10]、[6]、[7]、[1]、[3]、[9]、[4]、[2]
5. 拆到每个数组只剩 1 个元素，分解阶段结束。
6. 左指针指 1，右指针指 2 → 取 1，左指针后移
7. 左指针指 6，右指针指 2 → 取 2，右指针后移
8. 左指针指 6，右指针指 3 → 取 3，右指针后移
9. 左指针指 6，右指针指 4 → 取 4，右指针后移
10. 左指针指 6，右指针指 9 → 取 6，左指针后移
11. 依次取 7、9、10 最终合并结果：[1, 2, 3, 4, 6, 7, 9, 10]
12. 最底层：[10]&[6]→ 合并成[6,10]；[7]&[1]→[1,7]；[3]&[9]→[3,9]；[4]&[2]→[2,4]
13. 上一层：[6,10]&[1,7]→ 合并成[1,6,7,10]；[3,9]&[2,4]→[2,3,4,9]
14. 最顶层：[1,6,7,10]和[2,3,4,9]合并 → 最终[1,2,3,4,6,7,9,10]

// 归并排序递归实现 void MergeSort(int* arr, int left, int right, int* tmp) { if(left >= right) return; int mid = (left + right) / 2; // 递归拆分排序左右区间 MergeSort(arr, left, mid, tmp); MergeSort(arr, mid + 1, right, tmp); // 二路归并：合并两个有序区间 int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int idx = left; while(begin1 <= end1 && begin2 <= end2) { if(arr[begin1] <= arr[begin2]) tmp[idx++] = arr[begin1++]; else tmp[idx++] = arr[begin2++]; } // 拷贝剩余元素 while(begin1 <= end1) tmp[idx++] = arr[begin1++]; while(begin2 <= end2) tmp[idx++] = arr[begin2++]; // 有序数据拷贝回原数组 for(int i = left; i <= right; i++) arr[i] = tmp[i]; }

代码简析

递归先完成左右子区间的排序，再借助临时数组完成二路归并。每次比较两个子数组的头部元素，更小的优先放入临时空间，最后把剩余元素依次补齐，再写回原数组。

4.3 特性总结

1. 时间复杂度：O(Nlog N)，无论最好、最坏、平均情况复杂度一致，性能不受原始数据有序程度影响。
2. 空间复杂度：O(N)，需要额外开辟临时数组存储归并数据，这是它最主要的缺点。
3. 稳定性：稳定排序，相等元素的相对顺序在归并过程中不会被打乱。
4. 适用场景：尤其适合磁盘外排序，当数据量过大无法全部载入内存时，归并排序是主流方案。

📜 门派小结 ：归并排序和快速排序同属分治家族，但路线截然不同。快排先划分再递归，平均速度更快但最坏情况会退化；归并先拆分再合并，时间复杂度始终稳定，还能保证排序稳定，代价是需要额外的内存空间。

五、选择排序

门派小引：选择排序门派的行事风格非常直接 —— 不搞插入挪动，也不搞两两交换冒泡，每一轮只干一件事：从剩余元素里挑出最值，直接送到它该去的位置。门下两位选手，一位是简单直白的直接选择排序，一位是借助堆结构升级的堆排序。

5.1 直接选择排序

5.1.1 基本思想

直接选择排序是选择排序最朴素的实现。每一轮遍历未排序区间，找到关键字最小的元素，将它与未排序区间的第一个元素交换位置；有序区间从左向右逐步扩大，直到覆盖整个数组。

5.1.2 执行逻辑

1. 初始状态：有序区间长度为 0，未排序区间为整个数组[0, n-1]。
2. 第i轮排序（i 从 0 开始）：在未排序区间[i, n-1]中遍历，找到最小值的下标。
3. 将最小值元素与未排序区间的首元素arr[i]交换，此时arr[i]加入有序区间。
4. 重复上述步骤，直到未排序区间只剩 1 个元素，排序完成。

// 直接选择排序 C语言实现 void SelectSort(int* arr, int n) { for(int i = 0; i < n - 1; i++) { int min_idx = i; // 记录最小值下标 for(int j = i + 1; j < n; j++) { if(arr[j] < arr[min_idx]) min_idx = j; } // 交换最小值和未排序区第一个元素 int tmp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = tmp; } }

5.1.3 特性总结

1. 思路非常直观好理解，但整体效率不高，实际工程中很少使用。
2. 时间复杂度：O(N^2)，无论数组是否有序，都需要完整遍历找最小值。
3. 空间复杂度：O(1)，原地排序，额外空间开销极小。
4. 稳定性：不稳定排序，跨位置的交换操作可能打乱相同关键字元素的相对顺序。

5.2 堆排序

门派小注：堆排序本质还是选择排序。直接选择排序是每次遍历整个数组找最大值，堆排序用「大顶堆」快速锁定最大值，省去一遍遍全数组扫描

想要看懂堆排序流程，首先得认识这个核心工具 —— 大顶堆。这里很多人会产生疑问：我们最终目标是升序，为啥不用小顶堆直接拿最小值？看完堆的定义，我们再来解答这个经典疑问。

5.2.1什么是大顶堆

大顶堆是一棵完全二叉树，父节点的值 ≥ 左右孩子节点。 堆顶（树根）永远是整个堆里面最大的数字。 数组可以直接映射成完全二叉树，不需要额外开辟空间，这也是堆排序原地排序的关键。 对应的还有小顶堆：父节点 ≤ 子节点，堆顶是堆里最小元素。

❓灵魂拷问：升序排序，为什么选用大顶堆，而不是小顶堆？

堆排序有个关键特点：选出最值之后，把最值放到数组末尾固定，有序区域从后往前逐步扩大。

1. 大顶堆：堆顶是最大值 每次交换，把最大值放到数组最后的位置，这个位置就固定不再参与后续排序。 大数不断往数组尾部安家，最后前面剩下的自然就是从小到大的升序序列，和我们流程图的操作完全匹配。
2. 小顶堆：堆顶是最小值 如果用小顶堆，每次拿到的是最小值，交换后最小值会被放到数组末尾。 所有小数都堆在数组尾部，最终得到的数组反而是降序。

补充扩展：理论上小顶堆也能实现升序，但每次取出最小值放到数组前面，会破坏前面已经排好的有序区域，调整堆时代价更高，工程上不会这么写。

大顶堆是一棵完全二叉树，父节点的值 ≥ 左右孩子节点。 堆顶（树根）永远是整个堆里面最大的数字。 数组可以直接映射成完全二叉树，不需要额外开辟空间，这也是堆排序原地排序的关键。

结合这张流程图，一步一步拆解

初始堆：[20,17,4,16,5,3]，画成二叉树根节点是20（全局最大值）

1. 第一步：交换堆顶和堆末尾元素堆顶是最大值20，把20和堆最后一个元素3交换。 👉 此时20就位，固定在数组最后的位置，不再参与后续排序（图里蓝色标记代表已经排好的数）。 现在待排序的堆范围缩小，不再包含 20。
2. 第二步：向下调整，重新变回大顶堆现在堆顶变成了3，不满足大顶堆规则，我们执行向下调整：拿根节点3和左右孩子对比，把大的孩子换上来，一直换到满足大顶堆为止。 调整完成，新堆顶是17，也就是剩下元素里的最大值。
3. 循环重复上面两步

• 交换堆顶17和当前堆末尾元素，17固定就位
• 向下调整，选出剩余元素最大值16
• 交换、调整…… 依次把16、5、4全部放到末尾

每一轮：取堆顶最大值 → 放到数组尾部 → 调整堆选出下一个最大值不断缩小待排序堆的区间，直到堆只剩 1 个元素，排序全部完成。

5.2.2💡温馨提醒

1. 升序排序建大顶堆！很多人容易记反：不是小顶堆。小顶堆适合降序。
2. 堆排序不稳定：相同大小元素，相对顺序会被交换打乱。
3. 时间复杂度 O(Nlog N)：建堆是O(N)，每一次向下调整是(log N)，一共 N 次。
4. 原地排序，空间复杂度O(1)，不需要额外数组。

代码简要解析

// 向下调整：parent位置元素往下滑，维护大顶堆 void AdjustDown(int* arr, int n, int parent) { int child = 2 * parent + 1; while(child < n) { // 选出左右孩子里面更大的那个 if(child+1 < n && arr[child+1] > arr[child]) child++; if(arr[child] > arr[parent]) { swap(&arr[child], &arr[parent]); parent = child; child = 2*parent +1; } else break; // 满足大顶堆，停止 } } void HeapSort(int* arr, int n) { // 1、建大顶堆：从最后一个非叶子节点向前调整 for(int i = (n-2)/2; i >=0; i--) AdjustDown(arr,n,i); // 2、不断取出堆顶最大值放到数组末尾 int end = n-1; while(end>0) { swap(&arr[0], &arr[end]); AdjustDown(arr, end, 0); // 注意end，堆范围缩小，不碰已经排好的尾部 end--; } }

5.2.3特性总结

📜 门派小结 直接选择排序是选择门派的基础款，逻辑简单但效率平平，仅适合小数据场景；堆排序是它的进阶优化版，用堆结构把选最值的效率从O(N)降到O(log N)，时间复杂度跻身(Nlog N)级别，还保持了原地排序的优势，缺点是排序不稳定。

六、非比较排序

门派小引：前面咱们介绍的插入、选择、交换排序，全都属于比较排序，依靠元素两两比较来决定先后。而本门派的成员不走比较这条路，直接利用元素本身的值，通过映射完成排序，因此称为非比较排序。代表选手就是计数排序。

6.1 计数排序

6.1.1基本思想

计数排序也叫鸽巢原理，是哈希直接定址法的变形应用。

核心思想：不去比较元素大小，先统计每个数字出现多少次，再根据统计结果，把数字放回有序数组。只适合数值范围集中的数据。

操作步骤（结合图中例子）

待排序数组 A：[2, 5, 3, 0, 2, 3, 0, 3]

1. 统计频次：创建计数数组 C，C [i] 记录数字i在 A 中出现多少次。 图中 C 数组：值为 0 有 2 个，值为 1 有 0 个，值为 2 有 2 个，值为 3 有 3 个，值为 4 有 0 个，值为 5 有 1 个。
2. 前缀和处理：把 C [i] 修改成小于等于 i 的元素总个数。 这个操作的作用：直接算出数字i在结果数组 B 里的最后存放位置。
3. 从后向前遍历原数组 A： 取出 A 里的元素，查看 C 数组，找到它在 B 数组的下标，放到 B 里；对应 C 数组计数减 1。 ✨重点：必须从后往前遍历，这一步是保证计数排序稳定的关键！
4. 全部复制完成后，B 数组就是有序结果。

C 语言简易实现

void CountSort(int* arr, int n) { // 找最大值，确定计数数组的范围 int max = arr[0]; for(int i = 1; i < n; i++) { if(arr[i] > max) max = arr[i]; } // 开辟计数数组，初始化为0 int* countArr = (int*)calloc(max + 1, sizeof(int)); // 1.统计元素出现次数 for(int i = 0; i < n; i++) { countArr[arr[i]]++; } // 2.计算前缀和，C[i]变为<=i的元素总数 for(int i = 1; i <= max; i++) { countArr[i] += countArr[i-1]; } // 临时数组存放排序结果 int* tmp = (int*)malloc(sizeof(int)*n); // 3.从后向前遍历，保证排序稳定 for(int i = n-1; i >= 0; i--) { tmp[ countArr[arr[i]] - 1 ] = arr[i]; countArr[arr[i]]--; } // 拷贝回原数组 for(int i = 0; i < n; i++) { arr[i] = tmp[i]; } free(tmp); free(countArr); }

6.1.2特性总结

1. 优势：数据范围集中时，效率极高，它没有元素之间的比较操作；缺点：适用场景受限。如果数字跨度极大（如[1, 100000]），会开辟超大数组，浪费大量空间。
2. 稳定性：稳定排序（前提：从后向前遍历原数组）

📌 门派小考点： 很多同学写计数排序习惯从前向后遍历，虽然排序结果数字是对的，但是排序就会变成不稳定！考研 / 笔试很爱考这个坑点。

📜 门派小结：非比较排序门派 前面的几大门派都需要拿元素两两 PK 比较大小，而本门派直接摆烂不做比较，利用数字本身的值做映射统计，典型代表就是计数排序。 计数排序是典型的 “空间换时间” 选手，在整数密集的场景下能跑出碾压级的效率；但短板也十分明显，一旦数据跨度很大，就要开辟巨大的辅助数组，空间开销直接爆炸。 它是为数不多稳定的线性时间排序算法，记住关键点：想要保住稳定性，遍历原始数组时必须从后往前。

七、排序算法复杂度及稳定性分析

门派总览：插入、选择、交换、归并四大门派悉数登场，七位核心算法全部讲解完毕。这里用一张性能总表把时间复杂度、空间开销、稳定性等核心指标一网打尽，方便横向对比，也适合考前速记复盘。

7.1核心性能对比表

八、 选择题练习

参考答案

1.A 2.C 3.D 4.B 5.D 6.A 7.A

好啦，那这篇内容就先整理到这里，这次把相关排序算法的相关知识整理了一下，为了方便自己日后复习回顾，也希望能给正在学习的小伙伴一些参考。如果文中有理解不到位或是书写有误的地方，欢迎大家在评论区指出，一起交流共同进步。谢谢大家！