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

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