992-130024 資料結構與演算法(下)

原先我們在課堂上的方法是:
for (int i = data.length-1; i > 0; i--) {
    for (int j = 0; j < i; j++) {
        if (data[j] > data[j+1]) {
            int tmp = data[j];
            data[j] = data[j+1];
            data[j+1] = data[j];
        }
    }
}
這樣寫的話, best case 是 O(n^2), 不過有種implementation, 可以加一點多餘的判斷, 好讓Bubble Sort的best case 成為 O(n)
for (int i = data.length-1; i > 0; i--) {
    int swaps = 0;
    for (int j = 0; j < i; j++) {
        if (data[j] > data[j+1]) {
            int tmp = data[j];
            data[j] = data[j+1];
            data[j+1] = data[j];
            swaps++;
        }
    }
    if (swaps == 0) break;
}
事實上, wiki上有更好的方法

int n = data.length;
do {
    int newn = 0;
    for (int j = 0; j < n - 1; j++) {
        if (data[j] > data[j+1]) {
            int tmp = data[j];
            data[j] = data[j+1];
            data[j+1] = data[j];
            newn = j+1; // 最後一次發生swap的位置
        }
    }
    n = newn;
} while (n > 1);


以上是趙淑君同學在wiki上看到和老師的說法不同, 所提出的疑問. 謝謝趙同學的細心與用功, 請助教幫趙同學加點分數, 也希望能有更多的同學如此努力.
各位也可以把這次的作業版本修正一下, 看這樣做, Bubble Sort能快多少