1、老掉牙河內塔費式數列巴斯卡三角形三色棋老鼠走迷官（一）老鼠走迷官（二）騎士走棋盤八個皇后八枚銀幣生命游戲字串核對雙色、三色河內塔背包問題（Knapsack Problem ）數、運算蒙地卡羅法求PIEratosthenes篩選求質數超長整數運算（大數運算）長PI最大公因數、最小公倍數、因式分解完美數阿姆斯壯數最大訪客數中序式轉后序式（前序式）后序式的運算關于賭博洗撲克牌（亂數排列）Craps賭博游戲約瑟夫問題（Josephus Problem ）集合問題排列組合格雷碼（Gray Code ）產生可能的集合m元素集合的n個元素子集數字拆解排序得分排行選擇、插入、氣泡排序Shell排序法-改良的插

2、入排序 Shaker排序法-改良的氣泡排序 Heap排序法-改良的選擇排序 快速排序法（一） 快速排序法（二） 快速排序法（三） 合并排序法 基數排序法搜尋循序搜尋法（使用衛兵）二分搜尋法（搜尋原則的代表） 插補搜尋法費氏搜尋法矩陣稀疏矩陣多維矩陣轉一維矩陣上三角、下三角、對稱矩陣 奇數魔方陣4N魔方陣2（2N+1）魔方陣1.河內之塔說明河內之塔（Towers of Hanoi） 是法國人（Lucas）于1883年從泰國帶至法國的，河內為越戰時北越的首都，即現在的胡志明市；1883年法國數學家Edouard Lucas 曾提及這個故事，據說創世紀時Benares有一座波羅教塔，是由三支鉆石棒(

3、 Pag)所支撐，開始時神在第一根棒上放 置64個由上至下依由小至大排列的金盤( Disc ) ， 并命令僧侶將所有的金盤從第一根石棒移至第三根石棒，且搬運過程中遵守大盤子在小盤子之下的原則，若每日僅搬一個盤子，則當盤子全數搬運完畢之時，此塔將毀損，而也就是世界末日來臨之時。角軍法如果柱子標為ABC要由A搬至C,在只有一個盤子時，就將它直接搬至C,當有兩個盤子，就將B當作輔助柱。如果盤數超過2個，將第三個以下的盤子遮起來，就很簡單了，每次處理兩個盤子，也就是：A-B、A -C、B-C這三個步驟，而被遮住的部份，其實就是進入程式的遞回 處理。事實上，若有n個盤子，則移動完畢所需之次數為 2An

4、- 1 ,所以當盤數為64時，則所需 次數為：264- 1 = 9551615 為+16年，也就是約5000世紀，如果對這數字沒什幺概念，就假設每秒鐘搬一個盤子好了，也要約5850億年左右。#include void hanoi(int n, char A, char B, char C) if(n = 1) printf(Move sheet %d from %c to %cn, n, A, C);else hanoi(n-1, A, C, B);printf(Move sheet %d from %c to %cn, n, A, C);hanoi(n-1, B, A, C); int ma

5、in() int n;printf( 請輸入盤數： );scanf(%d, &n);hanoi(n, A, B, C);return 0;Algorithm Gossip: 費式數列說明Fibonacci 為 1200年代的歐洲數學家，在他的著作中曾經提到： 若有一只免子每個月生一只小免子，一個月后小免子也開始生產。起初只有一只免子，一個月后就有兩只免子，二個月后有三只免子，三個月后有五只免子（小免子投入生產） 。如果不太理解這個例子的話，舉個圖就知道了，注意新生的小免子需一個月成長期才會投入生產，類似的道理也可以用于植物的生長，這就是Fibonacci 數列，一般習慣稱之為費氏數列，例如以下

6、： 1 、 1 、 2、 3、 5、 8、 13、 21、 34、 55、 89解法依說明，我們可以將費氏數列定義為以下：fn = fn-1 + fn-2if n 1fn = nif n = 0, 1 #include #include #define N 20int main(void) int FibN = 0;int i;Fib0 = 0;Fib1 = 1;for(i = 2; i N; i+) Fibi = Fibi-1 + Fibi-2;for(i = 0; i N; i+) printf(%d , Fibi); printf(n);return 0;巴斯卡三角形#include #

7、define N 12long combi(int n, int r)int i;long p = 1;for(i = 1; i = r; i+)p = p * (n-i+1) / i;return p;void main()int n, r, t;for(n = 0; n = N; n+) for(r = 0; r = n; r+) int i;/*排版設定開始*/if(r = 0) for(i = 0; i = (N-n); i+) printf( );else printf( ); /*排版設定結束*/printf(%3d, combi(n, r);printf(n);Algorithm

8、 Gossip: 三色棋說明三色旗的問題最早由所提出，他所使用的用語為 Dutch Nation Flag（Dijkstra 為荷蘭人 ） ，而多數的作者則使用 Three-Color Flag 來稱之。假設有一條繩子，上面有紅、白、藍三種顏色的旗子，起初繩子上的旗子顏色并沒有順序，您希望將之分類，并排列為藍、白、紅的順序，要如何移動次數才會最少，注意您只能在繩子上進行這個動作，而且一次只能調換兩個旗子。解法在一條繩子上移動，在程式中也就意味只能使用一個陣列，而不使用其它的陣列來作輔助，問題的解法很簡單，您可以自己想像一下在移動旗子，從繩子開頭進行，遇到藍色往前移，遇到白色留在中間，遇到紅色往

9、后移，如下所示：只是要讓移動次數最少的話，就要有些技巧：如果圖中W昕在的位置為白色，則 W+1,表示未處理的部份移至至白色群組。如果WFB份為藍色，則B與W勺元素對調，而B與W、須各+1,表示兩個群組都多了一個元素。如果W所在的位置是紅色，則將W亍R交換，但R要減1,表示未處理的部份減1。注意 W 所不是三色旗的個數，它們只是一個移動的指標；什幺時候移動結束呢？ 一開始時未處理的R旨標會是等于旗子的總數，當R的索引數減至少于W勺索引數時，表示接下來的旗子就 都是紅色了，此時就可以結束移動，如下所示：#include #include #include #define BLUE b#define

10、 WHITE w#define RED rcolory = temp; int main() char color = r, w, b, w, w,b, r, b, w, r, 0;int wFlag = 0;int bFlag = 0;int rFlag = strlen(color) - 1;int i;for(i = 0; i strlen(color); i+)printf(%c , colori);printf(n);while(wFlag = rFlag) if(colorwFlag = WHITE)wFlag+;else if(colorwFlag = BLUE) SWAP(bF

11、lag, wFlag);bFlag+; wFlag+;else while(wFlag rFlag & colorrFlag = RED) rFlag-;SWAP(rFlag, wFlag);rFlag-;for(i = 0; i strlen(color); i+) printf(%c , colori);printf(n);return 0;Algorithm Gossip:老鼠走迷官(一)說明老鼠走迷宮是遞回求解的基本題型，我們在二維陣列中使用2表示迷宮墻壁，使用1來表示老鼠的行走路徑，試以程式求出由入口至出口的路徑。解法老鼠的走法有上、左、下、右四個方向，在每前進一格之后就選一個方向前

12、進，無法前進時退回選擇下一個可前進方向，如此在陣列中依序測試四個方向，直到走到出口為止，這是遞回的基本題，請直接看程式應就可以理解。#include #include int visit(int, int);int maze77 = 2, 2, 2, 2, 2, 2, 2,2, 0, 0, 0, 0, 0, 2,2, 0, 2, 0, 2, 0, 2,2, 0, 0, 2, 0, 2, 2,2, 2, 0, 2, 0, 2, 2,2, 0, 0, 0, 0, 0, 2,2, 2, 2, 2, 2, 2, 2;int startI = 1, startJ = 1; Warnsdorff在 182

13、3年提出，簡單的說，先將最難的位置走完，接下來的路就寬廣了， 騎士所要走的下一步， 為下一步再選擇時， 所能走的步數最少的一步。 ， 使用這個方法，在不使用遞回的情況下，可以有較高的機率找出走法(找不到走法的機會也是 有的) 。#include int board88 = 0;int main(void) int startx, starty;int i, j;printf( 輸入起始點： );scanf(%d %d, &startx, &starty);if(travel(startx, starty) printf( 游歷完成！ n);else printf(游歷失敗！ n);for(i

14、= 0; i 8; i+) for(j = 0; j N) showAnswer();else for(j = 1; j = N; j+) if(columnj = 1 &rupi+j = 1 & lupi-j+N = 1) queeni = j;H.Conwa斯提出，某一細胞的鄰居包括上、下、左、右、左上、左下、右上與右下相鄰之細胞，游戲規則如下：孤單死亡：如果細胞的鄰居小于一個，則該細胞在下一次狀態將死亡。擁擠死亡：如果細胞的鄰居在四個以上，則該細胞在下一次狀態將死亡。穩定：如果細胞的鄰居為二個或三個，則下一次狀態為穩定存活。復活：如果某位置原無細胞存活，而該位置的鄰居為三個，則該位置將復

15、活一細胞。確軍法生命游戲的規則可簡化為以下，并使用CAS正匕對即可使用程式實作：鄰居個數為 0、 1、 4 、 5 、 6、 7、 8 時，則該細胞下次狀態為死亡。鄰居個數為2時，則該細胞下次狀態為復活。鄰居個數為3時，則該細胞下次狀態為穩定。#include #include #include #define MAXROW 10#define MAXCOL 25#define DEAD 0#define ALIVE 1int mapMAXROWMAXCOL, newmapMAXROWMAXCOL;void init();int neighbors(int, int);void outputM

16、ap();void copyMap();int main() int row, col;char ans;init();while(1) outputMap();for(row = 0; row MAXROW; row+) for(col = 0; col MAXCOL; col+) switch (neighbors(row, col) case 0:newmaprowcol = DEAD;break;newmaprowcol = maprowcol;break;newmaprowcol = ALIVE;break;copyMap();printf(nContinue next Genera

17、tion ? );getchar();ans = toupper(getchar();if(ans != Y)break;return 0;void init() int row, col;for(row = 0; row MAXROW; row+)for(col = 0; col MAXCOL; col+) maprowcol = DEAD;puts(Game of life Program);puts(Enter x, y where x, y is living cell);printf(0 = x = %d, 0 = y = %dn, MAXROW-1, MAXCOL-1);puts(

18、Terminate with x, y = -1, -1);while(1) scanf(%d %d, &row, &col);if(0 = row & row MAXROW &0 = col & col MAXCOL) maprowcol = ALIVE;else if(row = -1 | col = -1) break;elseprintf(x, y) exceeds map ranage!);int neighbors(int row, int col) int count = 0, c, r;for(r = row-1; r = row+1; r+)for(c = col-1; c

19、= col+1; c+) if(r = MAXROW | c = MAXCOL) continue;if(maprc = ALIVE) count+;if(maprowcol = ALIVE)count-;return count;void outputMap() int row, col;printf(nn%20cGame of life cell statusn);for(row = 0; row MAXROW; row+) printf(n%20c, );for(col = 0; col MAXCOL; col+)if(maprowcol = ALIVE)putchar(#);elsep

20、utchar(-);void copyMap() int row, col;for(row = 0; row MAXROW; row+)for(col = 0; col MAXCOL; col+)maprowcol = newmaprowcol;Algorithm Gossip:字串核對說明 今日的一些高階程式語言對于字串的處理支援越來越強大（例如Java、Perl等），不過字串搜尋本身仍是個值得探討的課題，在這邊以Boyer- Moore法來說明如何進行字串說明，這個方法快且原理簡潔易懂。解法字串搜尋本身不難，使用暴力法也可以求解，但如何快速搜尋字串就不簡單了，傳統的字串搜尋是從關鍵字與字串

21、的開頭開始比對，例如Knuth-Morris-Pratt 演算法字串搜尋，這個方法也不錯，不過要花時間在公式計算上；Boyer-Moore字串核對改由關鍵字的后面開始核對字串，并制作前進表，如果比對不符合則依前進表中的值前進至下一個核對處，假設是p好了，然后比對字串中p-n+1至p的值是否與關鍵字相同。如果關鍵字中有重復出現的字元，則前進值就會有兩個以上的值，此時則取前進值較小的值，如此就不會跳過可能的位置，例如texture這個關鍵字，t的前進值應該取后面的 3而不是取前面 的7。#include #include #include table(char*);voidhanoihanoiha

22、noihanoihanoihanoihanoihanoihanoihanoihanoihanoihanoihanoihanoiize; s values) ize) printf(%st%dn,, aitemi.price);printf( 合計 t%dn, valueLIMIT);return 0;Javaclass Fruit private String name;private int size;private int price;public Fruit(String name, int size, int price) = name;= size;= pric

23、e;public String getName() return name;public int getPrice() return price;public int getSize() return size;public class Knapsack public static void main(String args) final int MAX = 8;final int MIN = 1;int item = new intMAX+1;int value = new intMAX+1;Fruit fruits = new Fruit(李子 , 4, 4500),new Fruit(蘋

24、果 , 5, 5700),new Fruit(橘子 , 2, 2250),new Fruit(草莓 , 1, 1100),new Fruit(甜瓜 , 6, 6700);for(int i = 0; i ; i+) for(int s = fruitsi.getSize(); s values) etSize() t + fruitsitemi.getPrice(); 合計 t + valueMAX);Algorithm Gossip: 蒙地卡羅法求PI說明 蒙地卡羅為摩洛哥王國之首都，該國位于法國與義大利國境，以賭博聞名。蒙地卡羅的基本原理為以亂數配合面積公式來進行解題，這種以機率來解題的方

25、式帶有賭博的意味，雖然在精確度上有所疑慮，但其解題的思考方向卻是個值得學習的方式。解法 蒙地卡羅的解法適用于與面積有關的題目，例如求PI 值或橢圓面積，這邊介紹如何求PI值； 假設有一個圓半徑為1，所以四分之一圓面積就為PI ，而包括此四分之一圓的正方形面積就為1 ，如下圖所示：如果隨意的在正方形中投射飛標(點)好了，則這些飛標(點)有些會落于四分之一圓內，假設所投射的飛標(點)有n點，在圓內的飛標(點)有 c點，則依比例來算，就會得到上圖中最后的公式。至于如何判斷所產生的點落于圓內，很簡單，令亂數產生X與Y兩個數值，如果*人2+丫人2等于1就是落在圓內。#include #include #

26、include #define N 50000int main(void) int i, sum = 0;double x, y;srand(time(NULL);for(i = 1; i N; i+) x = (double) rand() / RAND_MAX;y = (double) rand() / RAND_MAX;if(x * x + y * y) 1) sum+;printf(PI = %fn, (double) 4 * sum / N);return 0;Algorithm Gossip: Eratosthenes 篩選求質數說明 除了自身之外，無法被其它整數整除的數稱之為質數

27、，要求質數很簡單，但如何快速的求出質數則一直是程式設計人員與數學家努力的課題，在這邊介紹一個著名的 Eratosthenes 求質數方法。解法 首先知道這個問題可以使用回圈來求解，將一個指定的數除以所有小于它的數，若可以整除就不是質數，然而如何減少回圈的檢查次數？如何求出小于N的所有質數？首先假設要檢查的數是N子了，則事實上只要檢查至 N的開根號就可以了，道理很簡單，假設A*B=N,如果A大于N的開根號，則事實上在小于足前的檢查就可以先檢查到B這個數可以整除No不過在程式中使用開根號會精確度的問題，所以可以使用 i*i = N 進行檢查，且執行更快。再來假設有一個篩子存放 1N,例如： TOC

28、 o 1-5 h z 2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 20 21 N先將 2的倍數篩去：2 3 5 7 9 11 13 15 17 19 21 N再將 3的倍數篩去：2 3 5 7 11 13 17 19 N再來將 5的倍數篩去，再來將7的質數篩去，再來將11的倍數篩去 ，如此進行到最后留下的數就都是質數，這就是Eratosthenes 篩選方法( Eratosthenes Sieve Method ) 。檢查的次數還可以再減少，事實上，只要檢查6n+1與6n+5就可以了，也就是直接跳過2與3的倍數，使得程式中的 if 的檢查動作可以減

29、少。實作C#include #include #define N 1000int main(void) int i, j;int primeN+1;for(i = 2; i = N; i+) primei = 1;for(i = 2; i*i = N; i+) -4/239 - 4/(3*2393) + 4/(5*2395) - 4/(7*2397) + 可以將這個公式整理為：PI = 16/5 - 4/239 - 16/(53) - 4/(2393)/3+ 16/(55) - 4/(2395)/5 +也就是說第n項，若為奇數則為正數，為偶數則為負數，而項數表示方式為:16/5 2*n-1 -

30、 4/239 2*n-1 / (2*n-1)如果我們要計算圓周率至10的負L次方，由于16/5 2n-1 - 4/239 2n-1中16/5 2n1比4/239 2n1來的大,具有決定性，所以表示至少必須計算至第 n項:16/5 2*n-1 / (2*n-1) = 10 -L將上面的等式取log 并經過化簡，我們可以求得：n = L / (2log5) = L /所以若要求精確度至小數后L位數，則只要求至公式的第 n項，其中n等于:n = L/ + 1在上式中 為高斯符號，也就是取至整數(不大于 L/ 的整數) ；為了計簡方便，可以在程式中使用下面這個公式來計簡第n項： Wn -1/5 2-

31、Vn-1 / (2392) / (2*n-1)這個公式的演算法配合大數運算函式的演算法為： div(w, 25, w);div(v, 239, v);div(v, 239, v);sub(w, v, q);div(q, 2*k-1, q)至于大數運算的演算法，請參考之前的文章，必須注意的是在輸出時，由于是輸出陣列中的整數值，如果陣列中整數位數不滿四位，則必須補上0,在市言中只要 使用格式指定字04a使得不足位數部份自動補上0再輸出，至于Java的部份，使用NumberFormat來作格式化。#include #define L 1000#define N L/4+1, s0);for(k =

32、1; k = 0; i-) ci = ai + bi + carry;if(ci 10000)carry = 0;else .,這只要使用除法與余數運算就可以了，例如輸入input為abc,則：a = input / 100b = (input%100) / 10c = input % 10#include #include #include int main(void) int a, b, c;int input;printf( 尋找 Armstrong 數： n);for(input = 100; input = 999; input+) a = input / 100;b = (inpu

33、t % 100) / 10;c = input % 10;if(a*a*a + b*b*b + c*c*c = input) printf(%d , input);printf(n);return 0;Algorithm Gossip: 最大訪客數說明現將舉行一個餐會， 讓訪客事先填寫到達時間與離開時間， 為了掌握座位的數目，必須先估計不同時間的最大訪客數。解法這個題目看似有些復雜， 其實相當簡單，單就計算訪客數這個目的， 同時考慮同一訪客的來訪時間與離開時間，反而會使程式變得復雜；只要將來訪時間與離開時間分開處理就可以了，假設訪客 i 的來訪時間為 xi ，而離開時間為 yi 。在資料輸入完

34、畢之后，將 xi與yi分別進行排序（由小到大），道理很簡單，只要先計算某時 之前總共來訪了多少訪客，然后再減去某時之前的離開訪客，就可以輕易的解出這個問題。#include #include #define MAX 100#define SWAP(x,y) int t; t = x; x = y; y = t;int partition(int, int, int);void quicksort(int, int, int);1953年三月十七日1 10 31 33 37 70 48 60 80 801 10 31 33 37 48 70 60 80 801 10 31 33 37 48 60

35、 70 80 801 10 31 33 37 48 60 70 80 801 10 31 33 37 48 60 70 80 80插入排序像是玩樸克一樣，我們將牌分作兩堆，每次從后面一堆的牌抽出最前端的牌，然后插入前面一堆牌的適當位置，例如：排序前： 92 77 67 8 6 84 55 85 43 67將 77插入 92前將 67插入 77前將 8插入 67前將 6插入 8前將 84插入 92前將 55插入 67前77 92 67 8 6 84 55 85 43 6767 77 92 8 6 84 55 85 43 678 67 77 92 6 84 55 85 43 676 8 67 77

36、 92 84 55 85 43 676 8 67 77 84 92 55 85 43 676 8 55 67 77 84 92 85 43 676 8 55 67 77 84 85 92 43 676 8 43 55 67 77 84 85 92 676 8 43 55 67 67 77 84 85 92氣泡排序法顧名思義，就是排序時，最大的元素會如同氣泡一樣移至右端，其利用比較相鄰元素的方法，將大的元素交換至右端，所以大的元素會不斷的往右移動，直到適當的位置為止。基本的氣泡排序法可以利用旗標的方式稍微減少一些比較的時間，當尋訪完陣列后都沒有發生任何的交換動作，表示排序已經完成，而無需再進行之

37、后的回圈比較與交換動作，例如：排序前： 95 27 90 49 80 58 6 9 18 5027 90 4980 58 6 918 50 9595浮出27 49 8058 6 9 1850 90 9590浮出27 49 586 9 18 5080 90 9580浮出27 49 6 918 50 5880 90 9527 6 9 18 49 50 58 80 90 95 6 9 18 27 49 50 58 80 90 95 6 9 18 27 49 50 58 80 90 95由于接下來不會再發生交換動作，排序提早結束在上面的例子當中，還加入了一個觀念，就是當進行至i 與 i+1 時沒有交換

38、的動作，表示接下來的 i+2 至 n 已經排序完畢，這也增進了氣泡排序的效率。#include #include #include #define MAX 10#define SWAP(x,y) int t; t = x; x = y; y = t;void selsort(int); 3)n);return 0;void selsort(int number) int i, j, k, m;for(i = 0; i MAX-1; i+) m = i;for(j = i+1; j MAX; j+)if(numberj numberm)m = j;if( i != m)SWAP(numberi,

39、 numberm)printf( 第 %d 次排序： , i+1);for(k = 0; k MAX; k+) printf(%d , numberk);printf(n);void insort(int number) int i, j, k, tmp;for(j = 1; j MAX; j+) tmp = numberj;i = j - 1;while(tmp numberi) numberi+1 = numberi;i-;if(i = -1) break;numberi+1 = tmp;printf( 第 %d 次排序： , j);for(k = 0; k MAX; k+) printf

40、(%d , numberk);printf(n);void bubsort(int number) int i, j, k, flag = 1;for(i = 0; i MAX-1 & flag = 1; i+) flag = 0;for(j = 0; j MAX-i-1; j+) if(numberj+1 numberj) SWAP(numberj+1, numberj);flag = 1；printf( 第 d 次排序：，i+1);for(k = 0; k MAX; k+) printf(%d , numberk);printf(n);AlgoHthm Gossip: Shell排序法-改

41、良的插入排序說明插入排序法由未排序的后半部前端取出一個值，插入已排序前半部的適當位置，概念簡單但速度不快。排序要加快的基本原則之一，是讓后一次的排序進行時，盡量利用前一次排序后的結果，以加 快排序的速度，Shell排序法即是基于此一概念來改良插入排序法。解法Shell排序法最初是Shell于1959所提出，假設要排序的元素有n個，則每次進行插入排序時并 不是所有的元素同時進行時，而是取一段間隔。Shell首先將間隔設定為n/2 ,然后跳躍進行插入排序，再來將間隔n/4 ,跳躍進行排序動作，再來間隔設定為n/8、n/16,直到間隔為1之后的最 后一次排序終止，由于上一次的排序動作都會 將固定間隔

42、內的元素排序好，所以當間隔越來越小時，某些元素位于正確位置的機率越高，因 此最后幾次的排序動作將可以大幅減低。舉個例子來說，假設有一未排序的數字如右：89 12 65 97 61 81 27 2 61 98數字的總數共有10個，所以第一次我們將間隔設定為10 / 2 = 5 ，此時我們對間隔為5的數字進行排序，如下所示：畫線連結的部份表示要一起進行排序的部份，再來將間隔設定為5 / 2的商，也就是2,則第二次的插入排序對象如下所示：再來間隔設定為 2 / 2 = 1，此時就是單純的插入排序了，由于大部份的元素都已大致排序過了，所以最后一次的插入排序幾乎沒作什么排序動作了：將間隔設定為 n /

43、2 是 Shell 最初所提出，在教科書中使用這個間隔比較好說明，然而Shell 排序法的關鍵在于間隔的選定，例如Sedgewick證明選用以下的間隔可以加快Shell排序法的速度：其中4*(2j)2 + 3*(2 j) + 1不可超過元素總數n值，使用上式找出j后代入4*(2j)2 + 3*(2 j) + 1求得第一個間隔，然后將2j 除以 2代入求得第二個間隔，再來依此類推。后來還有人證明有其它的間隔選定法可以將Shell 排序法的速度再加快；另外Shell 排序法的概念也可以用來改良氣泡排序法。實作C#include #include #include #define MAX 10#de

44、fine SWAP(x,y) int t; t = x; x = y; y = t;void shellsort(int);int main(void) int numberMAX = 0;int i;srand(time(NULL);printf( 排序前： );for(i = 0; i 0) for(k = 0; k gap; k+) for(i = k+gap; i = k; j-=gap) if(numberj numberj+gap) SWAP(numberj, numberj+gap);elsebreak;printf(ngap = %d： , gap);for(i = 0; i

45、MAX; i+)printf(%d , numberi);printf(n);gap /= 2;AlgoHthm Gossip: Shaker排序法-改良的氣泡排序說明請看看之前介紹過的氣泡排序法：for(i = 0; i MAX-1 & flag = 1; i+) flag = 0;for(j = 0; j MAX-i-1; j+) if(numberj+1 right 時，則排序完成。實作C#include #include #include #define MAX 10#define SWAP(x,y) int t; t = x; x = y; y = t; void shakersor

46、t(int);int main(void) int numberMAX = 0;int i;srand(time(NULL);36. 排序法 - 改良的選擇排序說明選擇排序法的概念簡單， 每次從未排序部份選一最小值，插入已排序部份的后端，其時間主要花費于在整個未排序部份尋找最小值， 如果能讓搜尋最小值的方式加快， 選擇排序法的速率也就可以加快，Heap#序法讓搜尋的路徑由樹根至最后一個樹葉，而不是整個未排序部份，因而稱之為改良的選擇排序法。解法Heap排序法使用HeapTree （堆積樹），樹是一種資料結構，而堆積樹是一個二元樹，也就是每一個父節點最多只有兩個子節點（關于樹的詳細定義還請見資料

47、結構書籍） ，堆積樹的 父節點若小于子節點， 則稱之為最小堆積（ Min Heap） ， 父節點若大于子節點， 則稱之為最大堆積（ MaxHeap） ，而同一層的子節點則無需理會其大小關系，例如下面就是一個堆積樹：可以使用一維陣列來儲存堆積樹的所有元素與其順序， 為了計算方便， 使用的起始索引是1而不是0 ，索引1 是樹根位置，如果左子節點儲存在陣列中的索引為 s ，則其父節點的索引為 s/2 ，而右子節點為s+1 ，就如上圖所示，將上圖的堆積樹轉換為一維陣列之后如下所示： 首先必須知道如何建立堆積樹，加至堆積樹的元素會先放置在最后一個樹葉節點位置，然后檢查父節點是否小于子節點 （最小堆積）

48、， 將小的元素不斷與父節點交換，直到滿足堆積樹的條件為止，例如在上圖的堆積加入一個元素12，則堆積樹的調整方式如下所示：建立好堆積樹之后，樹根一定是所有元素的最小值，您的目的就是：將最小值取出然后調整樹為堆積樹不斷重復以上的步驟，就可以達到排序的效果，最小值的取出方式是將樹根與最后一個樹葉節 點交換，然后切下樹葉節點，重新調整樹為堆積樹，如下所示：調整完畢后，樹根節點又是最小值了，于是我們可以重覆這個步驟，再取出最小值，并調整樹 為堆積樹，如下所示：如此重覆步驟之后，由于使用一維陣列來儲存堆積樹，每一次將樹葉與樹根交換的動作就是將最小值放至后端的陣列，所以最后陣列就是變為已排序的狀態。其實堆積

49、在調整的過程中，就是一個選擇的行為，每次將最小值選至樹根，而選擇的路徑并不是所有的元素，而是由樹根至樹葉的路徑，因而可以加快選擇的過程，所以Heap#序法才會被稱之為改良的選擇排序法。#include #include #include #define MAX 10#define SWAP(x,y) int t; t = x; x = y; y = t;void createheap(int);void heapsort(int);int main(void) int numberMAX+1 = -1;int i, num;srand(time(NULL);printf( 排序前： );for

50、(i = 1; i = MAX; i+) numberi = rand() % 100;printf(%d , numberi); printf(n 建立堆積樹： );createheap(number);for(i = 1; i = MAX; i+)printf(%d , numberi);printf(n);heapsort(number);printf(n);return 0;void createheap(int number) int i, s, p;int heapMAX+1 = -1;for(i = 1; i = 2 & heapp heaps) SWAP(heapp, heap

51、s);s = p;p = s / 2;for(i = 1; i 1) SWAP(number1, numberm);m-;p = 1;s = 2 * p;while(s = m) if(s m & numbers+1 numbers) s+;if(numberp 0; i-) printf(%d , numberi);AlgoHthm Gossip:快速排序法(一)說明快速排序法(quick sort )是目前所公認最快的排序方法之一(視解題的對象而定)2然快速排序法在最差狀況下可以達O(n),但是在多數的情況下，快速排序法的效率表現是相當不錯的。快速排序法的基本精神是在數列中找出適當的軸心，

52、然后將數列一分為二，分別對左邊與右邊 數列進行排序，而影響快速排序法效率的正是軸心的選擇。這邊所介紹的第一個快速排序法版本，是在多數的教科書上所提及的版本,也最符合軸心分割與左右進行排序的概念，適合對初學者進行講解。因為它最容易理解,解法這邊所介紹的快速演算如下：將最左邊的數設定為軸，并記錄其值為迪圈處理： 令索引i 令索引j 如果i = j 如果i j從數列左方往右方找，直到找到大于從數列左右方往左方找，直到找到小于,則離開回圈,則交換索引i與j兩處的值s的數s的數將左側的軸與j進行交換對軸左邊進行遞回對軸右邊進行遞回透過以下演算法，則軸左邊的值都會小于s,軸右邊的值都會大于 s,如此再對軸

53、左右兩邊進行*表示要交換的數，口表示軸：遞回，就可以對完成排序的目的，例如卜面的實例，412476*114564216919 36*4124361145*64216919* 76412436111964*21*69)45 76412436111921646945 762124 :36 111941646945 76在上面的例子中， 41 左邊的值都比它小，而右邊的值都比它大，如此左右再進行遞回至排序完成。#include #include #include #define MAX 10#define SWAP(x,y) int t; t = x; x = y; y = t;void quick

54、sort(int, int, int);int main(void) int numberMAX = 0;int i, num;srand(time(NULL);printf( 排序前： );for(i = 0; i MAX; i+) numberi = rand() % 100;printf(%d , numberi);quicksort(number, 0, MAX-1);printf(n 排序后： );for(i = 0; i MAX; i+)printf(%d , numberi);printf(n);return 0;void quicksort(int number, int le

55、ft, int right) int i, j, s;if(left right) s = numberleft;i = left;j = right + 1;while(1) /向右找while(i + 1 & number+i -1 & number-j s) ;if(i = j)break;SWAP(numberi, numberj);numberleft = numberj;numberj = s;對左邊進行遞回對右邊進行遞回quicksort(number, left, j-1); /quicksort(number, j+1, right); /AlgoHthm Gossip:快速

56、排序法（二）說明在快速排序法（一）中，每次將最左邊的元素設為軸，而之前曾經說過，快速排序法的加速在于軸的選擇，在這個例子中，只將軸設定為中間的元素，依這個元素作基準進行比較， 這可以增加快速排序法的效率。確軍法在這個例子中，取中間的元素s作比較，同樣的先得右找比s大的索引i ,然后找比s小的索引j ,只要兩邊的索引還沒有交會， 就交換i與j的元素值，這次不用再進行軸的交換了， 因為在尋找交換的過程中，軸位置的元素也會參與交換的動作，例如：41 24 76 11 45 64 21 69 19 36首先 left 為0, right 為9, (left+right)/2=4 （取整數的商），所以軸

57、為索引4的位置，比較的元素是45,您往右找比45大的，往左找比45小的進行交換:41 24 76*11 4564 21 69 19 *3641 24 36 11 45* 64 21 69 19* 7641 24 36 11 19 64* 21* 69 45 76 4124 36 11 19 216469 45 76完成以上之后，再初別對左邊括號與右邊括號的部份進行遞回，如此就可以完成排序的目的。#include #include #include #define MAX 10#define SWAP(x,y) int t; t = x; x = y; y = t;void quicksort(

58、int, int, int);int main(void) int numberMAX = 0;int i, num;srand(time(NULL);printf(排序前：)；for(i = 0; i MAX; i+) numberi = rand() % 100;printf(%d , numberi);quicksort(number, 0, MAX-1);printf(n 排序后： );for(i = 0; i MAX; i+)printf(%d , numberi);printf(n);return 0;void quicksort(int number, int left, int

59、 right) int i, j, s;if(left right) s = number(left+right)/2;i = left - 1;j = right + 1;while(1) while(number+i s) ; / 向左找 if(i = j)break;SWAP(numberi, numberj);對左邊進行遞回對右邊進行遞回quicksort(number, left, i-1); /quicksort(number, j+1, right); /AlgoHthm Gossip:快速排序法（三）說明之前說過軸的選擇是快速排序法的效率關鍵之一，在這邊的快速排序法的軸選擇方式

60、更加快了快速排序法的效率，它是來自演算法名書Introduction to Algorithms 之中。解法先說明這個快速排序法的概念，它以最右邊的值s作比較的標準，將整個數列分為三個部份，一個是小于s的部份，一個是大于s的部份，一個是未處理的部份，如下所示：在排序的過程中，i與j都會不斷的往右進行比較與交換，最后數列會變為以下的狀態:然后將s的值置于中間，接下來就以相同的步驟會左右兩邊的數列進行排序的動作，如下所示:整個演算的過程，直接摘錄書中的虛擬碼來作說明: QUICKSORT(A, p, r)if p rthen q - PARTITION/, p, r) QUICKSORT(A, p