SOURCE

let arr = [1, 4, 2, 3, 11, 23, 8, 10]

function bubble(arr) {
    const len = arr.length;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - i; j++) {
            if (arr[j] > arr[j + 1]) {        // 相邻元素两两对比
                var temp = arr[j + 1];        // 元素交换
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr
}
// console.log(bubble(arr))

/**
 * 如果上面代码中，里面一层循环在某次扫描中没有执行交换，
 * 则说明此时数组已经全部有序列，无需再扫描了。
 * 因此，增加一个标记，每次发生交换，就标记，
 * 如果某次循环完没有标记，则说明已经完成排序。
 * 
*/
function bubbleUpdate(arr) {
    const len = arr.length;
    let bool = true;
    for (let i = 0; i < len; i++) {
        bool = false
        for (let j = i; j < len - i; j++) {
            if (arr[j] > arr[j + 1]) {        // 相邻元素两两对比
                var temp = arr[j + 1];        // 元素交换
                arr[j + 1] = arr[j];
                arr[j] = temp;
                bool = true;
            }
        }
        if (!bool) break;
    }
    return arr
}
// console.log(bubbleUpdate(arr))
/**
 * 如果R[0..i]已是有序区间，上次的扫描区间是R[i..n]，
 * 记上次扫描时最后 一次执行交换的位置为lastSwapPos，
 * 则lastSwapPos在i与n之间，不难发现R[i..lastSwapPos]区间也是有序的，
 * 否则这个区间也会发生交换；
 * 所以下次扫描区间就可以由R[i..n] 缩减到[lastSwapPos..n]
 * 
*/
function bubbleUpdate2(arr) {
    const len = arr.length;
    let first = 0;
    let last = 0;
    for (let i = 0; i < len; i++) {
        first = last;
        for (let j = len - 1; j > first; j--) {
            if (arr[j - 1] > arr[j]) {
                let temp = arr[j]
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                last = j;
            }
        }
        if (first == last) break;
    }
    return arr
}
console.log(bubbleUpdate2(arr))