排序

在這一節裡,我們說明一種排序的演算法 (algorithm), 並利用遞迴來設計它。

所謂排序,簡化來說,就是將一個數列,按照 <= 的順序排好。 這裡介紹 Hoare 在 1962 年提出的演算法。 他的基本想法就是二分法:在數列中任挑一個數,比如說正好位於數列中央的數, 名之為基準。 把數列中比基準小的都放到它的左邊,其他的都放到右邊, 然後拿基準左邊的子數列、和基準右邊的子數列,分別重複上一動。 一直到每個子數列裡面都只有一個數,那就排完了。

舉個例子來說,若原數列是

13 5 9 16 11 7 10
挑 16 來當做基準,就成了
(10 5 9 13 11 7) 16 ( )
這時候,16 的右邊是空數量,不必再做,但 16 的左邊要重複二分法的步驟。 現在,拿 9 當基準,就成了
(7 5 9 13 11 10) 16 ( )
然後,再將 (7 5) 和 (13 11 10) 分別送去重複二分法的步驟, 分別取 7 和 11 當做各自的基準,就成了
((5 7 ( )) 9 (10 11 13)) 16 ( )
其中黑色表示已經排定位的數、紅色代表還需要排序的子數列。 但是,現在每個需要排序的子數列,都只有一個元素,那就根本不必再做。 最後的答案就是
5 7 9 10 11 13 16

以下,我們按照 Hoare 的二分法設計 nsort(),並示範一個測試程式。


#include <stdio.h>
#define SIZE 7
 
main() {
    int v[SIZE], i;
    void nsort(int[], unsigned int, unsigned int);
 
    v[0]=13,v[1]=5,v[2]=9,v[3]=16,v[4]=11,v[5]=7,v[6]=10;
    for (i=0; i<SIZE; ++i)
        printf("%d ", v[i]);
    putchar('\n');
    nsort(v, 0, SIZE-1);
    for (i=0; i<SIZE; ++i)
        printf("%d ", v[i]);
    putchar('\n');
}
 
void nsort(int v[], unsigned int a, unsigned int b) {
    int t, p, i;
 
    if (a >= b)
        return;
    t=v[a], v[a]=v[(a+b)/2], v[(a+b)/2]=t;
    p = a;
    for (i=a+1; i <= b; ++i)
        if (v[i] < v[a])
            t=v[++p], v[p]=v[i], v[i]=t;
    t=v[p], v[p]=v[a], v[a]=t;
    nsort(v, a, p-1);
    nsort(v, p+1, b);
}

main() 的部分沒什麼值得解釋的。 注意,我們將 nsort() 的宣告寫到了 main() 的裡面。 這是 C 所容許的語法。

nsort() 裡面,它得到一個序列 v[], 和一個子序列的左端點 a 和右端點 b,含這兩個端點。 如果 a >= b 表示這個子序列只有一個元素,或根本是空的, 就不必再做任何事。指令

        return;
表示結束這個函式,但並沒有返回任何值給原函式。 在程式裡,看到 3 次
    t=...
這種指令。讀者應該瞭解,它們就是交換的意思。例如
            t=v[++p], v[p]=v[i], v[i]=t;
就是將 v[++p] 的值和 v[i] 的值交換。 最後,就是要瞭解一個技巧。 我們先將中央數 v[(a+b)/2] 與左端點 v[a] 交換位置。 此後左端點就是基準數。 然後用一個指標 p 來記錄最後一個小於基準數的足標。 等二分法結束了,再將左端點與 v[p] 交換, 於是所有小於基準數的數,都到了 v[p] 的左邊 (< p), 反之則在右邊 (> p)。 最後,就分別將左邊的子序列、和右邊的子序列,分別送去 nsort 再做二分法。

經過這些解釋,讀者應該可以瞭解,nsort() 的程式設計, 幾乎完全就是按照演算法的想法來做。 這就是遞迴想法的妙處。

習題

  1. 寫一個程式,命名為 sort-n.c,它從 stdin 讀入純文字檔案, 假設每列有一個整數,輸出這些數的排序。 也就是說,sort-n.c 的功能,就跟 UNIX 指令 sort -n < file 一樣。

[ 前一節 ]‧[ 後一節 ]‧[ 回目錄 ]



注意:此處所有文件均為原著,個別的版權宣告日後會一一公布, 整體版面設計亦尚未完成。但仍請勿抄襲文字與圖片,以免觸犯著作權法。

Created: May 21, 2000
Last Revised: May 21, 2000
© Copyright 2000 Wei-Chang Shann 單維彰

shann@math.ncu.edu.tw