首頁猿問 js實現(xiàn)的冒泡排序的問題

js實現(xiàn)的冒泡排序的問題

JavaScript

西蘭花偉大炮 2017-09-16 21:40:27

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循環(huán)里面len不減一效果是一樣的，如果不減是不是多了一次多余的比較，然后不使用bool來判斷與使用效果也是一樣的，使用是能提前中止排序很順利的情況來提高效率？

查看完整描述

5 回答

已采納

信者得救

TA貢獻(xiàn)22條經(jīng)驗獲得超10個贊

我能回答什么呢？

是的，是的。

最后一個數(shù)不用比較，因為最后剩兩個數(shù)要比較的時候，已經(jīng)比較過了。

if(isSorted)中這個isSorted為true時，就是里層循環(huán)中沒有發(fā)生過交換，沒有發(fā)生過交換，就意味著，已經(jīng)排好了。外部的循環(huán)就可以中止了。提高了效率。

反對回復(fù) 2017-09-16

anet

TA貢獻(xiàn)79條經(jīng)驗獲得超19個贊

考慮最爛的逆序，冒泡排序?qū)τ贜個數(shù)，要冒泡N-1次，每一次至少一個數(shù)歸位。

每次冒泡中的子循環(huán)，第一次遍歷的數(shù)位為N-1，每次遍歷的數(shù)位都要比上一次減一。

也就是說，對于10個數(shù)，要循環(huán)9次，每次循環(huán)中的子循環(huán)，第一次為9，第二次為8。。。

而數(shù)組的下標(biāo)是0開始計數(shù)

所以，通用的方法是

for(var i=len-2;i>=0;i--)

{

for(var x=0;x<=i;x++)

}

如果不減1只是多了無用的循環(huán)，這點你是對的。

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+'');

反對回復(fù) 2017-09-16