[科普中国]-盘排序

外排序算法

本算法主要由两个子算法组成:快速排序法和分段算法.

数据结构ST:存放文件名的字串数组.

A:存放排序数据的记录型数组.

S:元素指向A中某元素，该元素是某段目前最后一个元素的数组。

分段算法算法功能:给定段的右端点x，把数组A从L到r的元素分为两段，设分割点为ko，使从l 到k0的元素的排序码小于等于x的排序码，而k0十1到r的元素的排序码大于x的排序码。

外排序算法DSORTS1.数据文件名进栈ST，建立目的文件(排序结果文件)SORTF

S2.循环执行S3至S6，直至栈ST空为止

S3.从栈ST中弹出一文件名并赋给F，打开文件F

S4.从文件F中读数据入数组A

S5.若文件F结束，采用快速排序法对A中的数据排序后写到文件SORTF中，删除文件F

S6.如果文件F未结束，对A中从1至m的元素使用快速排序法进行排序，调用算法FQUICSEG ( F, ST)对文件F进行分段，删除文件F。1

算法优点(1)经典的外排序第一阶段按内存大小将外存中待处理文件分为若干子文件(段)，并利用有效的内排序方法对它们排序;而本算法只是“分段”而没有“排序”，即保证第1段的任一数据小于或等于第2段中任一数据，第2段中任一数据小于或等于第3段中任一数据，如此等等，但不保证任一段中所有数据是有序的，这样，本算法在分段阶段比经典的外排序法大大地减少了数据的比较和移动次数。

(2)经典的外排序的第二阶段是对这些已作排序的段进行归并(成顺串)，每归并一趟，就要读写所有记录一次;而本算法并没有“归并”阶段，它对任一段进行处理时，如果该段在内存中能容纳下时，就悉用快速内排序，反之，就采用分段，所以它总是局限于某一段(不妨将原待排序文件也看成一段)而与另外的段无关，也就是说，它处理某一段时，用不着读写其他段的记录，所以它读写磁盘的次数比经典的外排序方法大为减少，这正是本算法高速度高效率的主要原因。

(3)本算法既适用于外排序也适用于内排序。

(4)本算法的核心算法是分段算法，而分段算法是快速排序的一部分，所以本算法把“分段”和“内排序”有机地结合起来，这种有机的结合使得利用本算法编制程序比起利用经典的外排序算法编制程序来得容易。1