目录
排序的基本概念
排序的定义
排序的稳定性
内部排序和外部排序
插入排序
直接插入排序
折半插入排序
希尔排序
交换排序
冒泡排序
快速排序
选择排序
简单(直接)选择排序
树形选择排序
堆排序
归并排序
2路归并
基数排序
外部排序
排序的基本概念
排序的定义
排序（Sorting)是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作。
开始
│
├─► 输入记录序列 {R₁, R₂, …, Rₙ}
│ 和关键字序列 {K₁, K₂, …, Kₙ}
│ 以及排序方式（升序/降序）
│
├─► 初始化下标集合 {1, 2, …, n}
│
├─► 根据关键字比较规则，对下标进行排序
│ 比较 Kᵢ 与 Kⱼ 的大小
│ 按升序或降序确定排列 p₁, p₂, …, pₙ
│
├─► 生成新序列 {R_{p₁}, R_{p₂}, …, R_{pₙ}}
│
├─► 输出有序序列
│
▼ 结束
排序的稳定性
排序稳定性指的是：如果在待排序的序列中，两个记录具有相同的关键字值，那么在排序之后，它们的相对顺序与排序前保持一致。就说所用的序列方法是稳定的，反之不是。
内部排序和外部排序
内部排序
内部排序是指待排序的数据全部存放在计算机内存（RAM）中，排序过程中不需要访问外存（硬盘、磁带等）。
特点：
数据量相对较小（能一次性装入内存）
排序速度快（内存访问速度远高于外存）
分类：
内部排序的方法多、但就其全面性能而言，很难一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境(如记录的初始排状态等)下使用。
内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，可以将排序记录区分为两个区域:有序序列区和无序序列区。
使有序区中记录的数目增加一个或几个的操作称为一趟排序。
根据逐步扩大记录有序序列长度的原则不同，可以将内部排序分为以下几类：
| 类别 | 基本思想 | 增加有序区的方式 | 主要算法 |
|---|---|---|---|
|
插入类 插入排序 |
将无序子序列中的一个或几个记录插入到已有序序列的合适位置，扩大有序区长度 | 插入操作 |
直接插入排序 折半插入排序 希尔排序 |
|
交换类 交换排序 |
通过交换无序序列中的记录，使关键字最小（或最大）的记录移到有序区 | 交换操作 |
冒泡排序 快速排序 |
|
选择类 选择排序 |
在无序子序列中选出关键字最小（或最大）的记录，放到有序区末端 | 选择并移动 |
简单选择排序 树形选择排序 堆排序 |
|
归并类 |
将多个有序子序列归并成一个更大的有序序列 | 归并操作 | 2-路归并排序 |
|
分配类 基数排序 |
不比较关键字，通过多轮分配与收集操作按位/按组排序 | 分配收集 | 基数排序 |
适用场景：
小规模数据处理
数据库内存查询结果排序
程序运行时的临时排序任务
外部排序
外部排序是指待排序的数据量太大，无法全部放入内存，必须借助外存进行多次读写才能完成排序。
特点：
数据存储在磁盘、磁带等外部设备上
排序过程涉及分段读入内存 → 内部排序 → 写回外存 → 归并等步骤
适用场景：
大规模数据排序（TB 级别文件）
数据库对大表排序（ORDER BY 大数据量）
日志文件、海量数据分析
排序算法效率的主要评价指标
时间复杂度：执行排序所需的时间量级（比较、移动、交换等基本操作的次数随数据规模 n的增长趋势）
空间复杂度：算法执行过程中除输入数据外所需的额外存储空间
插入排序
插入排序（Insertion Sort）是最直观的排序算法之一。
基本思想是：每一趟将一个待排序的记录，按其关键字的大小插入已经排好的一组记录的适当位置，直到所有待排序记录全部插入为止。
直接插入排序
直接插入排序（Straight Insertion Sort)是一种最简单的排序方法，其基本操作是将一条记录插入已排好序的表，从而得到一个新的、记录数量增1的有序表。
算法逻辑
将整个序列看作两部分：
前一部分：有序序列（初始时只有第一个元素）
后一部分：无序序列（初始时从第二个元素开始）
过程：
将 无序序列 的第一个元素插入到 有序序列 中的合适位置，保持 有序序列 始终有序。
重复直到 无序序列 为空
插入：“将一个元素插入有序序列”的算法(原为顺序查找)
时空消耗
时间复杂度
直接插入排序的时间复杂度主要取决于比较次数和移动次数，两者均与初始序列的有序程度密切相关。
1. 最好情况（初始序列已有序）
每趟插入时，只需比较1次（无需移动元素）。
总比较次数：n−1次（n为元素个数）。
总移动次数：0次（仅需将元素放入原位置）。
时间复杂度：O(n)（线性阶）。
2. 最坏情况（初始序列逆序）
每趟插入时，需比较i次（i为当前无序区长度，从2到n），并移动i次（将前面i−1个元素后移，再插入当前元素）。
总比较次数：1+2+⋯+(n−1)=2n(n−1)≈O(n2)。
总移动次数：同样为2n(n−1)≈O(n2)（每次插入需移动前面所有已有序元素）。
时间复杂度：O(n2)（平方阶）。
3. 平均情况
假设初始序列随机分布，每趟插入的比较和移动次数约为2i（i为当前无序区长度）。
总比较和移动次数约为4n2，因此时间复杂度：O(n2)（平方阶）。
二、空间复杂度
直接插入排序是原地排序（In-place Sort），仅需常数级别的额外空间：
用于暂存当前待插入元素的变量（如
temp
控制循环的临时变量（如下标
i
j
| 情况 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 最好情况 | O(n) | O(1) |
| 最坏情况 | O(n²) | |
| 平均情况 | O(n²) |
折半插入排序
折半插入排序（Binary Insertion Sort）是直接插入排序的改进版，唯一区别是：
在“找插入位置”这一步，用二分查找代替顺序查找，减少比较次数。
时空消耗
一、时间复杂度
时间复杂度主要取决于比较次数和移动次数，两者均随数据规模 n增长而变化。
1. 比较次数
在直接插入排序中，插入第 i个元素（i≥2）时，需从有序区的末尾向前顺序查找插入位置，平均比较次数为 O(i)（最坏 i次，最好 1 次）。总比较次数为 O(n2)。
折半插入排序中，插入第 i个元素时，通过二分查找在长度为 i−1的有序区中查找插入位置，二分查找的时间复杂度为 O(logi)（每次将搜索范围减半）。因此，总比较次数为：
2. 移动次数
无论是否使用二分查找，插入操作中元素的移动次数与原直接插入排序完全一致。因为找到插入位置后，仍需将插入位置之后的元素逐个后移（腾出空间），移动次数取决于元素的初始顺序：
最好情况（初始有序）：无需移动元素，移动次数为 0。
最坏情况（初始逆序）：插入第 i个元素时需移动 i−1个元素，总移动次数为 ∑i=2n(i−1)=2n(n−1)=O(n2)。
平均情况：移动次数为 O(n2)（与直接插入排序相同）。
综合时间复杂度
由于移动次数是主导因素（比较次数的 O(nlogn)远低于移动次数的 O(n2)），折半插入排序的时间复杂度与直接插入排序相同：
最好/平均/最坏时间复杂度均为 O(n2)。
二、空间复杂度
折半插入排序仅需常数级别的额外空间（如二分查找的
low
high
mid
空间复杂度为 O(1)（原地排序）。
希尔排序
希尔排序（Shell Sort）是插入排序的升级版，它通过“分组插入排序”让数据大致有序，最后再用一次普通插入排序收尾。
核心思想：先让数组“大致有序”，再让它“完全有序”。
算法逻辑
1. 分组阶段（按 gap 分组）
设定一个增量 gap
把序列分成 gap 个子序列(作为每次排序的元素)，对序列进行插入排序
2. 缩小 gap
缩小 gap 后重复 1. 直到当 gap == 1 时，整个序列做最后一次插入排序。(此时数组已“大致有序”，插入排序非常快。)
gap：
初始值通常为 序列长度 整除 2
缩小 gap：每次将 gap 减半（或按某个序列，如 Sedgewick 序列）
时空消耗
时间复杂度
希尔排序的时间复杂度由增量序列的选择决定。其核心思想是通过分组插入排序使数组接近有序，最终通过一次插入排序完成，时间复杂度显著低于直接插入排序的 $O(n^2)$，但具体量级因增量序列不同而差异明显。
常见增量序列的时间复杂度
希尔原始增量（
）：
最坏时间复杂度为 
（如逆序数组），平均时间复杂度约为 $O(n^{1.5})$（经验值）。
Hibbard增量（
，如 
）：
最坏时间复杂度优化为 
（n 趋近于无穷大时），平均时间复杂度约为 $O(n^{5/4})$。
Sedgewick增量（如 
或 ，如 
）：
目前已知最优的增量序列之一，最坏时间复杂度可达 
（约 
），平均时间复杂度接近 
。
总结
希尔排序的时间复杂度无统一表达式，但通常认为：
最坏情况下：（原始增量）至 （Sedgewick增量）。平均情况下：介于 
和 之间（实际表现远优于直接插入排序）。
空间复杂度
希尔排序是原地排序算法（In-place Sort），仅需常数级别的额外空间（如临时变量存储交换元素、控制循环的索引等），空间复杂度为 O(1)。
关键结论
时间复杂度：依赖增量序列，最优可达 （Sedgewick增量），常规场景下约为 
。空间复杂度：O(1)（原地排序）。
希尔排序的优势在于对中等规模数据的高效性（尤其当数据部分有序时），且代码实现简单，是插入排序的重要改进版本。
交换排序
交换排序是一类通过“比较+交换”完成排序的算法统称，核心思想是：
一旦发现相邻或选定的一对元素逆序，就交换它们的位置，从而让较大（或较小）的记录像“气泡”一样不断向一端移动，最终得到有序序列。
冒泡排序
冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历要排序的列表，依次比较相邻的两个元素，并根据需要交换它们的位置。这个过程持续进行，直到列表已经排序完成。
算法逻辑
将整个序列看作两部分：有序序列（初始时为空)与无序序列（初始时初始序列）
从无序序列的第一个元素开始，依次比较相邻的两个元素。
如果前一个元素比后一个元素大（对于升序排序），则交换这两个元素的位置。
继续对无序序列的每一对相邻元素进行比较和交换，直到到达列表的一端。这样，最大/最小的元素就会“沉”到列表的一端。此时无序序列减小有序序列增大。
重复上述过程，每次遍历时忽略已经排序好的有序序列，直到整个序列排序完成。
时空消耗
时间复杂度
冒泡排序的时间复杂度主要由比较次数和交换次数决定，具体取决于输入数据的初始状态：
1. 最好情况（已有序）
若序列初始时已完全有序，只需进行1轮遍历（n-1次比较），无需任何交换即可结束排序。
比较次数：n−1次（n为元素个数）。
时间复杂度：O(n)（线性阶）。
2. 最坏情况（逆序）
若序列初始时完全逆序（如降序需转升序），需要进行n-1轮遍历，每轮比较次数依次递减（第i轮比较n−i次），且每轮需交换大量元素。
总比较次数：(n−1)+(n−2)+⋯+1=2n(n−1)≈2n2次。
总交换次数：同样为2n(n−1)次（每次比较都可能交换）。
时间复杂度：O(n2)（平方阶）。
3. 平均情况
对于随机排列的序列，冒泡排序的平均比较次数和交换次数均接近最坏情况的4n2，因此平均时间复杂度为O(n2)。
空间复杂度
冒泡排序是原地排序算法（In-place Algorithm），仅需常数级别的额外空间用于辅助变量（如临时存储交换值的变量、循环控制变量等），与输入规模n无关。
空间复杂度：O(1)（常数阶）。
总结
|
情况 |
时间复杂度 |
空间复杂度 |
|---|---|---|
|
最好情况 |
O(n) |
O(1) |
|
最坏情况 |
O(n2) |
O(1) |
|
平均情况 |
O(n2) |
O(1) |
注：冒泡排序的优势在于实现简单、稳定（相同关键字元素的相对顺序不变），但由于时间复杂度较高（O(n2)），实际中仅适用于小规模数据或教学场景。
快速排序
快速排序（Quick Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略。
算法逻辑
基准值（Pivot）：选择一个元素作为基准，将序列分为两部分：
左子序列：所有元素 ≤ 基准值。
右子序列：所有元素 ≥ 基准值。
(也可以分三组以小等大于基准值)
步骤1：
选择基准值，根据基准值将序列重新排列，满足：
基准值左侧所有元素 ≤ 基准值。
基准值右侧所有元素 ≥ 基准值。
步骤2：递归/迭代算法
将左子序列执行步骤1-2，右子序列同理。
———————————————————————
选择基准值：
选择首元素；尾元素；随机元素。
三数取中（首、尾、中间值的中位数）(推荐)。
将序列重新排列：
双指针算法：
初始：指针1指向序列第1个元素，指针2指向序列最后一个元素，指针3指向基准元素(如果基准值为序列元素，不是则为基准值)。
若指针1指向元素小于等于指针3指向的基准元素则指针1向右移动1。
若指针2指向元素大于等于指针3指向的基准元素则指针2向左移动1。
以上两条件都不满足则交换指针1与指针2所指向元素的位置。
直到指针1与指针2指向同一个元素，交换指针3指向基准元素与指针1或2指向元素。
(以基准元素(最后指针1与指针2指向同一个元素)位置分左右子序列)
时空消耗
快速排序的时间复杂度和空间复杂度与其划分的均衡性密切相关，以下是详细分析：
一、时间复杂度
快速排序的核心是分治策略，通过选择基准值将序列划分为左右子序列，递归排序子序列。其时间复杂度主要取决于划分的均衡程度（即基准值是否能将序列大致均分）。
1. 最好情况（最优划分）
每次选择的基准值恰好是序列的中位数，将序列均匀划分为两个长度接近的子序列（左子序列和右子序列的长度差不超过1）。此时，递归树的深度为 O(logn)，每层需要 
时间完成划分（比较和交换）。
总时间复杂度：。
2. 平均情况
即使基准值并非严格中位数，只要划分大致均衡（如每次划分后子序列长度比例为常数比例），递归树的深度仍为 ，每层总比较次数为 。数学推导（如递推式求解）表明，平均时间复杂度为 。
3. 最坏情况（最差划分）
每次选择的基准值是序列的最小或最大元素，导致划分极度不均衡（左子序列长度为0，右子序列长度为 n−1；或反之）。此时，递归树退化为链状结构，深度为 ，每层需要 时间。
总时间复杂度：（例如，对已有序序列选择首尾元素作为基准值时触发）。
二、空间复杂度
快速排序的空间复杂度主要来自递归调用栈的深度（不考虑输入数据本身的存储）。
1. 最好/平均情况
递归树深度为 
，因此递归栈的空间复杂度为 （存储每层递归的参数和局部变量）。
2. 最坏情况
递归树深度为 （链状结构），递归栈的空间复杂度为 。
三、补充说明
稳定性：快速排序是不稳定排序（划分过程中可能交换相等元素的相对位置）。
优化：通过选择更优的基准值（如“三数取中”：首、尾、中间元素的中位数）可避免最坏情况，实际应用中平均性能接近 O(nlogn)。
总结：
时间复杂度：最好/平均 ，最坏 。
空间复杂度：最好/平均 ，最坏 。
选择排序
核心思想是：将数组分为已排序和未排序两部分，每次从未排序部分中选出最小（或最大）的元素，将其放到已排序部分的末尾。
简单(直接)选择排序
算法逻辑
将整个序列看作两部分：
左一部分：有序序列（初始时只有第一个元素）
右一部分：无序序列（除有序序列以外）
假设当前无序序列的第一个元素是最小的。
从无序序列第二个元素开始的元素中，依次与 无序序列的第一个元素进行比较。
如果找到某个元素比其还要小，就将两个元素进行交换。
此时，有序序列的元素加1，无序序列的元素减1
重复上述，直到无序序列为空
时空消耗
1. 时间复杂度
简单选择排序的核心是：每次从无序区中选择最小（或最大）元素，与无序区首元素交换。其时间消耗主要来自两部分：
比较次数：
无论数据初始状态如何（是否有序），都需要完整地遍历无序区以找到最小值。
第1趟（n个元素）：需比较 n−1次（比较无序区前n-1个元素与首元素）。
第2趟（n-1个元素）：需比较 n−2次。
…
第 n−1趟（2个元素）：需比较 1次。
总比较次数为：(n−1)+(n−2)+⋯+1=
≈
，即 （平方阶）。
交换次数：
每趟仅需交换1次（将最小元素与无序区首元素交换），最多交换 n−1次（当每趟都需交换时）。交换次数与数据初始状态无关，为常数级 O(n)。
总时间复杂度：由主导的比较次数决定，为 O(n2)（无论最好、最坏或平均情况，均为平方阶）。
2. 空间复杂度
简单选择排序是原地排序（In-place Sort），仅需常数级别的额外空间：
用于记录当前最小元素的位置（如一个临时变量
minIndex
交换元素时的临时存储（如一个临时变量
temp
空间复杂度：O(1)（仅使用固定大小的辅助空间）。
总结
简单选择排序的优势是交换次数少（最多 n−1次），但实际效率较低（时间复杂度 O(n2)），通常用于小规模数据或对交换操作敏感的场景（如硬件限制交换成本高时）。
树形选择排序
核心思想是：利用完全二叉树的结构来选出序列中的最小值（或最大值），然后反复进行这个过程，直到所有元素有序。
算法逻辑
第一步：构建初始树（选出最小值）
构建完全二叉树：将n个叶子节点(序列元素)放置在这棵树的底层，每个叶子节点代表一个待排序的元素。如果n不是2的幂次方，则用空节点（或一个极大值）补齐到最近的2的幂次方，以保证树是完全二叉树。
从最顶层的叶子节点开始，让其左右两个孩子进行比较，将较小的那个值存入新的叶子节点。重复其直到根节点(叶子节点只有一个元素)，树的根节点值就是整个序列的最小值。
第二步：输出最小值并重构树以寻找次值
将根节点的值取出，作为排序后的第一个元素。
找到最小值在原始叶子节点中的位置。将这个叶子节点的值改为一个无穷。
然后，从这个被修改的叶子节点开始，沿着它到根节点的路径，自下而上重构树。
重复第二步到直到树的大小变为 1
时空消耗
树形选择排序（又称锦标赛排序）是一种利用完全二叉树结构选择最小（或最大）值的排序算法，其核心是通过树形比较逐步筛选出有序序列。以下是其时间和空间复杂度的详细分析：
一、时间复杂度
树形选择排序的时间消耗主要集中在构建初始树和重复筛选剩余元素两个阶段：
1. 构建初始树（选出最小值）
初始时，将
n
n
m
m ≥ n
树的高度为
h = ⌈log₂m⌉
h
每个内部节点需比较其左右子节点的值（取较小值），总比较次数为叶子节点数减 1（即
m - 1
m
n
2. 重复筛选剩余元素（找次小值、第三小值等）
每次选出最小值后，需将该叶子节点的值设为无穷大（表示已选出），并沿该节点到根的路径自底向上重新比较（重构树），直到根节点再次得到当前最小值。
每次重构树的比较次数为树的高度
h
n
n
总比较次数为
n × h
h = ⌈log₂m⌉ ≈ O(log n)
m
n
综合时间复杂度
构建初始树的 O(n) 可忽略，主导时间为 O(n log n)。因此，树形选择排序的时间复杂度为 O(n log n)（与堆排序相同）。
二、空间复杂度
树形选择排序的空间消耗主要用于存储完全二叉树结构：
若直接使用数组模拟二叉树（索引
i
2i+1
2i+2
(i-1)//2
m
m
m ≤ 2n
此外，无需额外辅助空间（比较过程仅需临时变量）。
因此，空间复杂度为 O(n)（因
m
n
总结
|
指标 |
树形选择排序 |
|---|---|
|
时间复杂度 |
O(n log n)（比较次数主导） |
|
空间复杂度 |
O(n)（存储树结构的数组） |
注：尽管时间复杂度与堆排序相同，但树形选择排序因需补全叶子节点（可能浪费空间）且重构树时需多次比较路径上的节点（实际效率低于堆排序），因此未被广泛采用，堆排序是更优的选择类排序算法。
堆排序
堆排序利用二叉堆（完全二叉树）这种数据结构进行排序。
核心概念
二叉堆：
一个近似完全二叉树的结构。
大顶堆：每个节点的值都大于或等于其子节点的值。因此，堆顶元素是最大值。
小顶堆：每个节点的值都小于或等于其子节点的值。因此，堆顶元素是最小值。
堆通常用数组来表示。对于索引为
i
其左子节点索引：
2 * i + 1
其右子节点索引：
2 * i + 2
其父节点索引：
(i - 1) // 2
堆的两个关键操作：
建堆：将一个无序数组构建成堆。
堆化：当某个节点的值发生变化时，重新调整以维护堆的性质。通常有两种情况：
下沉：从根节点开始，如果它比子节点小，就与最大的子节点交换，然后继续对交换后的位置进行下沉。这是堆排序中最常用的操作。
上浮：从最后一个非叶子节点开始，如果它比父节点大，就与父节点交换，然后继续对交换后的位置进行上浮。（在建堆初期使用）
算法逻辑
堆排序主要分为两个大的阶段：建堆和排序。我们以升序排序为例，此时需要构建一个大顶堆。
阶段一：构建大顶堆
目标：将输入的无序数组调整为一个大顶堆。
方法：从最后一个非叶子节点开始，向前依次对每个节点执行下沉操作。
为什么从后往前？
因为叶子节点本身已经是一个合法的堆（只有一个节点）。我们从最后一个非叶子节点开始，可以确保当我们处理到某个节点时，它的左右子树已经是堆了。这样我们只需关注当前节点与其子节点的关系即可完成堆化。
步骤：
找到最后一个非叶子节点的索引：
last_non_leaf = (n // 2) - 1
从这个索引开始，递减至 0，对每个节点执行下沉操作。
阶段二：排序
利用大顶堆的特性进行排序。
方法：反复执行以下两步，直到堆的大小变为 1。
交换：将堆顶元素（当前最大值，
arr[0]
arr[i]
i
缩小堆范围并堆化：堆的大小减 1（排除掉刚刚放好位置的那个最大值），并对新的堆顶元素执行下沉操作，以恢复大顶堆的性质。注意，此时下沉操作的范围仅限于
[0, i-1]
时空消耗
堆排序的时间复杂度和空间复杂度分析如下：
一、时间复杂度
堆排序的时间复杂度主要由两个阶段决定：建堆阶段和排序阶段。
1. 建堆阶段（以大顶堆为例）
目标是将无序数组调整为大顶堆。调整方法是从最后一个非叶子节点开始，向前依次对每个节点执行“下沉”操作（堆化）。
最后一个非叶子节点的索引：对于长度为 n的数组，最后一个非叶子节点的索引为 last_non_leaf = floor(n / 2) – 1（从0开始计数）。
下沉操作的时间：对于一个高度为 h的节点，下沉最多需要比较和交换 h次（沿树的高度向下调整）。
总比较次数：堆的高度为 log₂n，各层节点数与高度的关系为：第 k层（根为第0层）有 2k个节点，每个节点下沉次数为 k。因此，总比较次数为：
（具体推导可通过数学归纳法证明，建堆阶段的时间复杂度为 O(n)）。
2. 排序阶段
排序阶段需执行 n−1次“交换堆顶与末尾元素 + 堆化”操作：
每次交换后，堆的大小减1（排除已确定的最大值），并对新的堆顶执行下沉操作。
第 i次堆化的堆大小为 n−i，下沉操作的时间与该堆的高度成正比（高度为 log₂(n−i)）。
总时间复杂度为：
综合时间复杂度
建堆阶段 O(n)+ 排序阶段 
，因此堆排序的总时间复杂度为 O(nlogn)（最好、最坏、平均情况均为此复杂度）。
二、空间复杂度
堆排序是原地排序（In-place Sort），仅需常数级别的额外空间：
排序过程中仅使用少量临时变量（如交换元素时的中间变量、指针索引等），无需额外的数组或数据结构。
因此，空间复杂度为 O(1)（不考虑输入数据本身的存储）。
总结
|
指标 |
复杂度 |
说明 |
|---|---|---|
|
时间复杂度 |
|
建堆 O(n)+ 排序 O(nlogn)，与数据分布无关 |
|
空间复杂度 |
O(1) |
原地排序，仅需常数额外空间 |
补充：堆排序是不稳定排序（例如，数组中两个相同关键字的元素可能因交换堆顶与末尾元素而改变相对顺序）。
归并排序
归并排序（Merging Sort)就是将两个或两个以上的有序表合并成一个有序表的过程。
2路归并
核心思想是：将两个已经排好序的序列，通过两两比较的方式，合并成一个新的、完整的有序序列。
算法逻辑
假设我们有两个已排序的数组（或同一个数组中的两个连续段）：
左段 (Left)：
L[low ... mid]
右段 (Right)：
R[mid+1 ... high]
我们的目标是将它们合并到原数组
A[low ... high]
A
准备阶段：
创建一个临时数组（或直接操作），用于存放合并过程中的结果。设置三个指针：
i
low
j
mid+1
k
low
比较与合并阶段：
循环执行以下步骤，直到其中一个子序列被完全遍历完：比较
L[i]
R[j]
将较小的那个值放入目标位置
A[k]
i++
j++
k++
处理剩余元素阶段：
当其中一个子序列的元素全部被取完后，另一个子序列中剩下的所有元素（它们本身已经是升序/降序的）直接按顺序复制到目标数组的剩余位置即可。因为它们都比之前合并的所有元素大（或小）。此时，
A[low ... high]
时空消耗
归并排序（以2路归并排序为例）的时间复杂度和空间复杂度分析如下：
一、时间复杂度
归并排序的核心是分治策略：将序列递归地分成两半，分别排序后合并。其时间复杂度可通过递推公式或主定理分析：
递推分析
分解：将长度为 n的序列分成两半，耗时 O(1)（仅计算中间位置）。解决：递归排序两个长度为 n/2的子序列，总时间为 2T(n/2)。合并：合并两个有序子序列（长度各为 n/2），需遍历所有 n个元素，耗时 O(n)。
因此，递推公式为：
求解递推公式
根据主定理（Master Theorem），对于 ：
此处 a=2, b=2, f(n)=O(n)，满足 
（因 
）。
属于主定理情况2，解为 T(n)=。
具体表现
无论输入数据的初始状态（是否有序），归并排序的比较和合并操作次数固定，因此：
最好、最坏、平均时间复杂度均为 。
二、空间复杂度
归并排序的空间消耗主要来自合并阶段的临时存储：
合并过程的临时空间
合并两个有序子序列（如
left
right
合并
arr[low...mid]
arr[mid+1...high]
临时数组的最大长度不超过 n（当合并整个序列时）。
递归栈空间（可选）
若采用递归实现归并排序，递归深度为 
（因每次分解为两半，树高为 
），每层递归仅需常数空间存储参数（如
low
mid
high。
总空间复杂度
非递归（迭代）实现：仅需临时数组的 O(n)空间（递归栈可忽略）。
递归实现：临时数组 O(n)+ 递归栈 O(logn)，总体仍为 O(n)（因 n主导）。
总结
|
指标 |
归并排序（2路） |
|---|---|
|
时间复杂度 |
|
|
空间复杂度 |
O(n)（主要来自临时数组） |
注：归并排序是稳定排序（合并时若两元素相等，优先取左子序列元素，保持原顺序），且适合大规模数据或需要稳定性的场景（如对象排序）。
基数排序
前述各类排序方法都建立在关键字比较的基础上，而分配类排序不需要比较关键字的大小，它是根据关键字中各位的值，通过对待排序记录进行若干趟“分配”与“收集”来实现排序的，是一种借助于多关键字排序的思想对单关键字进行排序的方法。基数排序（Radix Sorting）是典型的分配类排序。
核心思想是：从最低有效位到最高有效位（或反过来），依次对每一位进行稳定的排序。
算法逻辑
基数排序主要有两种方法：
LSD（Least Significant Digit first）：从最低位开始排序。通常更常用，尤其适用于整数排序。
MSD（Most Significant Digit first）：从最高位开始排序。适用于字符串、卡片排序等。
LSD：
找到最大值，确定最大位数
以元素的第i位(初始值最低位-1)的值(不存在为默认(看情况))进行排序，i值加1重复其，直到最大位数
MSD：与LSD差不多
时空消耗
基数排序（Radix Sort）是一种非比较型的分配类排序算法，其核心是通过对关键字的每一位（或每一位组）进行多次“分配-收集”操作实现排序。其时空复杂度分析如下：
一、时间复杂度
基数排序的时间复杂度与关键字的位数 d、待排序元素数量 n、基数 r（每一位的可能取值个数，如十进制 r=10，二进制 r=2）直接相关。
1. 核心公式
基数排序的时间复杂度可表示为：
T(n)=O(d⋅(n+r))
其中：
d：关键字的最大位数（如排序三位数时 d=3）；
n：待排序元素的数量；
r：基数（每一位的可能取值数，如十进制 r=10）。
2. 具体分析
基数排序的过程是按位处理：从最低位（LSD）或最高位（MSD）开始，对每一位进行一次“分配-收集”操作。每一轮操作包含两步：
分配：将元素根据当前位的值分配到 r个桶（队列）中，耗时 O(n)（遍历所有元素）；
收集：按桶的顺序（从0到 r−1）将所有元素重新收集到原数组中，耗时 O(r+n)（r个桶的遍历 + n个元素的收集）。
因此，每一轮的时间复杂度为 O(n+r)。若关键字有 d位，则总时间复杂度为 O(d⋅(n+r))。
3. 常见场景下的简化
实际应用中，若关键字的位数 d远小于 n（如排序整数时 d通常为常数，如32位整数 d=32），且基数 r较小（如十进制 r=10），则 d⋅r可视为常数，此时时间复杂度近似为 O(n)。
例如：
对 n个十进制数（r=10，d为常数），时间复杂度为 O(n)；
对 n个32位整数（r=28=256分字节处理，d=4字节），时间复杂度为 O(4⋅(n+256))≈O(n)。
二、空间复杂度
基数排序的空间复杂度主要取决于辅助空间的使用：
桶的数量：需要 r个桶（队列或数组），每个桶最多存储 n个元素（极端情况下所有元素在同一桶）；
临时存储：收集阶段可能需要临时数组存储结果（但通常可直接覆盖原数组）。
因此，空间复杂度为：
S(n)=O(n+r)
其中：
n：临时存储元素所需的空间（最坏情况所有元素在一个桶）；
r：桶的数量（每个桶的基础空间）。
优化说明
若采用链表或动态数组实现桶，可进一步减少空间浪费（如空桶不预分配空间），但实际分析中通常仍按 O(n+r)计算。对于常见基数（如 r=10或 r=256），r远小于 n，因此空间复杂度可简化为 O(n)（主要是存储元素本身的临时空间）。
总结
|
指标 |
时间复杂度 |
空间复杂度 |
说明 |
|---|---|---|---|
|
基数排序 |
O(d⋅(n+r)) |
O(n+r) |
d为关键字位数，r为基数；实际应用中常近似 O(n)（当 d较小时）。 |
关键结论：基数排序的时间复杂度与关键字的位数和基数相关，在数据位数较少时（如整数、短字符串）效率极高；空间复杂度主要由桶数量和临时存储决定，实际应用中通常为线性级别 O(n)。
外部排序
外部排序是一种用于处理无法全部装入内存的海量数据的排序算法。当待排序的数据量非常大，以至于计算机的内存（RAM）不足以一次性容纳所有数据时，我们就需要使用外部排序。
它的核心思想是：将大数据集分解成多个可以放入内存的小数据集，分别对这些小数据集进行排序，然后再将这些有序的小数据集合并成一个完全有序的大数据集。
算法逻辑
阶段一：生成初始归并段
分段：将整个输入文件分成若干个大小等于或略小于内存容量的段。内部排序：依次将每个段读入内存，使用高效的内部排序算法（如快速排序、堆排序、归并排序）对其进行排序。写回磁盘：将排好序的每个段（称为一个归并段 或 Run）写回到磁盘上。
经过这一阶段，我们得到了
k
阶段二：多路归并
这是外部排序的核心，目的是将多个有序的归并段合并成一个大的有序文件。
选择归并路数：确定每次要合并多少个归并段（例如，2路归并、3路归并等）。路数越多，最终产生的归并段越少，但需要的缓冲区也越多。
分配缓冲区：为输入归并段和输出结果在内存中分配缓冲区。通常，每个输入归并段需要一个输入缓冲区，还需要一个输出缓冲区。
归并过程：
从每个输入归并段的输入缓冲区中取一条记录进行比较。
选出最小（或最大）的记录，放入输出缓冲区。
当输出缓冲区满时，将其内容写入磁盘。
当一个输入缓冲区的记录取空时，再从对应的归并段中读取下一批数据来填充它。
重复：重复上述过程，直到所有归并段都合并成一个大的有序文件。
时空消耗
外部排序的时间复杂度和空间复杂度与其核心流程（生成初始归并段、多路归并）密切相关，具体分析如下：
一、时间复杂度
外部排序的时间主要由两部分构成：生成初始归并段的时间和多路归并的时间。
1. 生成初始归并段的时间
过程：将大文件划分为大小为 M（内存容量）的段，每段读入内存后用内部排序（如快速排序、堆排序，时间复杂度 O(MlogM)）排序，再写回磁盘。
总时间：设文件总大小为 N，则初始归并段数量为 k=⌈N/M⌉。每段排序时间为 O(MlogM)，因此生成所有归并段的时间为：
（因 k⋅M≈N）。
2. 多路归并的时间
核心操作：每次从 m个归并段中各取一个元素比较，选出最小（或最大）元素写入输出缓冲区，直到所有元素归并完成。
比较次数：归并 k个长度为 M的段（总长度 N），需进行 k−1趟归并（每趟将段数减少）。每趟归并的比较次数为 O(N)（每个元素需参与一次比较），因此总比较次数为 O((k−1)⋅N)。
I/O 时间：每趟归并需读取所有段（O(N)数据）并写回结果（O(N)数据），因此 I/O 时间与 N成正比。
总时间：归并阶段的时间复杂度为 O(Nlogmk)（其中 m为归并路数，k为初始归并段数）。当 m增大时，logmk减小（段数减少更快），但实际受内存限制（需为每个段分配输入缓冲区），m不能无限大。
综合时间复杂度
外部排序的总时间由生成归并段的时间和归并时间共同决定，可表示为：
时间复杂度=
其中 k=⌈N/M⌉，因此 logmk=logm(N/M)。若 M远小于 N（如 N为 TB 级，M为 GB 级），logmk主导整体复杂度，故通常简化为 O(NlogN)（与内部排序同阶，但常数更大）。
二、空间复杂度
外部排序的空间主要用于内存缓冲区和临时存储：
1. 内存缓冲区
多路归并时，需为每个输入归并段分配一个输入缓冲区（通常大小为 B），以及一个输出缓冲区。假设内存容量为 M，则最多支持 m=⌊M/B⌋路归并（m为归并路数）。
缓冲区总占用空间为 O(m⋅B)=O(M)（因 m⋅B≤M）。
2. 临时存储（初始归并段）
生成初始归并段时，每个段需暂存于内存（大小 M）后写回磁盘，磁盘上的临时文件总大小为 N（与原数据相同）。但这是外存空间，不计入算法的额外空间复杂度。
综合空间复杂度
外部排序的额外空间复杂度（仅考虑内存）为 O(M)（M为内存容量）。若需优化归并路数 m，可能需要更小的缓冲区，但通常 M是给定的硬件限制，因此空间复杂度可视为 O(M)。
总结
|
指标 |
分析 |
|---|---|
|
时间复杂度 |
主要由归并阶段的比较和 I/O 决定，约为 O(NlogN)（与内部排序同阶，但常数更大）。 |
|
空间复杂度 |
额外内存空间为 O(M)（M为内存容量），主要用于缓冲区管理。 |
关键结论：外部排序的效率瓶颈在于 I/O 操作（读写磁盘），因此优化方向包括：
增大内存 M（减少初始归并段数 k）；
提高归并路数 m（减少归并趟数）；
使用更高效的内部排序算法（如快速排序）生成初始归并段；
优化缓冲区管理（减少磁盘读写次数）。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
相关文章
暂无评论...
