基本介紹
- 中文名：盤排序
- 外文名：Plate of sorting
- 定義：數據處理
外排序算法,數據結構,分段算法,外排序算法DSORT,算法優點,
外排序算法
本算法主要由兩個子算法組成:快速排序法和分段算法.
數據結構
ST:存放檔案名稱的字串數組.
A:存放排序數據的記錄型數組.
S:元素指向A中某元素，該元素是某段目前最後一個元素的數組。
分段算法
算法功能:給定段的右端點x，把數組A從L到r的元素分為兩段，設分割點為ko，使從l 到k0的元素的排序碼小於等於x的排序碼，而k0十1到r的元素的排序碼大於x的排序碼。
外排序算法DSORT
S1.數據檔案名進棧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段的任一數據小於或等於第2段中任一數據，第2段中任一數據小於或等於第3段中任一數據，如此等等，但不保證任一段中所有數據是有序的，這樣，本算法在分段階段比經典的外排序法大大地減少了數據的比較和移動次數。
(2)經典的外排序的第二階段是對這些已作排序的段進行歸併(成順串)，每歸併一趟，就要讀寫所有記錄一次;而本算法並沒有“歸併”階段，它對任一段進行處理時，如果該段在記憶體中能容納下時，就悉用快速內排序，反之，就採用分段，所以它總是局限於某一段(不妨將原待排序檔案也看成一段)而與另外的段無關，也就是說，它處理某一段時，用不著讀寫其他段的記錄，所以它讀寫磁碟的次數比經典的外排序方法大為減少，這正是本算法高速度高效率的主要原因。
(3)本算法既適用於外排序也適用於內排序。
(4)本算法的核心算法是分段算法，而分段算法是快速排序的一部分，所以本算法把“分段”和“內排序”有機地結合起來，這種有機的結合使得利用本算法編製程序比起利用經典的外排序算法編製程序來得容易。
