本文由图雀社区认证作者 神奇的程序员 写作而成,图雀社区将连载其前端学习数据结构与算法系列,点击阅读原文查看作者的掘金链接,感谢作者的优质输出,让我们的技术世界变得更加美好?
当面试官问你什么是排序算法?请你用JavaScript实现一个简单的冒泡排序,如果你没掌握,就会被问住。
本文采用图文的方式讲解冒泡排序的特点,分步骤讲解js的实现思路以及相对应的代码,欢迎各位感兴趣的开发者阅读本文?
从序列的最右边开始比较相邻两个数字的大小,再根据结果交换两个数字的位置,重复这一操作的算法即冒泡排序。
如图所示,将下列数字按从小到大的顺序进行排列。
接下来,我们用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));
执行结果
本来对我的单层冒泡很自信,认为我写的单层效率肯定比双层的效率高,结果啪啪打脸,我拿我写的和网上的双层循环在控制台跑了一遍,才发现我写的简直就是垃圾。
当我疑惑我的效率为啥慢的时候,我朋友给了我结论,好吧,是我太菜了。
* 文中使用的图片源自《我的第一本算法书》,如若侵权,请联系图雀社区公众号小编,作者立即删除相关图片。