介紹
冒泡排序執(zhí)行步驟（以升序為例读规，并假設(shè)有n個待排序數(shù)）：
1.對比前兩個數(shù)據(jù)丁频，如果第1個比第2個大則交換位置杉允，否則原封不動；
2.接著對比第2限府、3個數(shù)夺颤，按照第1個步驟執(zhí)行；
3.按第1個步驟一直到對比第n-1和第n和位置胁勺，此時第n個就是最大的數(shù)世澜；
4.將剩下的n-1個數(shù)按照上面的步驟執(zhí)行，得到第二大的數(shù)署穗；
5.以此類推直到對比完最后剩下的兩個數(shù)即可寥裂；
圖示：
冒泡排序
例子
假設(shè)有一個待排序數(shù)組[77, 6, 37, 96, 34, 6, 14], js實現(xiàn)如下(升序)：
function sort( arr ){
var result = [];
var len = arr.length - 1;
for(var i = 0; i< len; i++){
for(var j = 0; j < len- i; j ++ ){
if(!arr[j + 1]) continue;
if(arr[j + 1] < arr[j]){ // 交換位置
var med = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = med;
}
}
}
return arr;
}
sort([77, 6, 37, 96, 34, 6, 14]); // =>[6, 6, 14, 34, 37, 77, 96]
時間復(fù)雜度
可以看到運遍歷次數(shù)為：(n-1) + (n-2) + (n-3) + ... + 1 = (n^2 - n)/2, 按照大O階推導(dǎo)方法得時間復(fù)雜度為 O(n^2)
感謝閱讀！歡迎關(guān)注案疲！持續(xù)更新中...
