陌上寒

陌上寒个人博客

一篇文章搞定javascript冒泡排序

《一篇文章搞定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
一张图片描述的很形象
《一篇文章搞定javascript冒泡排序》

准备工作,造数据

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

  • 数组
  • 整数(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);

《一篇文章搞定javascript冒泡排序》

利用sort冒泡排序

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

《一篇文章搞定javascript冒泡排序》

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

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] = arr[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));

看下输出:
《一篇文章搞定javascript冒泡排序》
两层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));

《一篇文章搞定javascript冒泡排序》
第一次执行,找到最大的,并放在数组的左端
第二次执行,找到了第二大的,放在了做起第二的位置,
所以,内层循环可以做如下优化,当数据量很大的时候,显得尤为重要

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

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

发表评论

电子邮件地址不会被公开。