常见的排序算法有:冒泡排序,快速排序,选择排序,插入排序,本文对冒泡排序做了一个总结。
思路分析
想象一个大水池里有N多还未排好的序列的氢气球,较大的先冒出来,然后依次是较小的往上冒。即,每次比较相邻的两个数,小的在前大的在后,否则进行位置互换。
/** * 交换方法 * @param array $arr 目标数组 * @param $a 索引a * @param $b 索引b * @param bool $flag 交换标志 * @return bool */ function swap(array &$arr,$a,$b,$flag = false){ // 遍历i后面的元素,只要该元素小于当前元素,就把较小的往前冒泡 if($arr[$a] > $arr[$b]){ $temp = $arr[$a]; $arr[$a] = $arr[$b]; $arr[$b] = $temp; $flag = true; } return $flag; } /** * 第一种写法 * @param $arr 所要排序的数组 * @return mixed 返回的数组 */ function bubbleSort($arr) { $len = count($arr); if ($len <= 1) {return $arr;} //该层循环控制 需要冒泡的轮数 for ($i = 0; $i < $len-1; $i++) { //该层循环用来控制每轮 冒出一个数 需要比较的次数 for ($j = $i + 1; $j < $len; $j++) { // 或者 $this->swap($arr,$j,$j+1); $this->swap($arr,$i,$j); } } return $arr; } //第二种写法 public function BubbleSort2($arr){ $len = count($arr); if ($len <= 1) {return $arr;} for ($i = 0;$i < $len-1;$i++){ //TODO 本趟排序开始前,交换标志应为假 $flag = false; for ($j = 0;$j <= $len-2;$j++){ $flag = $this->swap($arr,$j,$j+1,$flag); } if(!$flag) return $arr; } return $arr; } //第三种写法 function BubbleSort3(array &$arr){ $len = count($arr); if ($len <= 1) {return $arr;} for($i = 0;$i < $len-1;$i++){ //从后往前逐层上浮小的元素 $j >= 0 for($j = $len - 2;$j >= $i ;$j --){ $this->swap($arr,$j,$j+1); } } return $arr; } //第四种写法 function bubbleSort4($arr) { $len = count($arr); if ($len <= 1) {return $arr;} for($i = 0;$i < $len-1;$i++) { for($j = 0;$j < $len-$i-1;$j++) { $this->swap($arr,$j,$j+1); } } return $arr; }
小结:
时间复杂度:O(n^2)
空间复杂度:O(1)
补充:可使用PHP内置函数 sort()或rsort().
上述函数对索引数组按照键值进行排序,为 array 中的单元赋予新的键名,这将删除原有的键名而不仅是重新排序。如果成功则返回 TRUE,否则返回 FALSE
冒泡排序属于稳定排序
登录后可发表评论