12.总结
12.1 基础知识
冒泡排序：两两比较交换每轮冒一个最大值。
选择排序：每轮往后找最小值换到前面来。
插入排序：每轮从后往前找在哪里插入。
希尔排序：分成子序列，每轮从后往前找在哪里插入，子序列数（步长）逐个变少直至最后一轮变成插入排序。
归并排序：递归分成左右集合，左右集合排序好后，合成重新合并排序。
快速排序：partition 后基准落在最终位置，左侧不大于基准、右侧不小于基准，再对左右子区间递归。
堆排序：从最后一个非叶结点向前建大根堆，父结点不小于子结点，堆顶为当前最大；将堆顶与未序末尾交换，缩小堆范围再调整。
计数排序：用计数数组统计各值出现次数，再按值域顺序写回（本系列为简版实现，稳定版需额外步骤）。
桶排序：按区间映射进桶，桶内单独排序，再按桶序合并输出。
基数排序：先按个位值的分桶后丢回原数组。再对十位的值进行分桶丢回原数组，以此推类直至所有位数排序完再合成。
12.2 核心要点速览
十种算法一句话
- 冒泡：从左到右比较相邻元素，逆序则交换；每一趟会把当前未序区间里的最大值推到右边界。
- 选择：已序在左、未序在右；每轮在未序中找最小下标，与未序首交换。比较次数多，写回次数少。
- 插入：已序在左；取出未序第一个元素，在已序段从后向前找插入位置并后移腾位。数据接近有序时比较和移动都少。
- 希尔：按递减步长把数组分成多条子序列，子序列内做插入排序，最后一步长为 1 即普通插入。大步长负责长距离归位，小步长负责收尾。
- 归并：左右两半分别有序后，用双指针合并成一段有序区间。时间
O(n log n)，常见实现需要O(n)辅助空间，稳定。 - 快排：每一轮选定 pivot，partition 后左侧不大于 pivot、右侧不小于 pivot，再对两侧递归。平均
O(n log n)，最坏O(n^2)，不稳定；递归栈深度划分均衡时O(log n)量级。 - 堆排：先建大根堆，再反复把堆顶与未序末尾交换并缩小堆、对根下沉。时间
O(n log n)，额外空间O(1)，不稳定。 - 计数：非负整数且上界不大时，用数组下标表示值做频次统计，再按值从小到大写回。时间
O(n+k)，空间随值域走。本系列是简版写回；要稳定需前缀和并从右向左写入结果区。 - 桶：按映射规则进桶，桶内再排序，最后按桶序拼接。复杂度由分布和桶内算法共同决定。
- 基数：LSD 从低位到高位做多趟分配-收集；每一趟对「当前位」的排序必须稳定，才能把低位的次序保留到高位比较里。
复杂度、原地与稳定性（总表）
查表时优先对照三项：最坏时间、额外空间、是否稳定。希尔的平均复杂度随步长序列变化，表中不写死单一渐近式；折半步长实现的最坏仍常记为 O(n^2)。
| 算法 | 平均时间 | 最坏时间 | 额外空间 | 原地 | 稳定 |
|---|---|---|---|---|---|
| 冒泡 | O(n^2) |
O(n^2) |
O(1) |
是 | 是 |
| 选择 | O(n^2) |
O(n^2) |
O(1) |
是 | 否 |
| 插入 | O(n^2) |
O(n^2) |
O(1) |
是 | 是 |
| 希尔 | 随间隔序列 | 常见 O(n^2) |
O(1) |
是 | 否 |
| 归并 | O(n log n) |
O(n log n) |
O(n) |
否（常规实现） | 是 |
| 快排 | O(n log n) |
O(n^2) |
O(log n) 量级（递归栈） |
是 | 否 |
| 堆排 | O(n log n) |
O(n log n) |
O(1) |
是 | 否 |
| 计数 | O(n+k) |
O(n+k) |
O(n+k) |
否 | 否（本系列简版写回） |
| 桶 | 常 O(n+k) 量级 |
可退化为 O(n^2) |
O(n+k) 量级 |
否 | 依桶内算法 |
| 基数 | O(d(n+k)) |
O(d(n+k)) |
O(n+k) |
否 | 是（LSD + 顺序收集） |
说明：n 为元素个数；k 在计数、桶、基数里含义不同（值域宽度、桶数、基数等），不要混用；d 为基数排序趟数。冒泡、插入在输入已有序时，比较量可接近 O(n)，表中平均列仍按乱序/一般数据来记。
系列演示约定与 SortHelpTool
- 示例一律按升序；C# 与 Lua 对照时，下标分别从 0 / 1 起，和各自正文一致即可。
SortHelpTool常用成员：arrayToSort：各篇共用的示例数组，跑完排序对照输出。PrintArray/PrintList：调试时把当前序列打成一行。Swap：冒泡、选择、快排里高频。FindMaxValue：计数、桶、基数里取上界或划桶。GetDigit(number, digit)：十进制从低位数第digit位（基数排序按位入桶）。CountDigits：十进制位数；0、负数在工程里要单独约定，本系列例子限定在非负整数。
// digit 从 1 表示个位、2 表示十位……从低位往高位数
// 例：1234 取 digit=2 得到十位上的 3
public static int GetDigit(int number, int digit)
{
return (number / (int)Math.Pow(10, digit - 1)) % 10;
}
冒泡排序：相邻逆序则交换，每趟固定右端一个最大值
- 在未序区间从左到右比较相邻元素，前者大则交换；一趟结束后，当前未序中的最大元素停在右边界，已序区从右侧延长一格。
- 提前退出：维护本趟是否发生过交换；若一整趟无交换，说明全局已有序，可直接返回。带该优化时，已有序输入约
O(n)次比较；无优化或乱序数据仍是O(n^2)。 - 仅在严格大于时交换，相等键不动，稳定；额外空间
O(1)。
for (int i = 0; i < array.Length - 1; i++)
{
bool isSwap = false;
for (int j = 0; j < array.Length - i - 1; j++)
{
if (array[j] > array[j + 1])
{
SortHelpTool.Swap(ref array[j], ref array[j + 1]);
isSwap = true;
}
}
if (!isSwap) return;
}
选择排序：在未序区间找最小，与未序首元素交换
- 第
i轮在[i, n-1]上扫描得到minIndex，与array[i]交换。每轮对数组的写入至多一次，交换比冒泡少，但比较仍是逐轮线性扫描，总计Θ(n^2)，与输入是否已有序无关。 - 最小值可能从远处换到前面，跨过相等键，不稳定；空间
O(1)。
插入排序：保存当前元素，在已序段中后移空位
i从 1 到n-1：令currentElement = array[i]，j = i - 1；在j >= 0且array[j] > currentElement时，把array[j]赋给array[j+1]并j--；结束后array[j+1] = currentElement。- 只有严格大于才后移，相等键不会被越过，稳定。最坏、平均
O(n^2)；数据近乎有序时内层循环极短，最好O(n)。适合小规模或作为分治排序在子区间很小时的收尾。
希尔排序：按步长分组做插入排序
- 外层递减
step（示例为n/2起反复减半至 1）。对每个step，下标step, step+1, …上的元素各自形成一条「隔step一条」的子序列，在子序列上做插入排序；比较与移动一次跨step格。 - 不稳定：跨步长交换可能打乱相等键的相对顺序。额外空间
O(1)。复杂度由步长序列决定；折半步长最坏仍可O(n^2)，但大步长阶段能减少后期插入的长距离搬运，整体往往明显快于裸插入。
| 对比 | 冒泡 | 选择 | 插入 | 希尔 |
|---|---|---|---|---|
| 每轮在干什么 | 相邻交换把大值往右推 | 在未序里找最值，换到未序首 | 把 array[i] 插入左侧已序 |
按 step 分组的插入排序 |
| 写回次数 | 多 | 每轮至多 1 次 | 近有序时少 | 介于上两者之间 |
| 稳定 | 是 | 否 | 是 | 否 |
| 最好可达 | O(n)（有剪枝且已有序） |
仍为 O(n^2) |
O(n)（已有序） |
依赖步长序列 |
归并排序：二分递归 + 双指针合并
- 将
[left, right]从中点拆成两段，递归到长度为 1；Merge把两个已序片段写入新数组，双指针比较，较小者（相等时先取左侧）先入结果，剩余一段整体拷贝。 - 本系列 C# 是「子调用返回新数组再合并」，不是原地 merge；时间
O(n log n)，辅助空间主要来自合并缓冲，量级O(n)，稳定（左端<=右端时先取左）。 - 链表归并可做到
O(1)额外指针；数组原地合并代价高、代码复杂，日常说的「归并占内存」多指「数组 + 辅助缓冲区」这一套。
if (leftArray[leftIndex] <= rightArray[rightIndex])
{
mergedArray[mergedIndex] = leftArray[leftIndex];
leftIndex++;
}
快速排序：划分基准 + 递归子区间
- Lomuto，本系列选最右为 pivot：
lessIndex表示「≤ pivot」区间的右端；i从left扫到right-1，若array[i] <= pivot则lessIndex++并视情况交换array[lessIndex]与array[i]。循环结束后将array[right]与array[lessIndex+1]交换，得到 pivot 最终下标，再递归左右两段。 - 平均
O(n log n)；已序且固定取最右为轴时最坏O(n^2)。主要额外开销是递归栈，划分均衡时深度O(log n)。不稳定，与 pivot 同值的元素可能被集中到某一侧。 - 随机 pivot、三数取中等可压低最坏概率；子区间很短时可换插入排序，减少递归层数。
堆排序：数组视作完全二叉树，大根堆 + 堆顶与末尾交换
- 0 基下标：结点
i的左右孩子为2i+1、2i+2。BuildMaxHeap从n/2-1递减到0依次Heapify，保证父结点值不小于子结点。 - 排序阶段：将
array[0]与当前未序末尾array[i]交换，未序长度减 1，再对根Heapify(heapSize=i, root=0)，直到堆中仅剩一个元素。 - 最坏时间
O(n log n)，额外空间O(1)，不稳定。常数和访存局部性往往不如快排，但对输入分布不敏感；若要求最坏n log n又不能开O(n)辅助数组，堆排是常见选项。
| 对比 | 归并 | 快排 | 堆排 |
|---|---|---|---|
| 额外空间 | O(n) 典型 |
O(log n) 栈为主 |
O(1) |
| 最坏时间 | O(n log n) |
O(n^2)（未优化 pivot） |
O(n log n) |
| 稳定 | 是 | 否 | 否 |
| 实现抓手 | Merge 双指针 |
Partition + 递归 |
Heapify + 交换堆顶 |
计数排序：值作下标统计频次
- 求
max，分配count[0..max]，遍历原数组做count[x]++；再令i从 0 递增，将i重复写回原数组count[i]次。时间O(n+k)，其中k与值域上界同阶；max远大于n时，计数数组又长又空，不划算。 - 上述流程是本系列的简版写回，不是标准稳定计数（缺前缀和与逆向填充）。前提一般是非负整数、上界可控、且没有要随键一起移动的附带数据。
foreach (var num in array)
countArray[num]++;
int index = 0;
for (int i = 0; i < countArray.Length; i++)
{
while (countArray[i] > 0)
{
array[index++] = i;
countArray[i]--;
}
}
桶排序：映射入桶、桶内排序、按序归并
- 示例用
num/5得桶号、bucketCount = max/5+1，桶内调用Sort/table.sort，再按桶编号依次写回原数组。若元素均匀散开，各桶规模接近n/k，整体接近O(n+k)；若全部落入同一桶，桶内再用平方算法，最坏可到O(n^2)。 - 是否稳定取决于桶内排序与收集方式；不要默认
List.Sort等对值类型一定稳定，答题时把桶内算法说清楚。
基数排序：低位优先（LSD）逐位分配
- 求最大值的位数
d，对digit = 1..d做一轮分配：GetDigit(num, digit)得到 0～9，入对应桶，再按桶号 0～9 依次倒回数组。单趟O(n+k)，k为基数 10，共d趟，总O(d(n+k))。 - LSD 正确性依赖每一趟不改变同桶内元素的相对顺序；本篇实现不在桶内二次排序，靠入桶先后 + 按桶序收集，把低位的次序保留到高位比较时再用。
| 对比 | 计数 | 桶（本篇示例） | 基数（LSD） |
|---|---|---|---|
| 瓶颈 | 值域宽度 k |
分布是否均匀、桶内算法 | 位数 d 与基数 k |
| 典型空间 | O(k) 计数数组 |
O(n+k) 桶存元素 |
O(n+k) 每趟桶 |
| 是否比较排序 | 否 | 否（桶内可能用比较排序） | 否 |
选型时先问的三件事
- 数据是否允许用非比较模型：计数、桶、基数都要求值域、分布或可拆分的数位/关键字；比较排序受
O(n log n)下界约束（决策树意义下）。 - 要不要稳定：多关键字排序或需要保留相等键原序时，归并、插入、冒泡，以及标准计数排序、本篇 LSD 基数实现，更合适；快排、堆排、选择、希尔一般视为不稳定算法。
- 空间与最坏：辅助空间紧、又要最坏
O(n log n)时多考虑堆排；能开O(n)缓冲区且要稳定用归并；快排平均性能好，配合随机轴、三数取中、小区间插入等可控制最坏情况。
12.3 面试题精选
基础题
1. 稳定排序与不稳定排序各举几例，不稳定一般是怎么「打破」相对顺序的
题目
什么是稳定排序？快排、堆排、选择排序为什么不稳定？各用一句话场景说明什么时候稳定性有用。
深入解析
- 稳定：关键字相等的元素，排序前后相对顺序不变。不稳定：远距离交换或分区时，相等键可能被翻到另一侧，相对顺序改变。
- 快排：partition 可能把与基准相等的元素集中到一侧，跨区间交换破坏原有相对顺序。
- 堆排：下沉、交换堆顶与末尾时，相等元素层级互换。
- 选择排序：每次把未序最小换到已序末尾，跨区间交换同样可能交换两个相等键的前后关系。
- 稳定性用处举例：先按「分数」排，再按「姓名」排；若第二次排序稳定，同分的人仍保持第一次的次序。
答题示例
稳定排序要求相等键排序前后相对顺序不变；快排、堆排、选择通过交换或分区可能跨过相等元素，因而不稳定。
多关键字排序时若先按次要键、再按主要键排，后一趟需要稳定算法，否则前一趟排好的次序会被打乱。
参考文章
- 1.概述
2. 插入排序最好、平均、最坏时间复杂度各是什么
题目
插入排序在什么数据形态下最好？最坏和平均为什么都是平方级？
深入解析
- 最好：输入已经有序时，内层
while一次都不执行，只做约n-1次比较，移动极少，整体O(n)。 - 最坏：逆序或每次都要插到最前面，第
i个元素最多移动i次，总和1+2+…+(n-1)，时间Θ(n^2)。 - 平均：随机数据下每个元素平均要越过已序区的一段，仍是
Θ(n^2)量级。
答题示例
已有序时最好 O(n)，内层几乎不移动。平均与最坏为 O(n²)，来自每个元素可能将已序段整体后移一格的累加。
插入排序适合小规模或近似有序数据；规模大且乱序应换
O(n log n)类算法。
参考文章
- 4.插入排序
3. 大根堆用数组存（0 基下标），父子和根的下标关系
题目
长度为 n 的数组表示完全二叉树大顶堆时，根下标是多少？结点 i 的左、右孩子下标公式是什么？为什么要从 n/2-1 开始向前 Heapify？
深入解析
- 根在
0；左孩子2i+1，右孩子2i+2（需< heapSize才算存在）。 - 最后一个非叶结点下标为
⌊n/2⌋-1：再大的下标都是叶，没有孩子，下沉无从谈起；从后往前保证孩子先已是各子堆根，再向上修正。
答题示例
根是下标 0。结点 i 的左右孩子是 2i+1 和 2i+2。
建堆从 n/2-1 往前扫，因为后半段是叶子不用调，从最后一个有孩子的父结点开始下沉，才能自下而上堆化。
参考文章
- 8.堆排序
4. 计数排序的 k 指什么，为什么 k 远大于 n 时不实用
题目
计数排序时间复杂度里的 k 是什么？若元素个数很少但最大值很大，会发生什么？
深入解析
k与值域上界同阶；该实现里计数数组长度为maxValue+1，与元素个数n无直接关系。max很大时，数组大部分下标闲置，时间和空间都被值域绑架，不如比较排序划算。
答题示例
这里的 k 可以理解为
max+1量级，即计数数组要覆盖的下标范围。n 小但 max 大时，仍要开很长的计数数组，开销主要由 max 决定，只适合值域有界的非负整数场景。
参考文章
- 9.计数排序
进阶题
1. 归并、快排、堆排都是「大约 n log n」，面试里怎么选
题目
从平均时间、最坏时间、额外空间、稳定性四个维度比较归并排序、快速排序、堆排序，并说明各自典型短板。
深入解析
- 归并：时间稳
O(n log n)，稳定，代价是O(n)辅助数组（链表实现可降到O(1)辅助但常数大）。适合要稳定或最坏也要n log n且能接受额外内存的场景。 - 快排：平均
O(n log n)，原地，常数较小、缓存友好；最坏O(n^2)，不稳定；递归栈平均O(log n)。不少标准库排序在其基础上做优化。 - 堆排：最坏
O(n log n)，额外空间O(1)，不稳定，访存局部性通常弱于快排；适合要求最坏n log n且不能开线性辅助区的场景。
答题示例
要稳定或沿用归并思路：归并。要平均快、原地：快排，并配合随机轴、小区间插入等压低最坏情况。要最坏
n log n且辅助空间严格O(1)：堆排。取舍：归并占
O(n)辅助，快排最坏与稳定性是短板，堆排常数偏大且不稳定。
参考文章
- 1.概述
2. 冒泡排序加「一轮没有交换就结束」后，最好时间复杂度怎么变，原理是什么
题目
无优化冒泡与带 isSwap 标志的冒泡，在最好情况下时间复杂度差多少？为什么？
深入解析
- 无优化：即使已有序，外层仍跑满约
n-1轮，内层比较总次数仍是Θ(n^2)。 - 有优化：第一轮扫描发现没有任何交换即可
return，比较约n-1次，时间O(n)。 - 标志位表达的是「这一趟是否发生过逆序对消除」；没有逆序对等价于全局非降。
答题示例
加标志后，已经有序的数组一趟比较就能发现没交换，直接结束，最好 O(n)。
不加的话照样要做满外层轮次，比较次数还是平方级。
参考文章
- 2.冒泡排序
3. Lomuto 分区结束时，为什么要把 pivot 换到 lessIndex+1
题目
以上文 Lomuto 实现为例：Partition 里 lessIndex 从 left-1 开始，i 从 left 扫到 right-1，遇到 <= pivot 就扩 lessIndex 并交换。循环结束后为什么要 Swap(array[lessIndex+1], array[right])？返回值表示什么？
深入解析
- 循环不变式：
[left..lessIndex]这一段里放的都<= pivot，(lessIndex+1..i)里是「大于 pivot 的已扫过元素」。 array[right]全程没参与与i的直接交换，最后落在lessIndex+1才能让左边全<= pivot、右边全>= pivot（本实现把等于 pivot 的也归到左侧）。- 返回值是 pivot 的最终下标，递归以此为界拆左右子区间。
答题示例
lessIndex 左边都是小于等于 pivot 的，lessIndex+1 到 right-1 是比 pivot 大的。基准一直在 right，最后把它换到 lessIndex+1，就夹在两块中间，这个位置就是 pivot 的最终位置。
返回这个下标，左右两边再分别快排。
参考文章
- 7.快速排序
4. 桶排序在什么情况下会从「接近线性」退化成很慢
题目
桶排序最坏能到什么复杂度？结合「元素分布」和「桶内排序」说明。
深入解析
- 所有元素进同一个桶时，外层桶工作退化为对全体元素做一次桶内排序；若桶内用插入/冒泡等平方算法，最坏
O(n^2)。 - 桶数过少或映射函数与数据分布不匹配时，容易出现「一桶装全部」。
答题示例
最坏情况是元素全部进同一个桶，桶内再跑一次平方阶排序，整体可到 O(n²)。
桶排序依赖分布是否能把元素摊到多个桶里；映射不当等价于只对原数组做了一次桶内排序。
参考文章
- 10.桶排序
深度题
1. 为什么比较排序有 O(n log n) 下界，计数和基数还能更快
题目
用决策树或信息论直觉说明比较排序的下界；计数排序、基数排序为什么可以突破，各自需要什么前提。
深入解析
- 比较排序每次比较只有两种结果，决策树叶子对应
n!种排列，树高下界Ω(n log n)。 - 计数排序：不通过比较决定先后，而是用值作为下标统计频次；前提是值可映射到有限范围且范围不能比
n大太多，否则空间爆炸。 - 基数排序：多趟分配，每趟对一位或一维关键字排序，依赖每趟子算法稳定；前提是关键字可拆分且趟数
d可控，辅助空间与基数k有关。
答题示例
比较排序可建模为决策树，叶子对应 n! 种排列，树高 Ω(n log n)。
计数、基数在特定数据假设下用下标或数位分配代替通用比较，可突破该下界；前提仍是值域/位数可控，不能当作万能排序。
参考文章
- 1.概述
2. 希尔排序相对插入排序快在哪里，为什么反而不稳定
题目
希尔排序和插入排序的关系是什么？大步长阶段解决了插入排序的什么痛点？不稳定通常怎么发生？
深入解析
- 关系：
step=1的最后一轮就是普通插入排序；前面各轮是在不同步长的子序列上做插入，让元素大步跳跃到更接近最终位置的地方，减少最后细调时的长距离后移。 - 快的原因：纯插入一次只挪一格，小元素在左侧时要挪很多次；希尔先用大步长把元素送到粗粒度正确区域，再缩小步长精修。
- 不稳定：交换发生在相隔
step的位置，相等元素可能被换到不同「子序列」语境下，相对次序不像相邻插入那样可保持。
答题示例
希尔是多组插入排序，步长递减到 1；大步长先把元素送到大致区域，减少末尾纯插入时的长距离移动。
不稳定来自跨步长交换：相等元素可能被换到不同子序列语境里，相对顺序不像相邻插入那样天然保持。
参考文章
- 5.希尔排序
3. 建堆 BuildMaxHeap 为何总体是 O(n)
题目
Heapify 单次下沉看似 O(log n)，从 n/2-1 扫到 0 要调用 O(n) 次，为什么整体仍是 O(n) 而不是 O(n log n)？
深入解析
- 不能写成
n次调用各O(log n)相乘：堆底层结点数量多但高度低，顶层结点少但高度高，按层累加代价可得线性上界（与调和级数相关）。 - 多数
Heapify只下沉常数层，仅靠近根的下沉路径长，摊到整体上仍是O(n)。
答题示例
建堆时大量结点在低层，单次
Heapify路径短；不能按 n×log n 粗乘。自底向上建堆总量 O(n)；排序阶段每次弹出堆顶再下沉，才是 n log n 量级。
参考文章
- 8.堆排序
4. LSD 基数排序为什么要求从低位到高位，且每一趟收集要稳定
题目
基数排序从个位排到十位再排到更高位时，若某一趟收集不稳定，会发生什么？能否改成先排高位再简单合并？
深入解析
- 低位趟排好后，高位尚未参与排序；下一趟按高位分桶时，同一高位桶内须保持上一趟留下的低位相对次序，整体才是全序。收集时若打乱同桶顺序，等价于破坏已排好的低位信息，结果错误。
- MSD（先高位）可行，但通常要递归处理子区间或额外结构，与「每趟填满原数组」的 LSD 写法不是同一条实现路径。
答题示例
高位相等时要用低位次序打破平局；后续每一趟收集必须保持同桶 FIFO，否则会覆盖前几趟的结果。
MSD 是另一套分支，不能直接把 LSD 的代码「倒着跑数位」当完整方案。
参考文章
- 11.基数排序
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
