数据结构11-内部排序算法的比较和应用以及外部排序

东阳的学习记录

内部排序算法的比较和应用

比较

注意图中颜色的对应

• 亮黄色框住的代表特殊情况下的时间复杂度，需要特别记忆。
• 屎黄色框住的代表该排序算法不稳定。
• 绿色框住的代表该排序算法的每一趟排序，都确定一个元素的最终位置。
  

应用

考虑因素：元素数目、元素大小、关键字结构及分布、稳定性、存储结构、辅助空间等；

1. 当n较小时(n<=50)，可采用直接插入排序或者简单选择排序；若n较大，则采用快排、堆排序或归并排序；
   • 其中快排适合初始序列无序的情况，若初始序列基本有序，或者需要O(1)的空间复杂度，则不应选择快排；
   • 堆排和快排都是不稳定的
   • 归并排序是稳定的
2. 若n很大，记录关键字位数较少且可分解，采用基数排序；
3. 当文件的n个关键字随即分布时，任何基于比较的排序算法，至少需要$O(nlog_2n)$O(nlog2​n)的时间；
4. 若初始序列基本有序，则采用直接插入排序和冒泡排序（$O(n)$O(n)）；
5. 当记录元素比较大时，应避免大量移动的排序算法，采用链式存储。

外部排序算法

外部排序通常采用归并排序方法。

1. 首先，根据内存大小，将外村文件划分为若干等分，依次读入内存，并使用内部排序算法对该子序列进行排序，再将排好序的子序列写回外存中。这些子序列被称为归并段；
2. 对归并段进行归并排序过程；这里不是直接将整个归并段全部输入到内存中，(有点类似队列)，将内存分为输出缓冲区1，2和输出缓存区，对于归并段1358和归并段2467，每次只将每个归并段的前两位放入内存的输入缓冲区中，依次比较，当其中一个输入缓冲区为空时，再将对应的归并段的剩余部分放入（可以用队列实现吧）。
   

外部排序的时间复杂度

外部排序的总时间 = 内部排序需要的时间 + 外存读写时间 + 内部归并时间
其中外存读写时间远大于另外两个。

归并趟数 = $[log_mr]$[logm​r]
易知：增加对应归并的路数就会减少磁盘io次数

失败树

树形选择排序的一种变体，可视为一棵完全二叉树。每个结点存放归并段再归并过程中当前参加比较的记录，背部结点用来记忆左右子树中的失败者，胜利者继续向上比较。

S趟归并总共需要的次数
$S(n-1)(m-1) = log_mr(n-1)(m-1)$S(n−1)(m−1)=logm​r(n−1)(m−1)

使用失败树后：$S(n-1)(m-1) = log_mr(n-1)log_2m = log_2r(n-1)$S(n−1)(m−1)=logm​r(n−1)log2​m=log2​r(n−1)

使用失败树可以避免内部归并时间的增加，但仍受到缓冲区大小的限制，路数过多同样会增加外存读写时间。

置换-选择排序算法

通过置换-选择算法，可以得到长度不等的归并段

设初始待排序文件为FI，初始归并段文件为FO，内存工作区为WA，内存工作区可容纳w个记录。

算法思想：

1. 从待排序文件FI输入w个记录到工作区WA；
2. 从WA中选取关键字最小的记录（比此时的MINIMAX大的最小值）保证有序，赋值给MINIMAX；若找不到这样的MINIMAX，则输出一个结束标志到FO中；
3. 将MINIMAX输出到FO中；
4. 若FI不为空，返回第一步；
   

最佳归并树

带权路径长度最小的树(哈夫曼树)
设由置换-选择排序得到9个初始归并段，分别1，2，3，4，5，6，7，8，9
据此构建哈夫曼树，这样的哈夫曼树即为最佳归并树