排序的基本概念
排序是指将表中的元素重新排列，使其按关键字有序的过程。
算法的稳定性：若待排序表中有两个元素RiRj，则其关键字相同（keyi = keyj），且排序前Ri位于Rj之前；若使用某排序算法后，Ri仍位于Rj之前，则称这个算法是稳定的；否则，称之为不稳定的
内部排序
插入排序
基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列，直到所有记录都插入完毕
直接插入排序
基本思想：将待排序序列分为已排序和未排序两部分。初始时，将第一个元素视为一个有序序列。然后，从未排序的部分依次取出每一个元素，在已排序的序列中从后向前扫描，找到相应的位置并插入，直到所有元素都插入完毕。在寻找插入位置的过程中，需要将比当前元素大的元素依次向后移动。
性能分析
空间效率：空间复杂度O(1)
时间效率：时间复杂度O(n2)
稳定性：稳定
适用性：适用于顺序存储和链式存储的线性表
折半插入排序
基本思想：是直接插入排序的一种优化。同样是将序列分为已排序和未排序两部分。区别在于，在寻找当前元素在已排序序列中的插入位置时，不再使用顺序查找，而是利用已排序序列的有序性，采用折半查找（二分查找）来确定插入位置。找到位置后，再统一将后面的元素后移，然后插入元素。这减少了比较次数，但移动次数并未改变。
性能分析
空间效率：空间复杂度O(1)
时间效率：时间复杂度O(n2)
稳定性：稳定
适用性：仅适用于顺序存储的线性表
希尔排序
基本思想：也称为“缩小增量排序”。它是对直接插入排序的改进。先将整个待排序的记录序列分割成若干个子序列（由相隔某个“增量”的元素组成）分别进行直接插入排序。然后逐步缩小增量，对全体元素进行粗略的调整，使序列基本有序。当增量缩小为1时，再对全体元素进行一次直接插入排序。由于在前期，元素能够较快地移动到大致位置，因此整体效率比直接插入排序高。
性能分析
空间效率：空间复杂度O(1)
时间效率：时间复杂度O(n1.3)
稳定性：不稳定
适用性：仅适用于顺序存储的线性表
交换排序
冒泡排序
基本思想：通过对待排序序列从前向后（或从后向前），依次比较相邻元素的值，若发现逆序则交换，使值较大（或较小）的元素逐渐从前移向后部（或从后移向前部），就像水底的气泡一样逐渐向上冒。经过多轮这样的操作，每轮都会将当前未排序部分的最大（或最小）元素“冒泡”到最终位置，直到整个序列有序。
性能分析
空间效率：空间复杂度O(1)
时间效率：时间复杂度O(n2)
稳定性：稳定
适用性：适用于顺序存储和链式存储的线性表
快速排序
基本思想：采用分治策略。在待排序序列中任选一个元素作为基准（pivot），通过一趟排序将待排序列分成独立的两部分，其中一部分的所有元素都比基准小，另一部分的所有元素都比基准大（如果按升序排序）。然后，再递归地对这两部分分别进行快速排序，以达到整个序列有序。整个过程是一个不断递归、层层划分的过程。
性能分析
空间效率：空间复杂度O(log2n)
时间效率：时间复杂度O(nlog2n)
稳定性：不稳定
适用性：仅适用于顺序存储的线性表
选择排序
简单选择排序
基本思想：将序列分为已排序和未排序两部分。每一趟排序，在未排序的部分中找到最小（或最大）的元素，将其与未排序部分的第一个元素交换位置。这样，每一趟都会将一个元素放到它的最终位置上。经过 n-1 趟，整个序列就变得有序。
性能分析
空间效率：空间复杂度O(1)
时间效率：时间复杂度O(n2)
稳定性：不稳定
适用性：适用于顺序存储和链式存储的线性表
堆排序
基本思想：利用堆（一种特殊的完全二叉树结构）进行排序。首先，将待排序的序列构建成一个大顶堆（升序排序时）或小顶堆（降序排序时），此时堆顶元素就是整个序列的最大值（或最小值）。将堆顶元素与堆的末尾元素交换，此时末尾元素即为有序区的第一个元素。然后，将剩余 n-1 个元素重新调整为一个堆，如此反复执行，便能得到一个有序序列。
性能分析
空间效率：空间复杂度O(1)
时间效率：时间复杂度O(nlog2n)
稳定性：不稳定
适用性：仅适用于顺序存储的线性表
归并排序
基本思想：采用经典的分治策略。首先将待排序序列分成若干个子序列，每个子序列是有序的（初始时，每个子序列长度为1，认为是有序的）。然后再将有序的子序列两两合并，得到更长的有序序列。这一过程称为归并。重复这个过程，直到将所有子序列合并成一个有序序列为止。归并排序通常采用递归实现。
性能分析（2路归并）
空间效率：空间复杂度O(n)
时间效率：时间复杂度O(nlog2n)
稳定性：稳定
适用性：适用于顺序存储和链式存储的线性表
基数排序
基本思想：是一种非比较型整数排序算法。它将整数按位数切割成不同的数字，然后按每个位数分别进行比较。具体来说，它按照“低位优先”或“高位优先”的规则，将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次稳定的排序（如利用计数排序或桶排序作为子过程）。这样从最低位一直到最高位排序完成后，整个序列就变成了一个有序序列。
性能分析
r = 队列个数；n = 元素个数；d = 关键字的分量（例：999分量为k3,k2,k1）
空间效率：空间复杂度O(r)
时间效率：时间复杂度O(d(n + r))
稳定性：稳定
适用性：适用于顺序存储和链式存储的线性表，链式结构尤其合适
计数排序
基本思想：是一种非比较型排序算法，适用于范围较小的整数排序。它不通过比较元素大小，而是利用数组下标来确定元素的正确位置。具体做法是，创建一个计数数组C，其长度等于待排序数组中整数的范围。然后遍历待排序数组A，统计每个整数出现的次数，存入计数数组C对应的下标中。最后，根据计数数组C中统计的次数，将元素依次放回原数组，从而完成排序。计数排序的核心在于将输入的数据值转化为键存储在额外的数组空间中。
性能分析
n = 输出数组的长度；c = 计数数组的长度
空间效率：空间复杂度O(n + k)
时间效率：时间复杂度O(n + k)
稳定性：稳定
适用性：适用于顺序存储的线性表
各种内部排序算法的比较
| 算法种类 | 时间复杂度 | 空间复杂度 | 是否稳定 | ||
|---|---|---|---|---|---|
| 最好情况 | 平均情况 | 最坏情况 | |||
| 直接插入排序 | O(n) | O(n2) | O(n2) | O(1) | 是 |
| 希尔排序 | --- | --- | --- | O(1) | 否 |
| 冒泡排序 | O(n) | O(n2) | O(n2) | O(1) | 是 |
| 快速排序 | O(nlog2n) | O(nlog2n) | O(n2) | O(log2n) | 否 |
| 简单选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 否 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 否 |
| 2路归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 是 |
| 基数排序 | O(d(r + n)) | O(d(r + n)) | O(d(r + n)) | O(r) | 是 |
外部排序
在对大规模文件进行排序时，由于记录数量庞大，无法将整个文件一次性装入内存。此时，待排序记录必须存储在外存上中，排序时仅能将部分数据调入内存处理，并通过多次内外存之间的数据交换，逐步完成整体排序。
外部排序的方法
外部排序通常采用归并排序的策略
- 生成初始归并段
- 多路归并
增大归并路数可有效减少归并趟数，从而显著降低总的I/O次数
败者树
基本思想：败者树是一种常用于多路归并（如外部排序中的多路归并）的数据结构，用于快速地从 k 个有序序列（或归并段）中选出当前最小的元素。它是一棵完全二叉树。
- 叶子节点：存储各个归并段当前参与比较的元素（或者指向这些元素的指针）。
- 内部节点：记录的是在该节点所代表的子树的比较中，"失败者"（即较大者）来自哪个段，而"胜利者"（即较小者）则继续向上与兄弟节点比较。根节点的上方通常会有一个节点记录最终的"胜利者"（即全局最小元素）来自哪个段
优势：当取出全局最小元素后，需要从其所在的段中取出下一个元素补入叶子节点。此时，只需要沿着该叶子节点到根节点的路径，与路径上每个内部节点记录的"失败者"重新进行比较，就能快速得到新的全局最小元素。相比于传统的多路归并每选出一个元素都需要比较 k-1 次，败者树能将比较次数减少到 ⌈log2k⌉⌈log2k⌉ 次，从而提高了归并效率
置换选择排序
基本思想：置换选择排序是外部排序中用于生成初始归并段的一种算法，它比传统的按内存大小直接等分输入文件生成归并段的方法，能生成更少、更长的归并段，从而减少后续归并的趟数。
核心步骤：
- 从输入文件中读取尽可能多的记录到内存工作区（大小为 w），直到工作区满
- 从工作区中选出关键字最小的记录（设为 MINIMAX），输出到归并段文件中
- 再从输入文件中读取下一条记录，替换刚才输出的记录的位置
- 如果新读入的记录的关键字大于等于刚刚输出的 MINIMAX，则它可以参与当前归并段的构建（即放入工作区，等待后续选择）
- 如果新读入的记录的关键字小于 MINIMAX，则它不能归入当前归并段（因为会导致归并段不是递增有序的），应将其暂时保留在工作区中，但标记为属于下一个归并段
- 重复步骤 2-5，直到工作区中的所有记录都属于下一个归并段（即工作区中所有记录的关键字都小于当前输出的 MINIMAX，无法继续生成当前归并段）。此时，当前归并段结束，开始生成下一个归并段
结果：通过这种方式，生成的初始归并段的平均长度约为内存工作区大小的 2 倍，有效减少了归并段的数量
最佳归并树
基本思想：最佳归并树是外部排序中，用于组织多个归并段进行归并，使得总的I/O次数（即读写磁盘的次数）最少的一种带权路径长度最短的树。它本质上是数据结构中的**哈夫曼树（Huffman Tree）**思想在多路归并中的应用。
概念：假设有 n 个初始归并段，每个归并段的长度（即包含的记录数）作为叶子节点的权值。进行 k 路归并时，构造一棵所有叶子节点为初始归并段、且只有度为 0 和度为 k 的节点的 k 叉树。这棵树的总带权路径长度（WPL）即为归并过程中总共需要读/写的记录数
构造方法：为了使总的I/O次数最小，需要将长度最短的归并段优先合并。这与哈夫曼树的构造过程类似，但需要注意一个重要问题：最后一次归并可能不是完整的 k 路归并。为了保证所有归并段都能参与归并，且树的每个内部节点都有 k 个分支（除了可能不满的最后一层），通常需要添加长度为0的虚段，使得总的叶子节点数 nn 满足 (n−1)mod (k−1)=0(n−1)mod(k−1)=0。然后，反复从集合中选出 k 个权值最小的归并段（或已归并生成的段）进行合并，形成一个新的节点（其权值为这 k 个节点权值之和），直到所有节点合并为一棵树。这棵树就是最佳归并树，对应的归并方案能保证磁盘读写次数最少