# 冒泡排序 ## 定义： > 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 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)，看起来性能并不是很好，所以我们在实践中基本不会选用冒泡算法。