冒泡排序（JS版）

1.冒泡排序

让数组当中相邻的两个数进行比较，数组当中比较小的数值向下沉，数值比较大的向上浮！外层for循环控制循环次数，内层for循环控制相邻的两个元素进行比较

2.代码实现

/**
 * 适用的情景为数据量不大，对稳定性有要求，且数据基本有序的情况下。
 * @type {number[]}
 */

var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48, 234, 35, 23, 5, 23];

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

console.time('bubbleSort1:');
console.log(bubbleSort1(arr));
console.timeEnd('bubbleSort1:');

//方法2
function bubbleSort2(arr) {
    var i = arr.length - 1;  //初始时,最后位置保持不变
    while (i > 0) {
        var pos = 0; //每趟开始时,无记录交换
        for (var j = 0; j < i; j++)
            if (arr[j] > arr[j + 1]) {
                pos = j; //记录交换的位置
                var tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        i = pos; //为下一趟排序作准备
    }
    return arr;
}

console.time('bubbleSort2:');
console.log(bubbleSort2(arr));
console.timeEnd('bubbleSort2:');

//方法3
function bubbleSort3(arr) {
    var low = 0;
    var high = arr.length - 1; //设置变量的初始值
    var tmp, j;
    while (low < high) {
        for (j = low; j < high; ++j) //正向冒泡,找到最大者
            if (arr[j] > arr[j + 1]) {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        --high;                 //修改high值, 前移一位
        for (j = high; j > low; --j) //反向冒泡,找到最小者
            if (arr[j] < arr[j - 1]) {
                tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;
            }
        ++low;                  //修改low值,后移一位
    }
    return arr;
}

console.time('bubbleSort3:');
console.log(bubbleSort3(arr));
console.timeEnd('bubbleSort3:');

//方法4
function bubbleSort4(arr) {
    let len = arr.length;
    let flag = true;
    for (let i = 0; i < len - 1 && flag; i++) {
        flag = false;
        for (let j = len - 1; j > i; j--) {
            if (arr[j] < arr[j - 1]) {
                let temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                flag = true;
            }
        }
        if (!flag) break;
    }
    return arr;
}

console.time('bubbleSort4:');
console.log(bubbleSort4(arr));
console.timeEnd("bubbleSort4:");