冒泡排序算是最简单的排序算法了,但是深入研究的话,还是能学到不少东西。
冒泡排序 ( 交换排序 )
冒泡算法的基本思想 : 两两比较相邻记录值, 如果反序则交换, 直到没有反序之外
1. 最简单的交换排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| /** * 本函数是最简单的一种交换排序, 严格的说并不算标准的冒泡排序, 其实现思路: * 外层循环第 1 次遍历结束的时候找到所有数字中最小( 或最大 )的放到第 1 位 * 外层循环第 2 次遍历结束的时候找到所有数字中第 2 小( 或第 2 大 )的放到第 2 位 * 外层循环第 3 次遍历结束的时候找到所有数字中第 3 小( 或第 3 大 )的放到第 3 位 * 以此类推, 当外层循环第 n 次遍历结束的时候找到所有数字中第 n 小, 即最大( 或第 n 大, 即最小 )的放到第 n 位 * 本算法的时间复杂度是: O(n^2); * 由于排序过程中已排序好的序列对剩余序列的排序没有任何帮助, 所以其效率比较低下 * @param Array &$arr, 必须传入一个数组类型 * @param int $type * @return bool|int */ function bubble_sort1(&$arr, $type = 0) { if (!number_check($arr)) { return false; }
$len = count($arr);
for ($i = 0; $i < $len; ++$i) { for ($j = $i+1; $j < $len; ++$j) { if (1 === $type) { if ($arr[$i] < $arr[$j]) {swap($arr[$i], $arr[$j]);} } else { if ($arr[$i] > $arr[$j]) {swap($arr[$i], $arr[$j]);} } } }
return 1; }
|
2. 标准冒泡排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| /** * 本函数是正宗的冒泡排序算法, 其基本实现思路是: * 外层循环的下标所对应的值总是代表本次外循环总最小或最大的数 * 内层循环总是从数组中最后一个数依次向前和相邻数比较, 根据所需顺序决定是否需要交换两者的值 * 外层循环第 1 次遍历结束的时候所有数字中最小( 或最大 )的数浮到第 1 位 * 外层循环第 2 次遍历结束的时候所有数字中第 2 小( 或第 2 大 )的数浮到第 2 位 * 外层循环第 3 次遍历结束的时候所有数字中第 3 小( 或第 3 大 )的数浮到第 3 位 * 以此类推, 当外层循环第 n 次遍历结束的时候所有数字中第 n 小, 即最大( 或第 n 大, 即最小 )的数位于第 n 位 * 本算法的时间复杂度是: O(n^2) * @param $arr * @param int $type 排序的类型: 0 为 从小到大 ( 默认 ) ; 1 为 从大到小 * @return bool|int */ function bubble_sort2(&$arr, $type = 0) { if (!number_check($arr)) { return false; }
$len = count($arr);
for ($i=0; $i<$len; ++$i) { for ($j=$len-2; $j>=$i; --$j) { if (1 === $type) { if ($arr[$j+1] > $arr[$j]) { swap($arr[$j+1], $arr[$j]);} } else { if ($arr[$j+1] < $arr[$j]) { swap($arr[$j+1], $arr[$j]);} } } }
return 1; }
|
3. 优化后的冒泡排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
|
function bubble_sort3(&$arr, $type = 0) { if (!number_check($arr)) { return false; }
$len = count($arr);
$is_order = is_ordered($arr, $len, $type); switch ($is_order) { case 1: if ($type == 1) { return 1; } else { array_reverse($arr); return 2; } break; case 2: if ($type == 1) { array_reverse($arr); return 3; } else { return 4; } default: break; }
$flag = true;
for ($i=0; $i<$len && $flag; ++$i) { $flag = false;
for ($j=$len-2; $j>=$i; --$j) { if (1 === $type) { if ($arr[$j+1] > $arr[$j]) { swap($arr[$j+1], $arr[$j]);} $flag = true; } else { if ($arr[$j+1] < $arr[$j]) { swap($arr[$j+1], $arr[$j]);} $flag = true; } } }
return 0; }
|
辅助函数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
function number_check( &$arr ) { if (!is_array($arr)) { return false; } else { foreach ($arr as $val) { if (!is_numeric($val)) {return false;} } }
return true; }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
|
function swap(&$a, &$b) { if (is_numeric($a) && is_numeric($b)) { $a = $a + $b; $b = $a - $b; $a = $a - $b; } else { return false; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| /** * 判断数组中的数字序列是否是已经有序这种特殊情况 * 注意输入参数检查, 这里调用者已经检查过了所以这里不再进行检查 * @param $arr * @param $len: 这里直接传过来不用再多一次计算 * @param int $type 升序或者降序 - 0 代表从小到大( 默认 ) ; 1 代表从大到小 * @return int 为 0 代表序列无序; 为 1 代表已经是 从大到小 的顺序; 为 2 代表已经是 从小到大 的顺序 */ function is_ordered(&$arr, $len, $type = 0) { $status = 0; for ($i=0; $i<$len-1; ++$i) { if (1 === $type) { if (($arr[$i] >= $arr[$i+1]) && (++$status == $len-1)) { return 1; } } else { if (($arr[$i] <= $arr[$i+1]) && (++$status == $len-1)) { return 2; } } }
return 0; }
|
注意事项
引用传递不要在调用函数时声明 &
而是在函数形式参数列表中指明 &
。即:
1 2 3 4 5 6 7 8 9 10 11
| function func( &$var ) { // do something }
$var = array()
# 错误的写法 func( &$var ) ;
# 正确的写法 func( $var )
|