# 冒泡排序 ## 定義： > 冒泡排序只會操作相鄰的兩個數據。每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關系要求，如果不滿足就讓它倆互換。一次冒泡會讓至少一個元素移動到它應該在的位置，重復 n 次，就完成了 n 個數據的排序工作。 第一次排序流程：  所謂冒泡，以升序來看，就是每次把待排序序列中的最大值插到已排序序列的最前面，這個過程就像冒泡一樣：  ## 代碼實現： ~~~ /** * @param $nums * @return mixed * 4 3 2 1 */ function bubble_sort($nums){ if(count($nums) <= 1){ return $nums; } for($i=0;$i<count($nums);$i++){//控制比較的次數，比較的次數與數組長度有關 $flag = true;//如果為true就表示數組元素位置沒有發生改變，用來控制判斷數組是否排好了序，這樣可以少比較 for($j=0;$j<count($nums)-$i-1;$j++){//控制比較的次數，第一次比較3次，第二次比較2次，第三次比較1次，第四次比較0次 if($nums[$j]>$nums[$j+1]){ $temps = $nums[$j]; $temps[$j] = $nums[$j+1]; $nums[$j+1] = $temps; $flag = false; } } if($flag){ return $a; return $nums; } } return $nums; } $nums = [1,2,3,4]; print_r(bubble_sort($nums)); ~~~ ## 冒泡排序的性能和穩定性 1. 時間復雜度： O(n^2) （n的平方） 2. 空間復雜度：只涉及相鄰元素的交換，是原地排序算法 3. 算法穩定性：元素相等不會交換，是穩定的排序算法 ## 總結： 時間復雜度是 O(n^2)，看起來性能并不是很好，所以我們在實踐中基本不會選用冒泡算法。