[科普中國]-盤排序

外排序算法

本算法主要由兩個子算法組成:快速排序法和分段算法.

數(shù)據(jù)結構ST:存放文件名的字串數(shù)組.

A:存放排序數(shù)據(jù)的記錄型數(shù)組.

S:元素指向A中某元素，該元素是某段目前最后一個元素的數(shù)組。

分段算法算法功能:給定段的右端點x，把數(shù)組A從L到r的元素分為兩段，設分割點為ko，使從l 到k0的元素的排序碼小于等于x的排序碼，而k0十1到r的元素的排序碼大于x的排序碼。

外排序算法DSORTS1.數(shù)據(jù)文件名進棧ST，建立目的文件(排序結果文件)SORTF

S2.循環(huán)執(zhí)行S3至S6，直至棧ST空為止

S3.從棧ST中彈出一文件名并賦給F，打開文件F

S4.從文件F中讀數(shù)據(jù)入數(shù)組A

S5.若文件F結束，采用快速排序法對A中的數(shù)據(jù)排序后寫到文件SORTF中，刪除文件F

S6.如果文件F未結束，對A中從1至m的元素使用快速排序法進行排序，調用算法FQUICSEG ( F, ST)對文件F進行分段，刪除文件F。1

算法優(yōu)點(1)經(jīng)典的外排序第一階段按內存大小將外存中待處理文件分為若干子文件(段)，并利用有效的內排序方法對它們排序;而本算法只是“分段”而沒有“排序”，即保證第1段的任一數(shù)據(jù)小于或等于第2段中任一數(shù)據(jù)，第2段中任一數(shù)據(jù)小于或等于第3段中任一數(shù)據(jù)，如此等等，但不保證任一段中所有數(shù)據(jù)是有序的，這樣，本算法在分段階段比經(jīng)典的外排序法大大地減少了數(shù)據(jù)的比較和移動次數(shù)。

(2)經(jīng)典的外排序的第二階段是對這些已作排序的段進行歸并(成順串)，每歸并一趟，就要讀寫所有記錄一次;而本算法并沒有“歸并”階段，它對任一段進行處理時，如果該段在內存中能容納下時，就悉用快速內排序，反之，就采用分段，所以它總是局限于某一段(不妨將原待排序文件也看成一段)而與另外的段無關，也就是說，它處理某一段時，用不著讀寫其他段的記錄，所以它讀寫磁盤的次數(shù)比經(jīng)典的外排序方法大為減少，這正是本算法高速度高效率的主要原因。

(3)本算法既適用于外排序也適用于內排序。

(4)本算法的核心算法是分段算法，而分段算法是快速排序的一部分，所以本算法把“分段”和“內排序”有機地結合起來，這種有機的結合使得利用本算法編制程序比起利用經(jīng)典的外排序算法編制程序來得容易。1