能看各种网站的浏览器,做网站方案,烟台工程建设信息网站,网站建设策划方案书一.内排总结
在之前博客里#xff0c;博主已经介绍了各种内部排序算法的原理和C语言代码实现#xff0c;不懂的朋友可以在同系列专栏里选择查看#xff0c;今天介绍常见排序算法的最后一点#xff0c;也就是外部排序。在此之前#xff0c;我们先对外部排序的各种算法做一…一.内排总结
在之前博客里博主已经介绍了各种内部排序算法的原理和C语言代码实现不懂的朋友可以在同系列专栏里选择查看今天介绍常见排序算法的最后一点也就是外部排序。在此之前我们先对外部排序的各种算法做一下简单的总结。
算法种类时间复杂度最好时间复杂度最坏时间复杂度平均空间复杂度稳定性折半插入排序O(n)O(n2 )O(n2 )O(1)是直接插入排序O(n)O(n2 )O(n2 )O(1)是希尔排序------------O(1)否冒泡排序O(n)O(n2 )O(n2 )O(1)是快速排序O(nlog2 n)O(n2 )O(nlog2 n)O(log2 n)否简单选择排序O(n2 )O(n2 )O(n2 )O(1)否堆排序O(nlog2 n)O(nlog2 n)O(nlog2 n)O(1)否2路归并排序O(nlog2 n)O(nlog2 n)O(nlog2 n)O(n)是基数排序O(d(nr))O(d(nr))O(d(nr))O®是
针对每种排序算法的效率差别我已经总结在上面的表格里了同时我后面还写了一份针对408范围内的所有数据结果和算法的效率分析专项总结大家可以期待一首。
二.外部排序
1.外排概念 前面介绍过的排序方法都是在内存中进行的(称为内部排序)。而在许多应用中经常需要对大文件进行排序因为文件中的记录很多无法将整个文件复制进内存中进行排序。因此需要将待排序的记录存储在外存上排序时再把数据一部分一部分地调入内存进行排序在排序过程中需要多次进行内存和外存之间的交换。这种排序方法就称为外部排序。 2.排序方法 文件通常是按块存储在磁盘上的操作系统也是按块对磁盘上的信息进行读写的。因为磁盘读/写的机械动作所需的时间远远超过内存运算的时间(相比而言可以忽略不计)因此在外部排序过程中的时间代价主要考虑访问磁盘的次数即I/O次数。 外部排序通常采用归并排序法。它包括两个阶段:①根据内存缓冲区大小将外存上的文件分成若干长度为l的子文件依次读入内存并利用内部排序方法对它们进行排序并将排序后得到的有序子文件重新写回外存称这些有序子文件为归并段或顺串;②对这些归并段进行逐趟归并使归并段(有序子文件)逐渐由小到大直至得到整个有序文件为止。
3.举例说明 用上面这个例子来说明我们假设左边是外存中的待排序序列右边是我们的内存。这里我们只是举例实际上用到外部排序时外存数据量非常庞大这里只是演示。这里涉及一部分操作系统的知识点但都是计算机专业应该都学过内存的数据修改完之后是要写回外存的所以我们这里有两个输入缓冲区和一个输出缓冲区输入缓冲区用来读入磁盘数据输出缓冲区用于把数据写回磁盘。
由于我们的外部排序是基于归并排序算法的归并排序算法要求初始序列有序所以这里我们在开始外部排序之前或者说正式排序之前也就是叫预排序我们需要构造初始有序序列。我们首先从磁盘读取两个块数据进入内存然后在内存中对这两个块的数据进行某一种内部排序。 针对本例的前两个数据块当排序结果写满一个输出缓冲区时我们把输出缓冲区的数据写回外存。以此类推预排序就是把外存的数据每两个块读入内存后排序排序后写回结果。这里的几个块一读是基于内存中输入缓冲区的个数有关它的选取和外部以及内部空间的大小有关。
预排序后的结果应该是这样的 接下来我们的外存中就存在初始有序序列了所以可以开始进行正常的归并排序了。这里注意预排序是两个数据块一读所以两个数据块就形成了一个初始子序列哦这里只有8个初始子序列哦。接下来把子序列1和子序列2的第一块分别读入输入缓冲区开始内部排序还是一样输出缓冲区已满我们就写回外存。这里还有一点注意哦当某个时刻比如输入缓冲区1的数据完了我们不是把输入缓冲区2的数据直接填到输出缓冲区而是把原来子序列后面的数据块读入内存哦假设我们这里使用的内部排序算法也是归并排序这样两个子序列是不是又合并成了一个大的子序列。然后两个大的子序列又可以合并成一个更大的序列直到最后只有一个序列表示我们外部排序完成。
4.效率分析
我们应该知道这里影响时间效率的最大因素其实是I/O口的读取次数内部排序的时间相较于I/O口的读取的读取时间是很少的。所以如果我们想要提高外部排序的时间效率那么就得想办法减少I/O口的读取次数。 一般地 对r个初始归并段做k路平衡归并归并树可用严格k叉树(即只有度为k与度为0的结点的k叉树)来表示。第一趟可将r个初始归并段归并为 ⌈ r / k ⌉ \lceil{r/k}\rceil ⌈r/k⌉ 个归并段以后每趟归并将m个归并段归并成 ⌈ m / k ⌉ \lceil{m/k}\rceil ⌈m/k⌉个归并段,直至最后形成一个大的归并段为止。树的高度-1 「logr1归并趟数S。可见只要增大归并路数k,或减少初始归并段 个数r都能减少归并趟数s,进而减少读写磁盘的次数达到提高外部排序速度的目的。 三.败者树
上节讨论过增加归并路数k能减少归并趟数s进而减少I/O次数。然而增加归并路数k时内部归并的时间将增加。做内部归并时在k个元素中选择关键字最小的记录需要比较k-1次。每趟归并n个元素需要做(n-1)(k-1)次比较s趟归并总共需要的比较次数随k增长而增长。因此内部归并时间亦随k的增长而增长。这将抵消由于增大k而减少外存访问次数所得到的效益。因此不能使用普通的内部归并排序算法。为了使内部归并不受k的增大的影响引入了败者树。 败者树是树形选择排序的一种变体可视为一棵完全二叉树。k个叶结点分别存放k个归并段在归并过程中当前参加比较的记录内部结点用来记忆左右子树中的“失败者”而让胜者往上继续进行比较一直到根结点。若比较两个数大的为失败者、小的为胜利者则根结点指向的数为最小数。
这是实现一个5路归并的败者树的例子。
可见使用败者树后内部归并的比较次数与k无关了。因此只要内存空间允许增大归并路数k将有效地减少归并树的高度从而减少I/O次数提高外部排序的速度。值得说明的是归并路数k并不是越大越好。归并路数k增大时相应地需要增加输入缓冲区的个数。若可供使用的内存空间不变势必要减少每个输入缓冲区的容量使得内存、外存交换数据的次数增大。当k值过大时虽然归并趟数会减少但读写外存的次数仍会增加。
四.置换-选择排序(生成初始序列)
减少初始归并段个数r也可以减少归并趟数S。若总的记录个数为n,每个归并段的长度为l,则归并段的个数r「nll 1。采用内部排序方法得到的各个初始归并段长度都相同(除最后一段外)它依赖于内部排序时可用内存工作区的大小。因此必须探索新的方法用来产生更长的初始归并段这就是本节要介绍的置换-选择算法。
设初始待排文件为FI,初始归并段输出文件为FO内存工作区为WA, FO和WA的初始状态为空WA可容纳w个记录。置换选择算法的步骤如下:
1)从FI输入w个记录到工作区WA。2)从WA中选出其中关键字取最小值的记录记为MINIMAX记录。3)将MINIMAX记录输出到FO中去。4)若FI不空则从FI输入下一个记录到WA中。5)从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录作为新的MINIMAX记录。6)重复3) ~5)直至在WA中选不出新的MINIMAX记录为止由此得到一个初始归并段输出一个归并段的结束标志到FO中去。7)重复2)~6)直至WA为空。由此得到全部初始归并段。
五.最佳归并树
文件经过置换-选择排序后得到的是长度不等的初始归并段。下 面讨论如何组织长度不等的初始归并段的归并顺序,使得I/O次数最少?假设由置换选择得到9个初始归并段,其长度(记录数)依次为9, 30, 12, 18,3, 17,2,6,24。现做3路平衡归并其归并树如图8.16所示。在图左中各叶结点表示一个初始归并段上面的权值表示该归并段的长度叶结点到根的路径长度表示其参加归并的趟数各非叶结点代表归并成的新归并段根结点表示最终生成的归并段。树的带权路径长度WPL为归并过程中的总读记录数故I/O次数 2xWPL 484。
显然归并方案不同所得归并树亦不同树的带权路径长度(I/O次数)亦不同。为了优化归并树的WPL可以将哈夫曼树的思想推广到m叉树的情形在归并树中让记录数少的初始归并段最先归并记录数多的初始归并段最晚归并就可以建立总的I/O次数最少的最佳归并树。上述9个初始归并段可构造成一棵如图右所示的归并树按此树进行归并仅需对外存进行446次读/写这棵归并树便称为最佳归并树。 六.总结
好了到这里408范围内的数据结构和算法部分我们已经学完了接下来转战计算机网络和操作系统部分。
