排序基本概念
- 输入n个记录，根据记录的关键字大小，输出该序列的重排，使得关键字有序
- 稳定算法：关键字大小相等的两条记录，在输入和输出中的先后顺序不变
- 内部排序：排序期间元素全部存放在内存，大部分内部排序是基于比较来移动记录顺序
- 外部排序：排序期间元素无法全部同时存放在内存，需要不断地在内外存之间移动的排序
插入排序
直接插入排序
算法步骤
- 假设排序表
在排序过程中处于以下状态：有序序列 无序序列 - 备份
- 找到元素
在 中的插入位置 - 将
整体依次后移1位，本步骤和上一步可以同时进行，即边移边找 - 将备份的
放入
算法性能
- 常数个辅助单元，空间开销
- 时间开销，最好情况
，平均和最坏情况 - 稳定排序算法
- 适用于顺序存储或链式存储的线性表
折半插入排序
- 对直接插入排序的优化：将比较和移动操作分离，先折半查找插入点，再统一进行移动
- 减少了比较元素的开销至
，但最坏时间复杂度还是 - 稳定排序算法
- 适用于顺序存储的线性表
希尔排序
算法步骤
- 取小于
的步长 ，距离间隔 的记录看作在同一组，组内直接插入排序 - 继续选更小的步长，重复该过程
- 直到步长选为1
- 注：目前对于步长序列怎么选择最好还没有定论
算法性能
- 空间开销O(1)
- 时间开销分析比较困难，最坏情况是
；当n在特定范围，时间复杂度 , - 不是稳定排序算法
- 适合顺序存储线性表
交换排序
冒泡排序
算法步骤
- 从前往后或从后往前扫描，比较相邻元素，逆序则交换
- 第k轮扫描，可以把第k大的元素放到倒数第k个位置，或把第k小的元素放到第k个位置
- 最坏进行n-1轮扫描即可完成排序
- 注：可以进一步优化，即记录每轮最后一次发生交换的位置，该位置后面的都已经排好；如果没有发生交换则可以提前结束排序
算法性能
- 空间开销
- 最坏情况和平均情况时间开销都是
，最好情况可以优化到 - 稳定排序算法
- 不同于插入排序，冒泡排序的有序子序列一定是全局有序（小于或大于所有无序序列的元素）
快速排序
算法步骤
- 选择一个基准pivot，例如第一个元素
- 将排序表划分为小于基准和大于等于基准两个部分，此时基准的位置是最终的位置
- 递归的对左右部分进行快排
- 若某部分只有一个元素，则该部分已经排序好
划分函数
- 双向法
- 例如基准为第一个元素，设置i和j两个指针，i指向基准，j指向最后的元素
- 先令j从后往前遍历，遇到比基准小的元素，则交换i和j元素
- 交换后令i从前往后遍历，遇到比基准大的元素，交换i和j元素
- 直到i和j相遇
- 事实上基准元素可以先进行备份，等确定最终位置再一次性放好
- 单向法
- 例如基准为第一个元素，设置i指针指向基准，j指针指向i下一个元素
- 令j从i+1位置向后遍历，遇到比基准小的元素，则交换i+1位置和j位置元素，再交换i和i+1位置元素
- 直到j扫描完整个表
性能分析
- 需要栈进行递归，平均空间开销
，最坏情况 - 平均时间复杂度
，最坏时间复杂度 ，可以尽量随机的选基准元素，使得最坏情况基本不发生 - 不是稳定算法，无论是划分函数是双向法还是单向法，因为交换元素时可能会导致不稳定
选择排序
简单选择排序
算法步骤
- n-1次循环
- 第i次循环从
中选出最小值和 交换 - 第i次循环也可以从
中选出最大值和 交换
性能分析
- 空间开销
- 最好、平均、最坏时间开销都是
，主要是比较的开销，移动的开销较小 - 默认数组实现不是稳定算法，比如
，用 替换左侧的 ，破坏了两个 的顺序 - 用链表实现则是稳定的
堆排序
堆结构
- 将一维数组看作完全二叉树，任意结点的值是对应子树的最大值或最小值
- 前者叫最大堆，后者叫最小堆
堆修复
- 假设堆顶缺失，对于结构上的修复，可以用数组末尾的结尾补到堆顶
- 对于性质上的修复，以最大堆为例，从堆顶开始，跟左右子结点比较
- 如果比左右子结点大，则完成修复
- 反之，将堆顶和左右子结点较大者交换，并继续修复子结点对应的子堆
- 修复的复杂度是
堆构建
- 非递归法
- 从最后一个有孩子的结点开始进行堆修复
- 复杂度O(n)，可以直接求和计算
- 递归法
- 先递归的将左右子树部分构建为堆
- 再对堆顶进行修复
- 复杂度O(n)，根据主定理算
堆排序步骤
- 以最大堆
为例，堆顶 和堆末尾元素 交换 - 修复堆
- 重复拿出堆顶，修复堆即可
堆插入
- 虽然堆排序用不到，这里补充一下堆结构的插入
- 思想是把插入元素放到末尾，再从底向上进行调整
- 开销是
堆排序性能
- 空间开销
- 时间开销
- 不是稳定排序算法
归并排序
- 归并排序是基于Merge操作的
- Merge操作把两个有序表合并，开销
- 归并排序先分治的排序两部分，再把两部分合并
- 空间复杂度
- 时间复杂度
- 稳定排序算法
- 如果是k路归并，由主定理，容易知道时间开销还是
基数排序
- 一种特殊的不基于比较的排序方法，而是基于关键字各个位的大小
- 可以按最高位优先MSD，也可以最低位优先LSD，但后者更常用和方便
- 假设关键字是d位，r进制数，以LSD为例
- 需要
到 ， 个链队列进行分配 - 重复进行分配和收集
- 第i次分配，根据关键字的低位起第i位的值，将关键字分配给对应的链队列
- 第i次收集，把各个链队列从
到 串起来 - 第i次分配和收集完成后，关键字的低i位是有序的
- 进行d次分配和收集后，排序完成
- 空间复杂度
，即队头指针、队尾指针 - 每次的分配复杂度
,收集复杂度 ,总的时间复杂度 ，与序列初始输入状态无关 - 稳定的排序算法
- 需要
排序算法应用
- 若n较小，可以采用直接插入排序或简单选择排序
- 若初始序列基本有序，适合采用直接插入排序或冒泡排序
- n较大时可以采用
的时间复杂度算法，如快速排序、堆排序、归并排序 - 快速排序是基于比较的内部排序中最好的方法，平均情况时间最短，但不是稳定排序
- 堆排序辅助空间少于快排，且最坏情况也是
，但不是稳定排序 - 归并排序是稳定排序，但空间开销较大。此外，可以考虑在序列较小时先直接插入排序，再高层归并，这样改进后还是稳定的。
- 基于比较的排序算法最坏时间复杂度下界是
，可以用判定树证明 - 如果n很大，且关键字位数少、可以分解的情况适合用基数排序
- 如果记录信息量大不适合频繁移动，可以选择链表作为存储结构
外部排序
基本概念
当对大文件进行排序时，因为文件太多，无法一次将整个文件放入内存，需要将待排序记录存储在外存，排序时再把数据一部分一部分调入内存排序，在排序过程中需要多次进行内存外存的交换，这种排序方法叫外部排序。
外部排序的方法
- 主要考虑访问磁盘的次数，即IO次数
- 首先根据内存情况，将文件分成若干子文件，依次读入内存进行内部排序
- 排序好后的子文件写回外存，这些子文件称为归并串或者顺串
- 对这些归并串归并直到整个文件有序
- 内存分成三个缓冲区，两个输入缓冲区和一个输出缓冲区，输入缓冲区空则继续从磁盘的对应归并串读，输出缓冲区满则写到磁盘中保存
举例说明
- 2000个记录，假设在8次内排序后得到8个初始归并串，每个归并串250个记录，每个磁盘块125个记录
- 8个归并串，两两归并，需要3轮归并
- 每轮归并需要16次读和16次写
- 三轮归并以及最开始内部排序需要的磁盘读写，一共4个32次，即128次读写
- 若增加归并路数，比如变成4路归并，则只需要两轮归并，一共3个32次，即96次读写
- 可以看出，增加归并路数、减小初始归并串数都可以减少归并轮数，从而减少IO次数
- 记忆：单轮归并中，每个记录都是进内存一次，出内存一次
多路平衡归并和败者树
- 增加归并路数可以减少读写磁盘的次数，但是增加了内部归并时的开销
- 具体来说，r个初始段，归并轮数
，每轮归并 个元素，比较次数 ，总比较次数和 有关，随着k增大而增大 - 解决方法是败者树
- 一种完全二叉树
- k个叶结点存放k个归并段当前参加比较的记录，内部结点用来保存失败者（较大者失败），胜利者继续向上比较，最终得到的胜利者就是当前选出的最小值
- 胜利者结点删除后，进来新的结点，只需要把新的结点到根的路径上的比较重进行一次即可更新败者树，因此可以认为每轮比较次数由
优化到了 ，从而总的比较次数和 无关 - 个人认为，用最小堆也可以起到差不多的效果
- 多路平衡归并的k也不是越大越好，因为路数k增加，需要增加输入缓冲区的个数，这对内存空间有要求，如果内存不够了，只能减小缓冲区大小，这样同样会使得读写外存次数增加
置换-选择排序
- 减少初始归并串数可以减少读写磁盘次数
- 采用内部排序法得到的初始归并串，依赖于可用内存工作区的大小
- 置换选择算法初始归并串的步骤如下（FI为输入文件，W为可容纳w个记录的内存工作区，FO为输出文件）
- 从FI中读w个记录到W
- 选W中关键字最小的记录，记为X，并加入到FO
- 若FI不空，则取1个记录到W
- 选W中比X大的最小记录，记为X，并加入FO
- 重复前2步
- 如果W中选不出比X大的最小记录，且W不空，则FO中输出一个初始归并串的结束标记
- 从第2步开始继续，直至W为空
- 置换选择算法中的取最小，可以使用败者树，也可以用最小堆
最佳归并树
- 采用置换-选择排序得到的初始归并串，长度不一定相同，因此，平衡归并不一定是最佳的归并顺序，有IO次数更少的归并顺序
- 利用哈夫曼树，叶结点表示初始归并段，权重为归并串长度（记录数），则WPL带权路径长度就是总读记录数，总读写记录数为2WPL
- 前面平衡树的轮数就是层数，WPL就是记录数乘以轮数，就是总读记录数
- 原理上就是希望记录少的初始归并串先归并，记录多的初始归并串后归并
- 哈夫曼树是严格的k叉树，如果初始归并段不足，则可以认为存在长度为0的虚初始段，参与归并
- 计算的方法是利用
，则 ，由此只需要补充叶结点数为k-1的整数倍加1即可
