資訊專欄INFORMATION COLUMN
摘要：如下是一個(gè)基本的冒泡排序算法，執(zhí)行的過(guò)程外部循環(huán)次內(nèi)部循環(huán)每次用的值與的值進(jìn)行比較由于外部循環(huán)的變量每次進(jìn)入內(nèi)部循環(huán)都不會(huì)改變，也就是的值進(jìn)入內(nèi)部循環(huán)后，都會(huì)以自身與也就是整個(gè)數(shù)組的所有元素比較一輪，結(jié)果是小于的數(shù)值都會(huì)被放到數(shù)組的開頭經(jīng)過(guò)
如下是一個(gè)基本的冒泡排序算法，執(zhí)行的過(guò)程
外部循環(huán)len次
內(nèi)部循環(huán)每次用arr[i]的值與arr[j]的值進(jìn)行比較
由于外部循環(huán)的i變量每次進(jìn)入內(nèi)部循環(huán)都不會(huì)改變，也就是arr[i]的值進(jìn)入內(nèi)部循環(huán)后，都會(huì)以自身與arr[j]（也就是整個(gè)數(shù)組的所有元素）比較一輪，結(jié)果是小于arr[i]的數(shù)值都會(huì)被放到數(shù)組的開頭
經(jīng)過(guò)外層循環(huán)的一次次的進(jìn)入內(nèi)層循環(huán)的比對(duì)后，數(shù)組也依照從小到大的順序排列了
let arr = [1, 3, 2]
let len = arr.length
for(let i = 0; i < len; i++){
for(let j = 0; j < len; j++){
if(arr[i] > arr[j]){
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
}
我們來(lái)分解步驟
第一輪外層循環(huán) i = 0
第一輪內(nèi)部循環(huán)
j = 0
arr[i] = 1 arr[j] = 1 arr[i] > arr[i]不成立，j++， arr保持現(xiàn)狀 [1, 3, 2]
j = 1
arr[i] = 1 arr[j] = 3 arr[i] > arr[j]不成立，j++, arr保持原樣 [1, 3, 2]
j = 2
arr[i] = 1 arr[j] = 2 arr[i] > arr[j]不成立，j++, arr保持原樣 [1, 3, 2]
j = 3
arr[i] = 1 arr[j] = undefined 由于len = 3 ,故 j < len不成立，第一輪層循環(huán)結(jié)束
第二輪外層循環(huán) i = 1
第二輪內(nèi)部循環(huán)
j = 0
arr[i] = 3 arr[j] = 1 arr[i] > arr[i]成立， arr[i]和arr[j]交換數(shù)值,arr更新為[3, 1, 2]
j = 1
arr[i] = 1 arr[j] = 1 arr[i] > arr[i]不成立，j++, arr保持原樣 [3, 1, 2]
j = 2
arr[i] = 1 arr[j] = 2 arr[i] > arr[i]不成立，j++, arr保持原樣 [3, 1, 2]
j = 3
arr[i] = 1 arr[j] = undefined 由于len = 3 ,故 j < len不成立，第二輪層循環(huán)結(jié)束
第三輪外層循環(huán) i = 2
第三輪內(nèi)部循環(huán)
j = 0
arr[i] = 2 arr[j] = 3 arr[i] > arr[i]不成立，j++, arr保持原樣 [3, 1, 2]
j = 1
arr[i] = 2 arr[j] = 1 arr[i] > arr[i]成立, arr[i]和arr[j]交換數(shù)值,arr更新為[3, 2, 1]
j = 2
arr[i] = 1 arr[j] = 1 arr[i] > arr[i]不成立，j++, arr保持原樣 [3, 2, 1
j = 3
由于眾所周知的原因，第三輪內(nèi)部循環(huán)結(jié)束
第四輪外層循環(huán) i = 3
由于i < len不成立，外部循環(huán)結(jié)束，現(xiàn)在我們的數(shù)組最終結(jié)果為[3, 2, 1]
接下來(lái)我們來(lái)看看有沒(méi)有優(yōu)化的空間
我們發(fā)現(xiàn)，每次內(nèi)部循環(huán)都市從索引 let j = 0; 開始的，也就是說(shuō)每次內(nèi)部循環(huán) arr[j]
都會(huì)把數(shù)組遍歷一遍，由于在上一次的內(nèi)部循環(huán)結(jié)束后，都會(huì)把最大的數(shù)放到數(shù)組的頭部，所以再次進(jìn)入內(nèi)部循環(huán)時(shí)，如果還去從頭比較就是浪費(fèi)時(shí)間
所以如何讓內(nèi)部循環(huán)將上次列入最大值的位置忽略呢？
答案就是i變量,每次結(jié)束一次外部循環(huán)i變量都會(huì)加1，這也代表著有i個(gè)最大值被置于數(shù)組頭部，也就是我們需要忽略的位置，所以，我們只需要將內(nèi)部循環(huán)的起始位置i加上i，就可以將已經(jīng)確定的位置忽略比較
for(let i = 0; i < len; i++){
for(let j = 0 + i; j < len; i++){
// 直接簡(jiǎn)寫成let j = i也行
}
}
然后我們來(lái)驗(yàn)證一下優(yōu)化的成果
用一個(gè)大一點(diǎn)的數(shù)組，并且記錄下循環(huán)次數(shù)
let arr = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7]
let len = arr.length
let count = 0
for(let i = 0; i < len; i++){
for(let j = 0; j < len; j++){
count++
if(arr[i] > arr[j]){
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
}
console.log(arr, count)
arr = [324, 76, 65, 62, 56, 51, 45, 44, 43, 43, 34, 7, 7, 7, 6, 6, 6, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 0]
count = 1156次
下面看下優(yōu)化過(guò)的
let arr = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7]
let len = arr.length
let count = 0
for(let i = 0; i < len; i++){
for(let j = i; j < len; j++){
count++
if(arr[i] > arr[j]){
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
}
console.log(arr, count)
arr = [0, 1, 1, 1, 2, 2, 2, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 34, 43, 43, 44, 45, 51, 56, 62, 65, 76, 324]
595次
結(jié)果毋庸置疑減少了近半數(shù)的無(wú)用循環(huán)，那么到此為止了嗎？
讓我們?cè)賮?lái)看看
我們現(xiàn)在用的比較方式是基于用數(shù)組中的一個(gè)位置與所有位置進(jìn)行比較，然后在下一輪比較時(shí)忽略已經(jīng)確定的位置，
如下：
[1, 3, 2]
1 比 1
1 比 3
1 比 2
大家是不是發(fā)現(xiàn)了一個(gè)無(wú)效操作？就是1和1比較，這就是一個(gè)無(wú)效操作，由于外部循環(huán)的i和內(nèi)部循環(huán)的j初始化會(huì)相等，所以arr[i]和arr[j]會(huì)取到同一個(gè)位置的值比較一次，那么怎么優(yōu)化這個(gè)操作呢？
答案就是讓內(nèi)部j從第二位開始，避免和arr[i]取同一個(gè)值的情況
for(let i = 0; i < len; i++){
for(let j = i; j < len - 1; j++){
if(arr[i] > arr[j+1]){
temp = arr[i];
arr[i] = arr[j+1];
arr[j+1] = temp;
}
}
}
注意我給內(nèi)部循環(huán)的len減去了1，是由于給j+1的會(huì)導(dǎo)致最后一次arr[j+1]會(huì)溢出數(shù)組，所以將其減1，正好彌補(bǔ)了j+1，也不會(huì)出現(xiàn)少遍歷數(shù)組元素的情況
然后我們來(lái)看看成果
[0, 1, 1, 1, 2, 2, 2, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 34, 43, 43, 44, 45, 51, 56, 62, 65, 76, 324] 561次
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/82602.html
摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩(wěn)定的排序算法。選擇排序思路選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類似插入排序，也分已排序區(qū)間和未排序區(qū)間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，...
摘要：多練練排序算法，不僅能夠讓我們知道一些排序方法的底層實(shí)現(xiàn)細(xì)節(jié)，更能夠鍛煉我們的思維，提升編程能力。排序算法的穩(wěn)定性一個(gè)穩(wěn)定的排序，指的是在排序之后，相同元素的前后順序不會(huì)被改變，反之就稱為不穩(wěn)定。 1. 導(dǎo)言 因?yàn)檫@是排序算法系列的第一篇文章，所以多啰嗦幾句。 排序是很常見(jiàn)的算法之一，現(xiàn)在很多編程語(yǔ)言都集成了一些排序算法，比如Java 的Arrays.sort()方法，這種方式讓我們可...
摘要：本文對(duì)一些排序算法進(jìn)行了簡(jiǎn)單分析，并給出了的代碼實(shí)現(xiàn)。平均時(shí)間復(fù)雜度不好分析，它是冒泡排序是穩(wěn)定的排序算法。冒泡排序是原地排序算法原地排序指的是空間復(fù)雜度是的排序算法。歸并排序，會(huì)將數(shù)組從中間分成左右兩部分。 本文對(duì)一些排序算法進(jìn)行了簡(jiǎn)單分析，并給出了 javascript 的代碼實(shí)現(xiàn)。因?yàn)楸疚陌舜罅康呐判蛩惴?，所以分析不?huì)非常詳細(xì)，適合有對(duì)排序算法有一定了解的同學(xué)。本文內(nèi)容其實(shí)不...
摘要：經(jīng)過(guò)一次冒泡排序，最終在無(wú)序表中找到一個(gè)最大值，第一次冒泡結(jié)束。也是我們后面要說(shuō)的冒泡排序的優(yōu)化。冒泡排序只執(zhí)行第一層循環(huán)，而不會(huì)執(zhí)行第二層循環(huán)。因此冒泡排序的時(shí)間復(fù)雜度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...
摘要：學(xué)堂碼匠本期繼續(xù)走入算法冒泡排序法。冒泡排序法完整代碼冒泡排序法的優(yōu)化假如序列的數(shù)據(jù)為使用上面的冒泡排序法進(jìn)行排序，得到的結(jié)果肯定沒(méi)有問(wèn)題，但是，待排序的序列是有序的，理論上是無(wú)需遍歷排序。 HTML5學(xué)堂-碼匠：本期繼續(xù)走入算法 —— 冒泡排序法。冒泡排序算法相對(duì)簡(jiǎn)單，容易上手，穩(wěn)定性也比較高,算是一種較好理解的算法，也是面試官高頻提問(wèn)的算法之一。 Tips：關(guān)于算法及排序的基礎(chǔ)知識(shí)...
閱讀 653·2021-11-25 09:43
閱讀 1926·2021-11-17 09:33
閱讀 839·2021-09-07 09:58
閱讀 2072·2021-08-16 10:52
閱讀 493·2019-08-30 15:52
閱讀 1735·2019-08-30 15:43
閱讀 1004·2019-08-30 15:43
閱讀 2938·2019-08-29 16:41
