《编程珠玑》读书笔记之冒泡排序

第一章

《编程珠玑》是一本好书，但对于我来说有点吃力，做一些笔记来记录知识吧，希望能坚持写笔记直到看完

第一个问题就是经典的排序问题，正好趁这个机会好好了解一下排序相关知识，做一点笔记作为备忘。

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);