冒泡排序如何优化？

刘嘿哈

发布于 2022-10-25 06:19:03

51700

代码可运行

文章被收录于专栏：js笔记js笔记

运行总次数：0

代码可运行

冒泡排序，是经典的排序算法之一，简单粗暴，但是性能一般

思路

大概是循环遍历这个数组，遍历次数为数组的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;
}