冒泡排序如何优化？
冒泡排序，是经典的排序算法之一，简单粗暴，但是性能一般
思路
大概是循环遍历这个数组 ，遍历次数为数组的length减1次，长度为3的数据，把前两个元素与其他每个元素比较一次即可，最后一个元素，被动比较即可（例如数组：[2,4,1],一共三个元素，length为3，排序需要比较两轮即可，第一轮2与4比较，因为2小于4，所以位置不动，下标向下移动一位，4和1比较，因为4大于1，所以位置互换，首轮排序结束结果：[2,1,4],进入下次循环，2和1比较，位置互换，下标向下移动一位，2和4比较，位置不变，排序结束） h代码实现
var arr=[2,4,5,6,7,9,7,6,5,4,3,1]；
function maopao(arr){
var x=0;
var len=arr.length;
for (var i = 0; i <len-1; i++) {
h for (var j = 0; j < len-1; j++) {
x++;
if(arr[j]>arr[j+1]){
mid=arr[j];
arr[j]=arr[j+1];
arr[j+1]=mid;
}
}
}
console.log(x,'循环了几次') // 132 次
return arr;
}
console.log(maopao(arr));这样写有点浪费性能，因为每一次循环，后面都会多一个元素是排序完成的，所以，j的限制条件有误
function maopao(arr){
var x=0;
var len=arr.length;
for (var i = 0; i <len-1; i++) {
x++;
// 每比完一个元素，后面就多一个排序完成的元素，不必重比
for (var j = 0; j < len-1-i; j++) {
x++;
if(arr[j]>arr[j+1]){
mid=arr[j];
arr[j]=arr[j+1];
arr[j+1]=mid;
}
}
}
console.log(x,'循环了几次')
return arr;
} 根据上面的思路可得，后面排序完成的部分不必再排。所以
function maopao(arr){
var x=0;
var mid=null
var len=arr.length;
var maxChangeIndex=len;
var max=len;
for (let i = 0; i <len-1; i++) {
x++;
for (let j = 0; j < maxChangeIndex; j++) {
x++;
if(arr[j]>arr[j+1]){
// 循环结束后最后修改位置就排序未完成的末端
max=j;
mid=arr[j];
arr[j]=arr[j+1];
arr[j+1]=mid;
}
}
maxChangeIndex=max;
}
console.log(x,'循环了几次')
return arr;
}反过来想前面已经排序完成的点是否也可以记录，就是第一次改变位置的前一位。下次比较不必从零开始
function maopao(arr){
var x=0;
var mid=null
var len=arr.length;
var maxChangeIndex=len;
var minChangeIndex=0;
var max=len;
var min=0;
var flag=true;
for (let i = 0; i <len-1; i++) {
x++;
for (let j = minChangeIndex; j < maxChangeIndex; j++) {
x++;
if(arr[j]>arr[j+1]){
if(flag){
min=j===0?0:(j-1);
flag=false;
}
max=j;
mid=arr[j];
arr[j]=arr[j+1];
arr[j+1]=mid;
}
}
flag=true;
minChangeIndex=min;
maxChangeIndex=max;
}
console.log(x,'循环了几次')
return arr;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-04-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录