外排序法的研究

• 作 者: 陶明华
• 机 构: 江苏省镇江师范专科学校计算机中心镇江 2l2003
• 出 处: 微计算机应用
• 发表日期: 2000年2期
• 关键词: 子文件 外排序 数据分配 排序过程 内排序 排序结果 写操作 排序法 内存 关键字 队列 时间复杂性 最终结果 算法效率 思想 排序方法 归并排序 磁盘 最小值

本算法的基本思想是将“桶”排序的思想运用到外排序上来.rn”桶”排序法:先把N个被排记录按关键字的不同值分配到radix(队列数)个队列中,每个队列称为一个“桶”;接着对每个”桶”内的数据进行排序;最后再将所有“桶”内数据按次序接在一起即完成整个排序.rn”桶”外排序法:把“桶”排序中分配到各个”桶”的过程改为分配到对应子文件;先按关键字的值把N个记录分配到radix个子文件中;接着再依次把各个子文件中的数据读入内存进行内排序,把排序结果写到最终结果文件中FOUT.例如:对N=10个数据(49,38,65,97,76,13,27,97,58,90)的外排序过程如下:rn(1)从被排数据中求得最大值Dmax=97、最小值Dmin=13,假设"桶”数radix=3.rn(2)求数据Di应写入的子文件号.子文件号=[(Di-Dmin)×(radix-1)/(Dmax-Dmin)]+1,i=1～N,分配结束后,每个子文件中的数据分配情况如下:rn子文件1中为49,38,13,27;子文件2中为65,76,58,90;子文件3中为97,97.至此,子文件1中的所有数据小于子文件2、子文件3中的所有数据;子文件2中所有数据又小于子文件3中的所有数据.rn(3)依次将子文件1、子文件2、子文件3读入内存进行内排序,再依次将排序结果写入排序文件FOUT中.FOUT中最终为以递增顺序排好序的数据.rn外排序算法效率主要取决于排序过程中对外存的读/写次数,整个排序过程仅对外存设备进行了二次读/写操作即完成了外排序.此方法的时间复杂性可近似认为(忽略内排序时间)是对N个数据共计进行2×N次读/写操作的时间,也即O(N).rn另外,采用此外排序方法,既可解决在外排序时所需读/写外存的次数和归并的趟数之间如何进行正确选择的矛盾,又可省去在最佳归并树的归并方案进行磁盘归并排序,需在内存建立一张载有归并段的长度和它在磁盘上的物理位置的索引表的工作.