今天咱們來(lái)說(shuō)說(shuō)冒泡排序吧匪燕！
廢話少說(shuō)，先把代碼給肝出來(lái)龟再？
const arr = [9, 5, 6, 3, 2, 7, 1, 8, 4]
function sort(arr) {
let temp = null
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}
console.log(sort(arr))
運(yùn)行結(jié)果：
ok利凑，沒(méi)問(wèn)題哀澈！
那么，再仔細(xì)想想膨报，真的是沒(méi)有什么問(wèn)題嗎适荣？
emmm，應(yīng)該是沒(méi)什么問(wèn)題啊够吩，結(jié)果也是正確的丈氓。
好的，那么可不可以進(jìn)行優(yōu)化呢鱼鼓？
比如该编，數(shù)組的數(shù)據(jù)如下：
const arr = [1, 2, 3, 4, 5, 6, 9, 8, 7]
我們?cè)谘h(huán)語(yǔ)句內(nèi)隨便打印個(gè)東西看看總共會(huì)運(yùn)行幾次
數(shù)不清了课竣，大家可以自己數(shù)數(shù)于樟。通過(guò)觀察其實(shí)我們可以發(fā)現(xiàn)拇囊，有很多地方其實(shí)是不需要排序的寥袭，因?yàn)槎际且呀?jīng)排好的了关霸，而且那些地方杰扫，不是只運(yùn)行了一遍章姓，而是每個(gè)大循環(huán)里都會(huì)去運(yùn)行一遍。零渐。系忙。
ok笨觅，現(xiàn)在我們知道了這么一種情況，那么怎么去優(yōu)化它呢杀糯？
其實(shí)很簡(jiǎn)單苍苞，每次大循環(huán)開(kāi)始時(shí)羹呵，我們定義一個(gè)變量骂际，默認(rèn)值為true，用來(lái)標(biāo)識(shí)數(shù)組是否已經(jīng)排好序冈欢。如果接下來(lái)的小循環(huán)中有元素交換過(guò)位置歉铝，我們將這個(gè)變量設(shè)為false，否則不變凑耻。等小循環(huán)完后太示，我們?nèi)タ纯催@個(gè)變量是否為false，如果為false香浩，是不是說(shuō)明這一次循環(huán)有元素交換過(guò)位置类缤，那么我們繼續(xù)進(jìn)行下一次大循環(huán)；如果為true邻吭，是不是說(shuō)明這一次循環(huán)沒(méi)有元素交換過(guò)位置，換言之，所有的元素其實(shí)已經(jīng)是排好序的了膏蚓，對(duì)嗎猖败？對(duì)啊，沒(méi)毛病敖翟省恩闻！那么我們直接結(jié)束所有循環(huán)，最后直接返回這個(gè)數(shù)組就好啦剧董！幢尚，廢話少說(shuō)，開(kāi)始優(yōu)化走起翅楼！
const arr = [1, 2, 3, 4, 5, 6, 9, 8, 7]
function sort(arr) {
let temp = null
for (let i = 0; i < arr.length; i++) {
console.log('大循環(huán)')
let isSorted = true // 新代碼
for (let j = 0; j < arr.length - 1 - i; j++) {
console.log('小循環(huán)')
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
}
console.log(sort(arr))
來(lái)看結(jié)果：
是不是智能了很多尉剩，ok，那么到這真的就結(jié)束了嗎毅臊？再想想還有沒(méi)有地方可以?xún)?yōu)化呢理茎？
我們?cè)倏纯慈缦聢?chǎng)景
const arr = [5, 4, 3, 2, 1, 6, 7, 8, 9]
結(jié)果如下：
通過(guò)觀察我們可以發(fā)現(xiàn)，這個(gè)數(shù)組后半部分其實(shí)已經(jīng)排好序了管嬉，那么我們還有必要每一次都去對(duì)后半部分去進(jìn)行排序嗎皂林？當(dāng)然不需要！
那么如何來(lái)解決這個(gè)問(wèn)題呢蚯撩？
我們可以在最開(kāi)始定義兩個(gè)變量础倍，一個(gè)是小循環(huán)的初始結(jié)束條件arrLength（arr.length - 1），另一個(gè)是當(dāng)前這一次大循環(huán)的小循環(huán)結(jié)束后胎挎，最后一次元素交換的前一個(gè)數(shù)的索引lastChangeIndex（默認(rèn)為0）沟启。然后在小循環(huán)中，將結(jié)束條件設(shè)為剛剛設(shè)置的初始條件犹菇，如果有元素交換德迹，則將前一個(gè)數(shù)的索引賦值給前面定義的索引變量。每一次小循環(huán)結(jié)束揭芍，我們將arrLength = lastChangeIndex就可以啦胳搞！讓每次小循環(huán)在最后一次交換元素結(jié)束，就保證了后面已經(jīng)排好序的數(shù)據(jù)不需要重復(fù)去對(duì)比排序啦沼沈！
老規(guī)矩流酬，上代碼！
const arr = [5, 4, 3, 2, 1, 6, 7, 8, 9]
function sort(arr) {
let temp = null,
arrLenth = arr.length - 1, // 新代碼
lastChangeIndex = 0 // 新代碼
for (let i = 0; i < arr.length; i++) {
console.log('大循環(huán)')
let isSorted = true
for (let j = 0; j < arrLenth; j++) {
console.log('小循環(huán)')
if (arr[j] > arr[j + 1]) {
temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
isSorted = false
lastChangeIndex = j // 新代碼
}
}
// 新代碼
arrLenth = lastChangeIndex
if (isSorted) {
break
}
}
return arr
}
console.log(sort(arr))
結(jié)果如下：
ok列另，大功告成！
