没有最优的排序方法，根据不同的情况选择合适的方法，有时甚至可以结合使用
排序：将一组任意排列的数据元素序列，重新排列成一个按关键字有序（升序或降序）的序列
如果参加排序的数据结点包含多个数据域，那么排序往往针对其中某个域而言
按待排序记录所在位置
内部排序：待排序记录存放在内存
外部排序：排序过程中需对外存进行访问的排序
按排序依据规则
插入排序：直接插入排序、折半插入排序、希尔排序
交换排序：冒泡排序、快速排序
选择排序：简单选择排序、树型选择排序、堆排序
归并排序：2-路归并排序
基数排序
10.2 插入排序
基本思想：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。
即：边插入边排序，保证子序列中随时都是排好序的。
在有序序列中插入一个元素，保持序列有序，有序长度不断增加
起初，a[1]是长度为1的子序列。然后逐一将a[2]-a[n]插入到有序子序列中
插入排序的种类：
直接插入排序
其他插入排序
希尔排序
直接插入排序
采用顺序查找法确定插入位置
我们把顺序表 L.r[1..L.length] 看成数组，排序过程是：
- 维护一个“已排序区”
- 当外层循环走到 i 时，默认 L.r[1..i-1] 已经是有序的
- 现在要把 L.r[i] 这个新元素插进这段有序区，使得 L.r[1..i] 有序
- 如果 L.r[i]已经不小于前一个，就不用插
- 若 L.r[i].key >= L.r[i-1].key，说明它就在正确位置（有序区末尾），这一趟不做移动
- 否则就执行“插入
- A. 复制插入元素到哨兵位
- L.r[0] = L.r[i]0 号位只是临时存 key 的“安全位置”。
- B. 已排序区里比它大的都右移
- 从 i-1 往左扫：只要 L.r[j].key > L.r[0].key，就把 L.r[j] 右移到 L.r[j+1]
- C. 插入到空出来的位置
- 最终停在某个 j，把哨兵放进 L.r[j+1]
哨兵的作用：有了哨兵 L.r[0]，内层循环不用写 j>=1 这种边界判断：
- 最极端情况（插到最前面），j 会退到 0。
- 当 j==0 时，条件 L.r[0].key < L.r[0].key 不成立，循环自然停止，不会越界
void InsertSort(SqList &L)
{
// i 从 2 开始：默认 L.r[1] 自己就是“已排序区”
for (i = 2; i <= L.length; ++i)
{
//LT(a,b)，若a小于b则返回真
// 如果当前元素比前一个小，说明它需要往左插入
if (LT(L.r[i].key, L.r[i-1].key))
{
// ① 把待插入元素先存到哨兵位（临时保存 key/记录）
L.r[0] = L.r[i];
// ② 先把前一个元素右移一格
把第 i-1 个元素复制到第 i 个位置，给后续“连续右移”开个头
// 这样做后，位置 i 先先腾出一格
L.r[i] = L.r[i-1];
// ③ 从已排序区的右端开始（i-2），向左找插入位置
// 只要哨兵的 key < 当前比较的 key，说明当前这个元素要右移
// 注意：这里不写 j>=1，是因为哨兵在 r[0]，退到 0 会自动停
for (j = i - 2; LT(L.r[0].key, L.r[j].key); --j)
{
// 把比待插入元素大的记录整体向右挪
L.r[j + 1] = L.r[j];
}
// ④ 循环结束时，j 指向“最后一个 <= 待插入元素”的位置
// 所以待插入元素应该放在 j+1
L.r[j + 1] = L.r[0];
}
// else：当前元素 >= 前一个元素，本来就有序，不动
}
}算法评价：
直接插入排序在基本有序时，效率较高，在待排序的记录个数较少时，效率较高
其他插入排序——折半插入排序
查找插入位置时采用折半查找法
和直接插入排序一样：每趟把 L.r[i] 插入到左边已排好序的 L.r[1..i-1] 里。
- 直接插入：用顺序查找找插入位置（从右往左比）。
- 折半插入：用二分查找找插入位置（low/high/mid）。但元素搬移（右移）次数不变，只是比较次数可能减少。
算法大致思路：
- 哨兵保存待插入元素
- L.r[0] = L.r[i];
- 在有序区 1..i-1 用二分查找定位插入点
- 初始化：low = 1，high = i – 1
- 循环：
- m = (low + high) / 2
- 如果 key < L.r[m].key：插入点在左半边 ⇒ high = m – 1
- 否则（key >= L.r[m].key）：插入点在右半边 ⇒ low = m + 1
- 循环结束条件：low > high
- 此时插入位置就是 high + 1（等价地也是 low）。
算法评价：
折半插入排序就平均性能来说比直接插入排序要快
它需要的关键字比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第i个对象时，需要经过⌊log_2i⌋+1次关键字比较，才能确定它应插入的位置：
当n较大时，总关键字比较次数比直接插入排序的最坏情况要好的多，但比其最好情况要差
在对象的初始排列已经按其关键字排好序或接近有序时，直接插入排序比折半插入排序的比较次数要少
时间复杂度：O(n2)
空间复杂度：O(1) 1个辅助空间
其他插入排序——2-路插入排序
为减少移动次数，增加n个辅助空间（数组d），但当首关键字为最大或最小时失去意义
空间复杂度：O(n)
其他插入排序——表插入排序
大致思路：
- 1）存储结构
- 用数组模拟链表：r[i].rc 存记录，r[i].next 存“下一个记录的下标”
- r[0] 是头结点：r[0].next 指向排序后第一个结点
为了减少记录移动：先只改 next 连成有序链，再把记录按链顺序搬到数组中。
算法两阶段
阶段A：建立有序链（逻辑排序）
- 从第 2 个记录开始，按关键字在已有链表中找插入位置
- 只修改 next 指针完成插入
- 不搬动记录本身 ⇒ 移动次数少
阶段B：重排记录 Arrange（物理排序）
- 目标：让数组 r[1..n] 本身按升序排列
- 从 p = r[0].next 开始沿链走，第 i 个结点应放到数组下标 i
- 若当前结点下标 p != i：交换 r[p] 与 r[i]，并修正相关 next
- 循环到 i = n-1，最终 r[1..n] 有序
希尔排序
先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序
希尔排序 = “多遍插入排序” + “逐步缩小间隔”
- 选一个增量序列 dlta[]（例如：n/2, n/4, …, 1）。
- 对每个增量 dk：
- 把序列按下标对 dk 取模分成 dk 组：第 1 组：1, 1+dk, 1+2dk, …第 2 组：2, 2+dk, 2+2dk, ………
- 每一组分别做一次直接插入排序（代码里通过 j -= dk 实现“组内向前比较与移动”）。
- 当 dk 最终变为 1 时，相当于对整个序列做一次普通插入排序；但此时序列已“基本有序”，所以效率更高。
// 希尔排序：按给定的增量序列 dlta[0..t-1] 依次做“按 dk 分组的插入排序”
void ShellSort(SqList &L, int dlta[], int t)
{
// k 表示当前使用第几个增量
for (k = 0; k < t; ++k)
{
// 对当前增量 dk=dlta[k] 执行一次“希尔插入”（分组插入排序）
ShellInsert(L, dlta[k]);
}
}
// 希尔插入：对间隔为 dk 的元素序列分别做直接插入排序
// 等价于：把数组按 dk 分成 dk 组，每组做一次插入排序（组内下标相差 dk）
void ShellInsert(SqList &L, int dk)
{
// 从第 dk+1 个元素开始（因为它前面 dk 个元素各自是每组的第一个）
for (i = dk + 1; i <= L.length; ++i)
{
// 如果当前元素比同组的前一个元素还小，说明需要向前“插入”
// 同组前一个元素位置是 i-dk
if (LT(L.r[i].key, L.r[i - dk].key))
{
// 哨兵：暂存待插入的记录，避免被覆盖
L.r[0] = L.r[i];
// j 从同组前一个位置开始，按 dk 递减向前找插入位置
// 条件：j>0 防止越界；且待插入 key < 当前比较 key，就继续后移
for (j = i - dk; j > 0 && LT(L.r[0].key, L.r[j].key); j -= dk)
{
// 把较大的记录向后移动 dk 个位置（仍在同一组内移动）
L.r[j + dk] = L.r[j];
}
// 找到位置后，把哨兵中的记录放入（插入到同组正确位置）
L.r[j + dk] = L.r[0];
}
// else：当前元素已经 >= 同组前一个元素，不用动
}
}10.3 快速排序
冒泡排序
对n个记录，依次比较相邻两个关键字，不满足条件，则交换—–一趟冒泡排序
优点：每趟结束时，不仅能让最大值走到最后面位置，还能同时部分理顺其他元素
如何提高效率：一旦某一趟比较时不出现记录交换，说明已排好序了，就可以结束本算法
// 冒泡排序（带“提前结束”标志位）
void sort(SqList &L)
{
// 外层：第 i 趟冒泡（最多 length-1 趟）
for (i = 1; i <= L.length - 1; i++)
{
flag = FALSE; // 本趟是否发生过交换（没交换说明已经有序）
// 内层：从前往后两两比较，把本趟最大值“冒”到末尾
// 末尾 i-1 个已经排好，所以只需到 length-i
for (j = 1; j <= L.length - i; j++)
{
// 如果前一个比后一个大，就交换（升序）
if (L.r[j].key > L.r[j + 1].key)
{
L.r[j] <--> L.r[j + 1]; // 交换相邻元素
flag = TRUE; // 记录发生过交换
}
}
// 如果这一趟一次交换都没有，说明整体已经有序，直接结束
if (!flag) break;
}
}
快速排序
基本思想：
通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序
快速排序流程
- 选基准（pivot）：在区间 [low, high] 里选一个元素当基准
- 划分 Partition：把区间重排成：
- 基准左边都 ≤ pivot
- 基准右边都 ≥ pivot并返回基准最终位置 pivotloc
- 分治递归：对基准左半 [low, pivotloc-1] 继续快排；对右半 [pivotloc+1, high] 继续快排
- 终止条件：当区间长度为 0 或 1（即 low >= high）时停止
- low 和 high 不是“数值大小的左右”，而是数组下标区间的左右边界。我们不断把区间越分越小，所以很容易出现：只剩 1 个元素：比如 [3,3]，这时 low == high
// 快速排序入口：对整个顺序表进行快速排序
void QuickSort(SqList &L)
{
// 从第 1 个到第 length 个元素整体排序（下标从 1 开始的写法）
Qsort(L, 1, L.length);
}
// 快速排序递归函数：对 L 的 [low, high] 区间排序
void Qsort(SqList &L, int low, int high)
{
// 递归结束条件：区间内至少要有 2 个元素才需要排
if (low < high)
{
// 划分：把区间按 pivot 分成两部分，并返回 pivot 最终位置
pivotloc = Partition(L, low, high);
// 递归排序 pivot 左边部分
Qsort(L, low, pivotloc - 1);
// 递归排序 pivot 右边部分
Qsort(L, pivotloc + 1, high);
}
}
// 一趟划分：选取 L.r[low] 为枢轴，把区间[low..high]调整成：
// 枢轴左边都 <= pivotkey，右边都 >= pivotkey，返回枢轴最终位置
int Partition(SqList &L, int low, int high)
{
// 用 0 号单元暂存枢轴记录（哨兵），避免枢轴被覆盖
L.r[0] = L.r[low];
// 取枢轴关键字（pivot）
pivotkey = L.r[low].key;
// low、high 两端向中间逼近
while (low < high)
{
// 从右往左找第一个 < pivotkey 的元素（>= pivot 的都留在右边）
while (low < high && L.r[high].key >= pivotkey)
--high;
// 找到了 < pivot 的元素，把它填到左边的“坑”里
L.r[low] = L.r[high];
// 从左往右找第一个 > pivotkey 的元素（<= pivot 的都留在左边）
while (low < high && L.r[low].key <= pivotkey)
++low;
// 找到了 > pivot 的元素，把它填到右边的“坑”里
L.r[high] = L.r[low];
}
// low == high 时，坑位相遇，把最初保存的枢轴放回这个位置
L.r[low] = L.r[0];
// 返回枢轴最终下标
return low;
}
最后的练习快速排序题期末肯定考
10.4 选择排序
简单选择排序
每一趟在n-i+1(i=1,2…,n-1)个记录中选择关键字最小的记录作为有序序列中第i个记录
排序过程：
第1趟：通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第1个记录交换
第2趟：通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第2个记录交换
第i趟：通过n-i次比较，从剩余的n-i+1个记录中找出关键字次小的记录，将它与第i个记录交换
重复上述过程，共进行n-1趟排序后，排序结束
// 简单选择排序：每一趟从未排序区间里选出最小元素，放到当前位置 i
void SelectSort(SqList &L)
{
// i 表示当前要放“第 i 小”的位置（已排序区末尾+1）
for (i = 1; i < L.length; ++i)
{
// 在区间 [i .. L.length] 中查找最小关键字的下标 j
j = SelectMinKey(L, i);
// 如果最小值不在当前位置 i，就交换到 i 位置
if (i != j)
L.r[i] <--> L.r[j]; // 交换 L.r[i] 和 L.r[j]
}
}算法评价：
树形选择排序
算法思路
大致思路
- 把每个待排序元素放到叶子结点（图里最底下一排）。如果叶子数不够凑成 2^k，就用 \infty 补齐（表示永远不会赢）。
- 两两比较：每个父结点保存它两个孩子里较小的那个（像比赛晋级）。这样一路比到根结点，根结点就是全体最小值。
- 输出最小值：把根结点的值写到结果数组的下一个位置。
- 删掉这个最小值：把它对应的叶子改成 \infty（表示它已经用过了）。
- 只沿着这条叶子到根的路径重新比较更新（不用整棵树重算）。
- 重复 3–5，直到输出完所有元素。
算法评价
堆排序
算法思路：
将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序
实现堆排序需解决两个问题
1、如何由一个无序序列建成一个堆？
2、如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？
如何由一个无序序列建成一个堆？
- 从最后一个有孩子的结点开始：i = ⌊n/2⌋
- 依次往前：i = n/2, n/2-1, …, 1
- 对每个 i 做一次“下滤/筛选”（sift down）：
如果是大根堆：让较大的孩子往上顶，直到父 ≥ 子- 如果是小根堆：让较小的孩子往上顶，直到父 ≤ 子
如何在输出堆顶元素后，调整剩余元素为一个新的堆：
小顶堆：
输出堆顶元素之后，以堆中最后一个元素替代之
然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换
重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”
算法评价：
- 比较次数同树形选择排序
- 时间复杂度O(nlogn)
- 空间复杂度O(1)
- 不稳定排序
10.5 归并排序
将两个或两个以上的有序表组合成一个新的有序表
2-路归并排序
设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1
两两合并，得到「n/2 ︳个长度为2或1的有序子序列
再两两合并，……如此重复，直至得到一个长度为n的有序序列为止
算法评价：
10.6 基数排序
最高位优先法（MSD)：先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列
最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，……依次重复，直至对最高位关键字k1排序后，便成为一个有序序列
按个位（最低位）分配/收集
按十位分配/收集（在上一趟结果基础上）
按百位分配/收集（最高位）
各种排序方法的综合比较
- 稳定排序：如果有两个元素“关键字相同”，排序后它们的相对先后顺序不变。
- 不稳定排序：关键字相同的元素，排序后它们的相对顺序可能改变。
习题：
