摘要
针对外排序存在的困难,给出了一种高效的外排序方法.利用分段的思想将内、外排序算法结合起来,减少计算过程中读写外存的次数,从而提高速度和效率,算法复杂性为O(nlog_2n),通常数百万的排序数据仅需读写磁盘二三遍便可完成排序,大大地减少读写磁盘遍数.本算法既适合内排序,也适合外排序.
To counter problems presented in the external sort,this paper presented an efficient algorithm for external sort.By combining internal sort with external sort based on 'segment', and reducing reading/writing in the calculating,it raised the efficiency and the speed,and was suitable for both internal and external sorts.The complexity of the algorithm is O (nlog_2 n). Generally,the sorting of several million of data can be finished with only 2 or 3 times of reading/writing operating to the disk.
关键词
内排序
外排序
快速排序
复杂性
internal sort
external sort
quick sort
complexity