首頁(yè) 猿問(wèn) js實(shí)現(xiàn)的冒泡排序的問(wèn)題

js實(shí)現(xiàn)的冒泡排序的問(wè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));我有一個(gè)問(wèn)題，這里i循環(huán)里面len不減一效果是一樣的，如果不減是不是多了一次多余的比較，然后不使用bool來(lái)判斷與使用效果也是一樣的，使用是能提前中止排序很順利的情況來(lái)提高效率？

查看完整描述

5 回答

已采納

信者得救

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

我能回答什么呢？

是的，是的。

最后一個(gè)數(shù)不用比較，因?yàn)樽詈笫蓚€(gè)數(shù)要比較的時(shí)候，已經(jīng)比較過(guò)了。

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

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

anet

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

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

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

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

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

所以，通用的方法是

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

{

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

}

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

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

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