在這一節裡，我們說明一種排序的演算法 (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);
}
在 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() 的程式設計， 幾乎完全就是按照演算法的想法來做。 這就是遞迴想法的妙處。
習題
注意：此處所有文件均為原著，個別的版權宣告日後會一一公布， 整體版面設計亦尚未完成。但仍請勿抄襲文字與圖片，以免觸犯著作權法。
Created: May 21, 2000
Last Revised: May 21, 2000
© Copyright 2000 Wei-Chang Shann 單維彰