簡介
冒泡排序婿禽，將臨近的數(shù)字兩兩比較赏僧，按照大小順序進(jìn)行位置交換。
- 第一趟排序后扭倾，最大的數(shù)字（從小到大排序）或最小的數(shù)字（從大到小排序）被交換到最后一位淀零，也就是說最后一位被確定；
- 第二趟確定倒數(shù)第二位數(shù)字膛壹；
- 以此類推驾中，第三趟確定倒數(shù)第三位數(shù)字，第四趟確定倒數(shù)第4位數(shù)字模聋，第五趟...
講解
設(shè)示例數(shù)組為：[5,2,7,1,4,9,8]肩民，小->大排序；
- 第一趟排序
第一次：[5,2,7,1,4,9,8]中5與2比較链方，5>2所以交換位置持痰，數(shù)組變作為-->[2,5,7,1,4,9,8]；
第二次：[2,5,7,1,4,9,8]中5與7比較祟蚀，5<7所以不交換位置工窍，數(shù)組變作為-->[2,5,7,1,4,9,8]占调；
第三次：[2,5,7,1,4,9,8]中7與1比較，7>1所以交換位置移剪，數(shù)組變作為-->[2,5,1,7,4,9,8]；
第四次：[2,5,1,7,4,9,8]中7與4比較薪者，7>4所以交換位置纵苛，數(shù)組變作為-->[2,5,1,4,7,9,8]；
第五次：[2,5,1,4,7,9,8]中7與9比較言津，7<9所以不交換位置攻人，數(shù)組變作為-->[2,5,1,4,7,9,8]；
第六次：[2,5,1,4,7,9,8]中9與8比較悬槽，9>8所以交換位置怀吻，數(shù)組變作為-->[2,5,1,4,7,8,9]；此時最大的數(shù)字9已經(jīng)到了末尾初婆。
第二趟排序
第一次：[2,5,1,4,7,8,9]中2與5比較蓬坡，2<5所以不交換位置，數(shù)組變作為-->[2,5,1,4,7,8,9]磅叛；
第二次：[2,5,1,4,7,8,9]中5與1比較屑咳，5>1所以交換位置，數(shù)組變作為-->[2,1,5,4,7,8,9]弊琴；
第三次：[2,1,4,5,7,8,9]兆龙；
第四次：[2,1,4,5,7,8,9]；
第五次：[2,1,4,5,7,8,9]敲董；這里不需要第六次比較紫皇，因?yàn)樽詈笠粋€數(shù)已知是最大的，不需要再進(jìn)行比較腋寨。同理第三趟不需要第五次比較聪铺，第四趟不需要第四次比較...
之后演示已無必要，喲喲切克鬧精置，咳咳...
我們可以發(fā)現(xiàn)计寇，該算法的復(fù)雜度為：(n-1)+(n-2)+...+2+1=n(n-1)/2
演示代碼
//從小到大排序
function bubbleSort(array){
var tem = 0;
for (var i = 0; i < array.length; i++) {
for (var j = 0; j < array.length-i; j++) {
if(array[j]>array[j+1]){
tem = array[j];
array[j] = array[j+1];
array[j+1] = tem;
}
}
}
}
window.onload=function(){
var array = [2,3,1,4,9,7,5];
bubbleSort(array);
console.log(array);
}
補(bǔ)充一：最近聽見很多同學(xué)在說冒泡排序的復(fù)雜度為n的平方，百度一看似乎蠻多人也是這樣認(rèn)為的脂倦，看到的同學(xué)難免會有些為難究竟哪一個復(fù)雜度是正確的番宁。
事實(shí)上，兩者都是正確的赖阻，n(n-1)/2是比較精確蝶押，而n^2則是表示該算法復(fù)雜度的數(shù)量級。
n(n-1)/2 --->
(n^2-n)/2 --->
當(dāng)n足夠大時火欧，-n的影響很小棋电，而為了表示數(shù)量級n^2的系數(shù)1/2也去掉 --->
那么現(xiàn)在復(fù)雜度就是n^2了
