东阳的学习记录
注意图中颜色的对应
亮黄色框住的代表特殊情况下的时间复杂度，需要特别记忆。屎黄色框住的代表该排序算法不稳定。绿色框住的代表该排序算法的每一趟排序，都确定一个元素的最终位置。考虑因素：元素数目、元素大小、关键字结构及分布、稳定性、存储结构、辅助空间等；
当n较小时(n<=50)，可采用直接插入排序或者简单选择排序；若n较大，则采用快排、堆排序或归并排序； 其中快排适合初始序列无序的情况，若初始序列基本有序，或者需要O(1)的空间复杂度，则不应选择快排；堆排和快排都是不稳定的归并排序是稳定的 若n很大，记录关键字位数较少且可分解，采用基数排序；当文件的n个关键字随即分布时，任何基于比较的排序算法，至少需要 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)的时间；若初始序列基本有序，则采用直接插入排序和冒泡排序（ O ( n ) O(n) O(n)）；当记录元素比较大时，应避免大量移动的排序算法，采用链式存储。外部排序通常采用归并排序方法。
首先，根据内存大小，将外村文件划分为若干等分，依次读入内存，并使用内部排序算法对该子序列进行排序，再将排好序的子序列写回外存中。这些子序列被称为归并段；对归并段进行归并排序过程；这里不是直接将整个归并段全部输入到内存中，(有点类似队列)，将内存分为输出缓冲区1，2和输出缓存区，对于归并段1358和归并段2467，每次只将每个归并段的前两位放入内存的输入缓冲区中，依次比较，当其中一个输入缓冲区为空时，再将对应的归并段的剩余部分放入（可以用队列实现吧）。外部排序的总时间 = 内部排序需要的时间 + 外存读写时间 + 内部归并时间 其中外存读写时间远大于另外两个。
归并趟数 = [ l o g m r ] [log_mr] [logmr] 易知：增加对应归并的路数就会减少磁盘io次数
树形选择排序的一种变体，可视为一棵完全二叉树。每个结点存放归并段再归并过程中当前参加比较的记录，背部结点用来记忆左右子树中的失败者，胜利者继续向上比较。
S趟归并总共需要的次数 S ( n − 1 ) ( m − 1 ) = l o g m r ( n − 1 ) ( m − 1 ) S(n-1)(m-1) = log_mr(n-1)(m-1) S(n−1)(m−1)=logmr(n−1)(m−1)
使用失败树后： S ( n − 1 ) ( m − 1 ) = l o g m r ( n − 1 ) l o g 2 m = l o g 2 r ( n − 1 ) S(n-1)(m-1) = log_mr(n-1)log_2m = log_2r(n-1) S(n−1)(m−1)=logmr(n−1)log2m=log2r(n−1)
使用失败树可以避免内部归并时间的增加，但仍受到缓冲区大小的限制，路数过多同样会增加外存读写时间。
通过置换-选择算法，可以得到长度不等的归并段
设初始待排序文件为FI，初始归并段文件为FO，内存工作区为WA，内存工作区可容纳w个记录。
算法思想：
从待排序文件FI输入w个记录到工作区WA；从WA中选取关键字最小的记录（比此时的MINIMAX大的最小值）保证有序，赋值给MINIMAX；若找不到这样的MINIMAX，则输出一个结束标志到FO中；将MINIMAX输出到FO中；若FI不为空，返回第一步；带权路径长度最小的树(哈夫曼树) 设由置换-选择排序得到9个初始归并段，分别1，2，3，4，5，6，7，8，9 据此构建哈夫曼树，这样的哈夫曼树即为最佳归并树
