最新消息:阿里云双12优惠,史上最低折扣。

JavaScrip实现冒泡排序

服务器租用 aliyun 92浏览

Flutter 路由——页面表及页面参数绑定的自动生成

Flutter 自带完善的路由框架,可以直接用Navigator.of(context).push(route)打开新页面或者用命名的方式

当面试官问你什么是排序算法?请你用JavaScript实现一个简单的冒泡排序,如果你没掌握,就会被问住。

本文采用图文的方式讲解冒泡排序的特点,分步骤讲解js的实现思路以及相对应的代码。

概念

从序列的最右边开始比较相邻两个数字的大小,再根据结果交换两个数字的位置,重复这一操作的算法即冒泡排序。

特点

从序列的末尾开始比较相邻两个数字的大小

如果比较的数据比左边相邻的数据小,则左移当前比较的数据。

直至当前比较数据的位置等于当前比较次数时,则一轮结束。

比较完一轮后,如果当前轮数不等于序列的长度,则继续从末尾开始比较。

图解示例

如图所示,将下列数字按从小到大的顺序进行排列。

 

排序过程1

从数据的末尾开始比较相邻两个数字的大小

 

排序过程2

比较后,发现6<7,故交换位置。

 

排序过程3

完成后,将6与相邻的数字4进行比较,6>4,故不交换位置

 

排序过程4

完成后,将4与相邻的数字8进行比较,4<8,故交换位置

重复同样的操作进行比较,直到当前比较的值到数据的最左边为止。

不断对数字进行交换,直到当前比较的数字到了最左边,无相邻数据可比较,序列中最小的数字就会移动到最左边。

 

排序过程5

继续下一轮排序,从数据的末尾继续进行比较,直到比较到数据的第2个位置为止。

 

排序过程6

当比较到数据的左边第2个位置时,序列中第2小的数字也就到达了指定位置。

重复上述操作,直到当前比较的数字的位置为当前比较的次数,即排序完成。

 

排序过程7

实现思路

声明一个函数,参数为一个数组

初始化比较轮数为1

对数组进行遍历

在循环中获取当前比较值在数组中的的下标:数组长度 – 当前循环次数

在循环中获取当前比较值左侧相邻值在数组中的下标:数组长度 – (当前循环的次数+2)

得到下标后,分别获取当前比较值和与之左侧相邻的值

判断当前比较值的数组下标是否等于当前轮数

如果相等则轮数自增1,如果当前轮数不等于数组长度则让循环继续执行

如果不相等,则比较当前值与左侧相邻值的大小,如果当前值<左侧相邻值,则进行位置交换

如果当前轮数等于数组长度,循环结束,返回排序好的数组。

接下来,我们用JavaScript根据实现思路来实现下冒泡排序。

const bubbleSort = function (arr) {

    // 比较的轮数

    let round = 1;

    for (let i = 0; i < arr.length;i++){

        // 当前比较值的位置 = 数组长度 – 当前循环的次数(i从0开始,所以需要+1)

        const compareIndex = arr.length-(i+1);

        // 与当前比较值左侧相邻值的位置 = 数组长度 – (当前循环的次数+2)

        const leftNeighborIndex = arr.length-(i+2);

        // 获取当前比较的值

        const compareVal = arr[compareIndex];

        // 获取与之相邻的左侧值

        const leftNeighborVal = typeof arr[leftNeighborIndex] !==”undefined”?arr[leftNeighborIndex]:””;

        // 如果当前比较值的位置等于轮数(因为轮数是从1开始的,数组下标是从0开始的,所以需要-1)时则一轮结束

        if(compareIndex===round-1){

            console.log(`第${round}轮结束: ${arr},共比较${i}次`);

            // 轮数增加

            round ++;

            // 如果当前轮数不等于数组长度则循环继续

            if(round!==arr.length){

                i = -1;

            }

        } else{

            // 比较当前值与左侧相邻值的大小

            if(compareVal<leftNeighborVal){

                // 交换位置,使用结构赋值实现。[array[index1],array[index2]] = [array[index2],array[index1]]

                [arr[compareIndex],arr[leftNeighborIndex]] = [arr[leftNeighborIndex],arr[compareIndex]];

            }

        }

    }

    return arr;

};

// 声明一个乱序

const dataArr = [5,8,2,7,9,1,10,0];

// 调用函数

console.log(bubbleSort(dataArr));

转载请注明:小猪云服务器租用推荐 » JavaScrip实现冒泡排序