PHP 冒泡排序由浅到深

冒泡排序算是最简单的排序算法了,但是深入研究的话,还是能学到不少东西。

冒泡排序 ( 交换排序 )

冒泡算法的基本思想 : 两两比较相邻记录值, 如果反序则交换, 直到没有反序之外

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) {
# 这里需要使用 `===` 来进行严格判断, 以免传入类似 null 等空元素产生安全隐患
if (1 === $type) {
if ($arr[$i] < $arr[$j]) {swap($arr[$i], $arr[$j]);}
} else {
# 如果 $type 没指定值或者指定其他值都按 $type = 0 进行默认处理
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) {
# 这里因为第一位至少得比较一次, 所以必须 $j>=$i 否则第一个元素无法被遍历到
# 为了形象, 模拟出冒泡的动作, 这里从尾部开始遍历, 表达最小或最大元素从最底部逐渐上浮到 `水面` 的感觉
# 这里的写法不唯一, 只要能遍历到每个元素然后体现相邻两个元素交换就行了, 向前和向后其实是一样的
for ($j=$len-2; $j>=$i; --$j) {
# 这里需要使用 `===` 来进行严格判断, 以免传入类似 null 等空元素产生安全隐患
if (1 === $type) {
if ($arr[$j+1] > $arr[$j]) { swap($arr[$j+1], $arr[$j]);}
} else {
# 如果 $type 没指定值或者指定其他值都按 $type = 0 进行默认处理
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
/**
* 本算法解决的是当对诸如 2,1,3,4,5,6,7,8,9 这种基本认为有序的数列进行排序的时候, 第 2 种算法在已经排好顺序后还是会去做多余的判断带来的效率降低问题
* 优化的基本思路是:
* 已经有序的数字之间无需再次排序; 尽量利用已经有序的部分数列
* 如果在外层循环的一次完整遍历中都没有发生过一次交换则认为已经排序完成退出排序, 而如果发生交换过则证明序列还没有成为我们期望的顺序而需要继续排序
* 如果序列已经完全有序但是和想要的顺序刚好相反, 则此时可以先通过判断是否是这种情况然后使用 array_reverse() 翻转序列即可, 这样在 n 很大的情况下时间复杂度只有 O(1)
* 本算法的时间复杂度是: 最好情况( 要排的序列自身可以认为有序 )下 O(1) 或者 O(n); 最坏情况下 O(n^2)
* 分析算法的技巧在于: 可以通过分析几个情况推广到一般情况而不是把每种情况都验证一遍
* @param $arr
* @param int $type 排序的类型: 0 为 从小到大 ( 默认 ) ; 1 为 从大到小
* @return bool|int
*/
function bubble_sort3(&$arr, $type = 0) {
if (!number_check($arr)) { return false; }

$len = count($arr);

# 如果数组中的数字本身有序则不用进行冒泡排序, 要么返回原数组, 要么返回原数组的翻转数组
# 如果 $type = 1 且数组本身也是从大到小 ( $is_order = 1 ) , 则直接返回 1
# 如果 $type = 1 且数组本身是从小到大 ( $is_order = 2 ) , 则翻转数组后返回 2
# 如果 $type = 0 且数组本身也是从小到大, 则直接返回 3
# 如果 $type = 0 且数组本身是从大到小, 则翻转数组后返回 4
$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 代表本数列还没有排序好, 如果为 false 则代表本数列已经排序好无需再排, 然后退出外层循环
$flag = true;

# 写法不唯一但是必须注意外层循环和内层循环的数组越界问题
for ($i=0; $i<$len && $flag; ++$i) {
# 乐观地认为该序列已经有序无需再排, 这是最好的情况, 如果真是这样则跳出外循环, 这样可以避免最好情况下的无意义比较
$flag = false;

# 这里因为第一位至少得比较一次, 所以必须 $j>=$i 否则第一个元素无法被遍历到
# 为了形象, 模拟出冒泡的动作, 这里从尾部开始遍历, 表达最小或最大元素从最底部逐渐上浮到 `水面` 的感觉
# 这里的写法不唯一, 只要能遍历到每个元素然后体现相邻两个元素交换就行了, 向前和向后其实是一样的
for ($j=$len-2; $j>=$i; --$j) {
# 这里需要使用 `===` 来进行严格判断, 以免传入类似 null 等空元素产生安全隐患
if (1 === $type) {
if ($arr[$j+1] > $arr[$j]) { swap($arr[$j+1], $arr[$j]);}
$flag = true;
} else {
# 如果 $type 没指定值或者指定其他值都按 $type = 0 进行默认处理
if ($arr[$j+1] < $arr[$j]) { swap($arr[$j+1], $arr[$j]);}
$flag = true;
}
}
}

return 0;
}

辅助函数

  • number_check()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 对输入的参数进行检查, 不能为非数组, 也不能为非数字
* @param $arr
* @return bool
*/
function number_check( &$arr ) {
if (!is_array($arr)) {
return false;
} else {
foreach ($arr as $val) {
if (!is_numeric($val)) {return false;}
}
}

return true;
}
  • swap()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 交换 2 个数字
* @param $a
* @param $b
* @return bool
*/
function swap(&$a, &$b) {
if (is_numeric($a) && is_numeric($b)) {
$a = $a + $b;
$b = $a - $b;
$a = $a - $b;
} else {
return false;
}
}
  • is_ordered()
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 )

Powered by Hexo and Hexo-theme-hiker

Copyright © 2017 - 2022 Keep It Simple And Stupid All Rights Reserved.

访客数 : | 访问量 :