一篇文章搞定javascript冒泡排序

从今天开始讲述关于javascript的排序

冒泡排序

冒泡排序是最慢的排序算法之一，但也是最容易实现的排序算法。
之所以叫冒泡排序是因为这种算法在排序时，数据值会像气泡一样从数组的一端漂浮到另一端，假设正在将一组数字按照升序排列，较大的值会浮动到数组的右侧，较小的值会浮动到数组的左侧，之所以会产生这种现象是因为算法会多次在数组中移动，比较相邻的数据，当左侧的值大于右侧的值时，将他们进行互换。

一个简单的🌰：
E A D B H
经过第一次排序后：
A E D B H
第一个和第二个元素进行了互换

经过第二次排序：
A D E B H
第二个和第三个进行了互换

经过第三次排序：
A D B E H
第三个和第四个进行了互换

最后，第二个和第三个再次进行互换，得到最终顺序：
A B D E H
一张图片描述的很形象

准备工作，造数据

我们先准备一组随机数据，用来排序使用
要求：

• 数组
• 整数（0-100）

let arr = []

function arrData(num) {
    for (let i = 0; i < num; i++) {
        arr[i] = Math.floor(Math.random() * num + 1)
    }
}
arrData(100)
console.log(arr);

利用sort冒泡排序

arr = arr.sort(function (a, b) {
    return a - b
});
console.log(arr); 

通过添加中间变量实现冒泡排序

let arr = []

function arrData(num) {
    for (let i = 0; i < num; i++) {
        arr[i] = Math.floor(Math.random() * num + 1)
    }
}
arrData(10)
function sortarr(myArr) {
    for (let i = 0; i < myArr.length - 1; i++) {
        for (let j = 0; j < myArr.length - 1; j++) {
            if (myArr[j] > myArr[j + 1]) {
                let temp = myArr[j];
                myArr[j] = myArr[j + 1];
                myArr[j + 1] = temp;
            }
        }
    }
    return myArr;
}
let arr1 =   sortarr(arr)
console.log(arr1);

输出结果是一样的

不通过添加中间变量实现冒泡排序

不使用中间变量，算法原型如下：（不使用第三个变量，互换两个元素）

a = 10; //第一个元素
b = 5; //下一个元素
if (a > b) {
    a = a + b; // a(15) = 10 +5;
    b = a - b; // b(10) = 15 - 5;
    a = a - b; // a(5) = 15 - 10;
}

冒泡排序如下：

function jssort(myArr) {
    for (let i = 0; i < myArr.length-1; i++) { //要循环多少次
        for (let j = 0; j < myArr.length  - 1; j++) { //要移动几次
            if (myArr[j] > myArr[j + 1]) {
                myArr[j] = myArr[j] + myArr[j + 1]; //a = a+b 
                myArr[j + 1] = myArr[j] - myArr[j + 1]; //b = a-b
                myArr[j] = myArr[j] - myArr[j + 1]; //a = a-b
            }
        }
    }
    return myArr;
}

通过es6，可以实现同样的效果
算法原型：

let arr1 = [1,3]
[1,3]=[3,1]
console.log(arr1);//=>?[3, 1]

排序

function jssort(myArr) {
    for (let i = 0; i < myArr.length-1; i++) { //要循环多少次
        for (let j = 0; j < myArr.length  - 1; j++) { //要移动几次
            if (myArr[j] > myArr[j + 1]) {
                [myArr[j] , myArr[j + 1]]=[myArr[j+1] , myArr[j]]
            }
        }
    }
    return myArr;
}

冒泡排序的一次优化

我们之前的数组的长度是100，不利于观察，我们声明一个简单一点的数组

var arr = [65, 39, 28, 11, 10, 3];
function jssort(myArr) {
    for (let i = 0; i < myArr.length - 1; i++) { //要循环多少次
        console.log(`第${i}次`);
        for (let j = 0; j < myArr.length - 1; j++) { //要移动几次
            if (myArr[j] > myArr[j + 1]) {
                [myArr[j], myArr[j + 1]] = [myArr[j + 1], myArr[j]]
            }
            console.log(arr);
        }
    }
    return myArr;
}
console.log(jssort(arr));

看下输出：

两层for循环，当i=0的时候，里面的循环完整执行，从j=0执行到j=5,这也就是第一遍排序，结果是将最大的数排到了最后

当i=1的时候，里面的循环再次完整执行，由于最大的数已经在最后了，没有必要去比较数组的最后两项，所以可以做一下优化：

var arr = [65, 39, 28, 11, 10, 3];
function jssort(myArr) {
    for (let i = 0; i < myArr.length - 1; i++) { //要循环多少次
        console.log(`第${i}次`);
        for (let j = 0; j < myArr.length - 1 - i; j++) { //要移动几次
            if (myArr[j] > myArr[j + 1]) {
                [myArr[j], myArr[j + 1]] = [myArr[j + 1], myArr[j]]
            }
            console.log(arr);
        }
    }
    return myArr;
}
console.log(jssort(arr));

第一次执行，找到最大的，并放在数组的左端
第二次执行，找到了第二大的，放在了做起第二的位置，
所以,内层循环可以做如下优化，当数据量很大的时候，显得尤为重要

for (let j = 0; j < myArr.length - 1 - i; j++) {
    //....
}

好了，关于javascript冒泡排序就讲到这里了，明天我们继续讨论js排序的其他算法