冒泡排序（Bubble Sort）晚胡，是一種計算機(jī)科學(xué)領(lǐng)域的較簡單的排序算法西潘。
它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素侧戴，如果他們的順序錯誤就把他們交換過來宁昭。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成酗宋。
這個算法的名字由來是因為越大的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端积仗，故名。
以上我是百度搜的 本缠，具體內(nèi)容可以看書斥扛，閑來看精華
圖中有三個變量 Outer 代表了每次我們要觀察的位置入问，可以看到Outer 右側(cè)的數(shù)據(jù)是已經(jīng)是最大的丹锹，有序的，所以我們的每次循環(huán)到Outer就可截至芬失，多余的比較是無用的楣黍。
Inner是每次循環(huán)比較的指針，Inner+1 比較過后棱烂，如果Inner > Inner+1 就做交換租漂，否則就移動Inner
原書是用java寫的 ，這里我用我喜歡的Swift重新寫一份
func bubbleSort<T:Comparable>( aArr:[T]) -> [T] {
var arr = aArr
for outerIndex in (1...arr.count - 1).reverse() { // 從最外層開始
for innerIndex in 0..<outerIndex {
if arr[innerIndex] > arr[innerIndex + 1] {
let temp = arr[innerIndex]
arr[innerIndex] = arr[innerIndex + 1]
arr[innerIndex + 1] = temp
}
}
}
return arr
}
//冒泡排序的時間復(fù)雜度為O ( n2 )。
print(bubbleSort([9,8,7,6,5,4,3,2,1,0]))
先說明下算法的效率
在算法的效率中 最好的效率到最差的順序為 O(1) , O(log(N)) , O(N),O(N2)哩治。
看圖可知
對于冒泡排序的效率秃踩，我們假定數(shù)組長N ，并且恰好我們的數(shù)組是逆序的业筏，我們第一次排序的比較次數(shù)為N -1 第二次為N-2 憔杨，第三次N-3 ,一次類推，這個排序的比較次數(shù)之和為 （N-1）+ (N-2)+(N-3) = N(N-1)2 蒜胖。
在觀察算法的效率時我們一般忽略掉常數(shù)消别，所以算法的比較次數(shù)為N*N次 也就是 O(N2)
冒泡算法的交換效率，假定我們的數(shù)組是逆序的台谢，每次比較都需要交換寻狂，所以算法的交換也需要O(N2)
補充說明
對于只要有嵌套循環(huán)的操作，我們就要懷疑這個算法的效率為O(N2) 朋沮，外層循環(huán)執(zhí)行N次 蛇券，內(nèi)層循環(huán)往往執(zhí)行少于N次，但是我們觀察一個算法時會忽略掉常數(shù)朽们，往往觀察出來就是O(N2) 怀读。
由圖可以看到冒泡算法效率很差，但是其算法比較簡單骑脱，在學(xué)習(xí)算法基礎(chǔ)非常適合入門使用菜枷，而且由于現(xiàn)在計算機(jī)的發(fā)達(dá)，很小的數(shù)據(jù)量叁丧，對于冒泡算法時間消耗也是可以容忍的啤誊，
繼續(xù)奮斗中，加油
