《程式設計珠玑》讀書筆記之冒泡排序

第一章

《程式設計珠玑》是一本好書，但對于我來說有點吃力，做一些筆記來記錄知識吧，希望能堅持寫筆記直到看完

第一個問題就是經典的排序問題，正好趁這個機會好好了解一下排序相關知識，做一點筆記作為備忘。

1. 排序

   公共函數swap

   待排序序列

function swap(arr, a, b) {//隻适用于整數交換
    arr[a] = arr[a] ^ arr[b]
    arr[b] = arr[a] ^ arr[b]
    arr[a] = arr[a] ^ arr[b]
}
           

冒泡排序

太長不看黨可以直接看最後的版本

基礎版本實作

最基本的雙層循環實作，每趟找到一個最大值

function maopao(arr) {
    let len = arr.length;
    for (let i = 0; i < len; i++) {
        for (let i = 0; i < len; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
            }
        }
    }
    console.log(arr);
}
maopao(arr);
           

減少趟數優化

針對1,2,3,4,6,5,7這種隻需要少于n次外循環排序就能有序的數組，

隻要其中某次循環沒有發生交換即有序，跳出循環，避免無效的比較操作

function maopao(arr) {
    let len = arr.length;
    for (let i = 0; i < len; i++) {
        let flag = true;
        for (let i = 0; i < len; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
                flag = false;
            }
        }
        if (flag) {
            console.log("break");
            break;
        }
    }
    console.log(arr);
}
maopao(arr);
           

緩存最大交換位置+反向冒泡尋找最小值

針對3,2,1, 4,5,6,7這種後半部分已經有序并且大于前半段的數組，每趟循環中比較45,56,67是沒有意義的，因為有序并且都大于前半段，是以不會發生交換，利用不發生交換這一點，找到最大的交換位置，下一趟比較久掃描到最大交換位置即可，不再比較後面的數值。

在每一趟中我們可以找到最大值，也可以優化一下，反向冒泡找到最小值，這樣可以減少外面循環的趟數。

function maopao(arr) {
    let len = arr.length;
    let pos = len;
    let temp = 0;
    for (let i = 0; i < len; i++) {
        let flag = true;
        for (let j = 0; j < pos; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                flag = false;
                temp = j;
            }
        }
        pos = temp;
        if (flag) {
            console.log("break");
            break;
        }
        for (let j = pos; j > 0; j--) {
            if (arr[j - 1] > arr[j]) {
                swap(arr, j - 1, j);
                flag = false;
            }
        }
        if (flag) {
            console.log("break1");
            break;
        }
    }
    console.log(arr);
}
           

另一種優化方式

這種方式減少了内部循環的次數+正反兩次冒泡

function BubbleSort(arr) {
    let len = arr.length;
    let flag = true;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < (len / 2) | 0; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                flag = false;
            }
            if (arr[len - 1 - j] < arr[len - 2 - j]) {
                swap(arr, len - 1 - j, len - 2 - j);
                flag = false;
            }
        }
        if (flag) {
            break;
        }
    }
    console.log(arr);
}
           

最終版本（優化+注釋）

如果還有疑問，這裡的程式可以自己直接複制去運作一遍，其中的注釋和列印資訊可以很清楚的得知每次做了什麼以及如何優化的

function swap(arr, a, b) {
    [arr[a], arr[b]] = [arr[b], arr[a]];
}
let arr = [91, 60, 96, 7, 35, 65, 10, 69, 9, 30, 20, 31, 77, 81, 24];
let tnt = 0;

function BubbleSort(arr) { //冒泡排序
    let len = arr.length;
    let pos = len; //記錄有序的邊界位置
    for (let i = 0; i < len; i++) {
        let flag = true;
        for (let j = 0; j < pos; j++) { //減少内循環比較操作的次數
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                flag = false;
                console.log(arr[j], arr[j + 1], "第" + (i + 1) + "次max檢索");
                tnt = j;
            }
        }
        if (flag) {
            console.log("break");
            break; //減少外循環趟數
        }
        pos = tnt;
        console.log("目前最大有序位置為" + pos);
        for (let j = pos; j > i; j--) { //反向冒泡找到最小值
            if (arr[j - 1] > arr[j]) {
                swap(arr, j - 1, j);
                flag = false;
                console.log(arr[j - 1], arr[j], "第" + (i + 1) + "次min檢索");
            }
        }
        if (flag) {
            console.log("break");
            break; //減少外循環趟數
        }
        //每趟（即每次外循環）都會找到一個目前最大值和最小值
        console.log("第" + (i + 1) + "趟排序結果：" + arr); 
    }
    console.log(arr);
}
BubbleSort(arr);