C 語言初學教材 - 第四章 氣泡排序法

電腦科學中已經發展出非常非常多種的排序演算法,因為排序跟搜尋同樣重要,排序過的資料結構,才有助於更快速的搜尋。



我們選擇的是一個概念簡單的氣泡排序法來作為帳號資料的排序之用,好處是概念簡單,但是處理的步驟稍多,所以排序大量資料會很費時間。簡單來說,如果我們希望帳號按英文字母的順序來排列,氣泡排序法會從頭依序比對兩筆資料的順序,沒有按照英文字母的順序就會交換兩筆資料的位置。


照這樣從頭跑到尾,只跑一次是不夠的,因為只跑一次只能確定把英文字母順序字串排到最後面,例如排列以下三個字母
c e b


我們用下圖說明氣泡排序法的運作



因為有三個字母,所以每一輪作兩次比較。第一輪第一次比較 c 與 e ,符合順序,不做任何更動。第一輪第二次比較 e 與 b ,不符合順序,所以交換。


第二輪第一次比較 c 與 b ,不符合順序,所以交換。第二輪第二次比較 c 與 e ,符合順序,不做任何更動,排序於是完成。


是不是很簡單呢?我們提供給 sort 指令的程式碼如下
// sort 為排序指令
if (!strcmp(instruction, "sort")) {
    for (j = 1; j < SIZE - 1; j++) {
        for (k = 2; k < SIZE; k++) {
            if (userID[k - 1][0] > userID[k][0]) {
                strcpy(tempName, userID[k - 1]);
                strcpy(tempCode, userCODE[k - 1]);
                strcpy(userID[k - 1], userID[k]);
                strcpy(userCODE[k - 1], userCODE[k]);
                strcpy(userID[k], tempName);
                strcpy(userCODE[k], tempCode);
            }
        }
    }
    counter = 1;
                            
    printf("\n資料已排序完成\n");
    continue;
}


注意第 161 行的外層 for 迴圈表示第幾輪,第 162 行的內層 for 迴圈表示第幾次。內層 for 迴圈中,我們用 k - 1 表示前一個帳號字串, k 表示後一個帳號字串,然後迴圈中我們比較的是帳號字串的第一個字元的大小,由於字元型態可以對應到 ASCII 的整數值,各字母是按順序遞增的,所以這裡如果 k - 1 大於 k ,就表示順序顛倒,需要交換。


至於怎麼做交換的呢?我們先用 tempName 及 tempCode 兩個字元陣列暫存 k - 1 的內容,然後把 k 的內容搬移到 k - 1 ,最後再把 tempName 及 tempCode 的內容回存到 k 之中,這樣,就完成交換了。


我們在最後把 counter 設為 1 ,這是為什麼呢?因為空字串含有字元 '\0' ,這個字元在 ASCII 表示 0 ,所以空字串都會被移到 userID 及 userCODE 兩個陣列的前面,具有內容的字串會排列在後面。


所以列印使用者列表的指令要稍作修改
// list 為列印使用者列表的指令
if (!strcmp(instruction, "list")) {
    printf("\n以下為所有註冊使用者的帳號及密碼\n");
    printf("\n帳號 - 密碼\n");
    for (j = 0; j < SIZE; j++) {
        if (userID[j][0] == '\0') {
            continue;
        }
                                
        printf("%s - %s\n", userID[j], userCODE[j]);
    }
    continue;
}


簡單說,就是 break 改成 continue 。


別忘了,用的新的變數 k ,要先宣告
// 宣告狀態變數、迴圈變數及陣列索引值變數
int state, i, j, k;
int counter;


這樣雖然是可以運作的程式,還是會有些問題,我們稍後會繼續討論。


完整的範例程式碼及編譯執行,請繼續參考


問題與討論
  1. 說明氣泡排序法的排序發方式。
  2. 有什麼方式可以改良氣泡排序法,使之效率提升呢?
  3. 程式第 43 行到第 46 行的作用是什麼?為什麼要加入這個 for 迴圈?
  4. 繼續測試這個版本的程式,找出可能會發生問題的地方。




沒有留言: