数据结构：思想与方法-翁惠玉-27783第十章幻灯片.ppt

* template class T void mergeSort(T a[], int left, int right) { int mid = (left+right)/2; if (left == right) return; mergeSort(a, left, mid); mergeSort(a, mid+1, right); merge(a,left,mid+1,right); } * 归并排序的包裹函数 为了使归并排序的函数原型和其他排序算法保持一致，我们再给它加了一个包裹函数。包裹函数调用递归的归并排序函数实现排序。 template class T void mergeSort(T a[], int size) { mergeSort(a, 0, size-1); } * 归并排序的分析 设N是2的幂，则 T(1) = 1 T(N) = 2T(N/2) + N 两边除N，得 * 把所有的式子相加，得： 则： T(N) = NlogN + N = O(NlogN) 所以，归并排序的时间复杂性是O(NlogN)。但从空间上看，它需要额外的空间 * 第10章 排序 引言 插入排序 选择排序 交换排序 归并排序 外排序 * 外排序 外排序模型 预处理 归并 大多数内排序算法都是利用了内存是直接访问的事实,读写一个数据是常量的时间。如果输入是在磁带上，磁带上的元素只能顺序访问。甚至数据是在磁盘上，效率还是下降，因为转动磁盘和移动磁头会产生延迟。 * 外排序模型 外排序具有设备依赖性。这里考虑的算法工作在磁带上 完成有效的排序至少需要两个磁带机 三个磁带机可以简化问题 * 外排序的基本方法 由于一次外存操作所需的时间可以执行数百条甚至上千条指令，因此在外排序中我们主要考虑的是如何减少外存储器的读写 在外存上进行排序的最常用的方法是利用归并排序，因为归并排序只需要访问被归并序列中的第一个元素，这非常适合于顺序文件。 外排序由两个阶段组成： 预处理阶段：根据内存的大小将一个有n个记录的文件分批读入内存，用各种内排序算法排序，形成一个个有序片段。 归并阶段：将这些有序片段逐步归并成一个有序文件。 * 外排序 外排序模型 预处理 归并 大多数内排序算法都是利用了内存是直接访问的事实,读写一个数据是常量的时间。如果输入是在磁带上，磁带上的元素只能顺序访问。甚至数据是在磁盘上，效率还是下降，因为转动磁盘和移动磁头会产生延迟。 * 预处理阶段 最简单的方法是按照内存的容量尽可能多地读入数据记录，然后在内存进行排序，排序的结果写入文件，形成一个已排序片段。 每次读入的记录数越小，形成的初始的已排序片段越多。而已排序片段越多，归并的次数也越多。 如果能够让每个初始的已排序片段包含更多的记录，就能减少排序时间。置换选择可以让我们在只能容纳p个记录的内存中生成平均长度为2p的初始的已排序片段。 * 置换选择 如何更有效地构造已排序片段 事实上，只要第一个元素被写到输出磁带上，它所用的内存空间就可以给别的元素使用。如果输入磁带上的下一个元素比刚刚输出的元素大，它能被放入这个已排序片段。 * 置换选择过程 初始时，将M个元素读入内存，用一个buildHeap有效地放入一个优先级队列。 执行一次deQueue，把最小的元素写入输出磁带。 从输入磁带读入下一个元素。 如果它比刚才写出去的元素大，则把它加入到优先级队列； 否则，它不可能进入当前的已排序片段。因为优先级队列比以前少了一个元素，该元素就被放于优先级队列的空余位置， 继续这个过程，直到优先级队列的大小为0，此时该已排序片段结束。我们通过一个buildHeap操作重新构建一个优先级队列，开始了一个新的已排序片段，此时用了所有存放在空余位置中的元素。 * 已排序片段构建实例：文件上的数据为1、4、10、2、0、5、7、6、3、9、12，内存中能够容纳3个记录 a[0] a[1] a[2] 输出 1 4 10 1 2 4 10 2 4 10 0 4 5 10 0 5 7 10 0 7 10 0 6 10 0 6 3 已排序片段结束 0 3 6 0 3 6 9 3 6 9 12 6 9 12 9 12 12 已排序片段结束 * 外排序 外排序模型 预处理 归并 大多数内排序算法都是利用了内存是直接访问的事实,读写一个数据是常量的时间。如果输入是在磁带上，磁带上的元素只能顺序访问。甚至数据是在磁盘上，效率还是下降，因为转动磁盘和移动磁头会产生延迟。 * 归并 两路归并 多路归并 多阶段归并 * 两路归并 假设我们有四条磁带A1,A2,B1和B2，两个用于输入，两个用于输出。开始时数据在A1上 内存一次能排序M个记录 工作过