js实现的冒泡排序的问题

Question

function bubbleSort(arr){
    var len = arr.length,temp;
    for(var i = 0;i < len-1;i++){
    var isSorted = true;
    for(j = 0;j < len - 1 -i;j++){
    if(arr[j] > arr[j+1]){
    temp = arr[j];
    arr[j] = arr[j+1];
    arr[j+1] = temp;
    isSorted = false;
    }
    }
    if(isSorted){
    break;
    }
    }
    return arr;
}
var arrTest = [10,9,7,8,6,4,3,12,40];
console.log(bubbleSort(arrTest));

我有一个问题，这里i循环里面len不减一效果是一样的，如果不减是不是多了一次多余的比较，然后不使用bool来判断与使用效果也是一样的，使用是能提前中止排序很顺利的情况来提高效率？

Answer 1

我能回答什么呢？是的，是的。最后一个数不用比较，因为最后剩两个数要比较的时候，已经比较过了。if(isSorted)中这个isSorted为true时，就是里层循环中没有发生过交换，没有发生过交换，就意味着，已经排好了。外部的循环就可以中止了。提高了效率。

Answer 2

考虑最烂的逆序，冒泡排序对于N个数，要冒泡N-1次，每一次至少一个数归位。每次冒泡中的子循环，第一次遍历的数位为N-1，每次遍历的数位都要比上一次减一。也就是说，对于10个数，要循环9次，每次循环中的子循环，第一次为9，第二次为8。。。而数组的下标是0开始计数所以，通用的方法是for(var i=len-2;i>=0;i--){for(var x=0;x<=i;x++)}如果不减1只是多了无用的循环，这点你是对的。var arr=[9,8,7,6,5,4,4,3,2,1,3,2,5,23,5,6,12,1,7]; for(var i=arr.length-2;i>=0;i--)//!important { for(var x=0;x<=i;x++)//!important { if(arr[x+1]<arr[x]) { arr[x+1]^=arr[x]; arr[x]^=arr[x+1]; arr[x+1]^=arr[x]; } } } console.log(arr+'');

Answer 3

不减一当然会多一次咯。你如果想提高效率当然这个算法还不是最优的，你可以试着减少一些变量，尽量重用变量试试改进你的算法