冒泡排序是我们会经常用到的排序方法，本文记录一下冒泡排序及优化的实现方法，希望对大家有所帮助

一、 前情提要

js 中可以使用数组的原生方法 sort 来进行排序。默认排序顺序是在将元素转换为字符串，然后比较它们的 UTF-16 代码单元值序列时构建的

直接使用 sort，元素会按照转换为的字符串的诸个字符的 Unicode 位点进行排序

let arr = [4,2,8,10,1];
arr.sort()
console.log(arr) // [1, 10, 2, 4, 8]

会发现，上面的结果中，10 在 2 的前面，不过 sort 方法有一个可选参数可以传入一个函数，解决数字类型数组的排序问题

let arr = [4,2,8,10,1];
function compareNumbers(a, b) {
  return a - b;
}

arr.sort(compareNumbers)
console.log(arr) // [1, 2, 4, 8, 10]

二、冒泡排序实现 sort

1、基础实现

let arr = [4,2,8,10,1,9,10,6,20,21,22,23];
let count = 0;
function sort (arr) {
    for(let i=0; i < arr.length-1; i++){
        for(let j=0; j < arr.length-i-1; j++){
            if (arr[j] > arr[j+1]) {
                let tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
            count++;
        }
    }
    return arr
}
let result = sort(arr);
console.log(count) // 66
console.log(result) // [1, 2, 4, 6, 8, 9, 10, 10, 20, 21, 22, 23]

n 为数组长度，执行次数为 n(n-1)/2，时间复杂度为 O(n^2)

2、增加有序标示位

基础实现中，如果在进行到最后一轮循环之前数组已经有顺序，但是排序算法还是会执行后面的循环，所以我们可以添加一个标示，如果内层循环，没有数据交换说明已经有序，可以提前退出循环。

let arr = [4,2,8,10,1,9,10,6,20,21,22,23];
let count = 0;
function sort (arr) {
    for(let i=0; i < arr.length-1; i++){
        let isSorted = true; // 有序标记初始值为true
        for(let j=0; j < arr.length-i-1; j++){
            if (arr[j] > arr[j+1]) {
                let tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                isSorted = false; // 有元素交换则数组为无序
            }
            count++;
        }
        if (isSorted) {
            break;
        }
    }
    return arr
}
let result = sort(arr);
console.log(count) // 45
console.log(result) // [1, 2, 4, 6, 8, 9, 10, 10, 20, 21, 22, 23]

基础实现需要 66 次，如果实现有序的轮次更靠前，可以更明显。

3、增加有序标示位

第二种优化，只有在全部有序的情况下才会终止循环，如果数组已经有部分有序，还是要遍历。
为了优化这种情况，可以添加一个有序区的标示位，记录最后一次交换元素的位置。代码如下：

let arr = [4,2,8,10,1,9,10,6,20,21,22,23];
let count = 0;
function sort (arr) {
    // 记录最后一次交换元素的位置
    let lastExchangeIndex = 0;
    // 无序数列边界
    let sortBorder = arr.length - 1
    for(let i=0; i < arr.length-1; i++){
        let isSorted = true; // 有序标记初始值为true
        for(let j=0; j < sortBorder; j++){
            if (arr[j] > arr[j+1]) {
                let tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                isSorted = false; // 有元素交换则数组为无序
                lastExchangeIndex = j;
            }
            count++;
        }
        sortBorder = lastExchangeIndex
        if (isSorted) {
            break;
        }
    }
    return arr
}
let result = sort(arr);
console.log(count) // 29
console.log(result) //  [1, 2, 4, 6, 8, 9, 10, 10, 20, 21, 22, 23]

优化无止境，本文参考漫画算法中的代码实现。

最后

感谢各位的阅读，如有不对欢迎批评指正，共同交流。