php算法优化
这里总结一下冒泡排序算法的方式
冒泡排序最简单的实现方式如下(我用PHP来实现,用其他语言也是一样的)：
生成1w的随机数
1
2
3
4
5
6
set_time_limit(0);
$arr = [];
for ($k = 0; $k < 10000; $k++) {
$arr[] = $k;
}
shuffle($arr);
冒泡排序这个经典的算法
1
2
3
4
5
6
7
8
9
10
11
12
function bubble($value = []){
$len = count($value);
for ($i=0; $i < $len; $i++) {
for ($j=0; $j < $len-$i-1; $j++) {
if($value[$j]>$value[$j+1]){
$tmp = $value[$j+1];
$value[$j+1] = $value[$j];
$value[$j] = $tmp;
}
}
}
}
一 通过上面的代码，会发现，数组其实在第一轮排序后就已经将数组排序好了。后面的几轮排序其实都是无用功。也就是说下面的代码白白走了$len-1遍，一点作用都没发生。
白白执行$len-1遍的代码中，每一遍都能在(n-1)的数据比较，如果数组的长度n极大，这个消耗还是很严重的。所以我们首先要解决一下这个问题，怎么才能不造成无谓的数据比较的资源浪费。
优化策略:在程序中添加标识，用于记录每次外循环过程中，是否发生了数据的交换。如果没有发生数据的交换，就意味者在上一轮的外循环过程中，数据已经排序完成，不需要继续循环比较数据了，我们直接break掉就可以了。如果还存在这数据的交换，就意味着在之前的外部循环中，数据还没有排序好，这一轮排序操作或者接下来的排序操作才可以完成排序工作，我们还需要进行下一轮的排序来完成排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
$len = count($value);
for($i=0;$i<$len;$i++){
//设置flag变量，用来记录数据是否交换完成
$flag = true;
for($j=0;$j<$len-1;$j++){
if($value[$j] > $value[$j+1]){
//进行交换
$temp = $value[$j];
$value[$j] = $value[$j+1];
$value[$j+1] = $temp;
$flag = false;
}
}
if($flag){
break;
}
}
其实，在进行数据排序的过程中，随着排序的进行，数据逐渐从无序变为有序，出现上面情况的可能性会逐步的增高的。
二
好了，说完上面的问题，咱们再来看下面的问题。当冒泡排序的外部循环每执行一次，就会将最大值(最小值)交换到数组的最前端或者数组的最后端
依此类推，我们可以发现，每一轮循环完毕，都能求出某个位置上的应有的数据，并且完成交换。那么也就是说数组的左部(右部)逐渐变得有序，且有序部分的长度等于外部循环进行的轮数。既然数组的左部(右部)逐渐变得有序，那么每次循环过程中，我们就不需要再比较数组的左部(右部)的有序的部分了。
优化策略:新增一个变量来记录某次外部循环过程中最后发生的数据交换的位置。使用上面记录的位置来作为下一次外部循环中的内部循环的终止条件，这样就能减少不必要数据比较过程。代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
$len = count($value);
$last_pos = $len; //记录每一次外部循环过程中，最后进行数据交换的位置
$next_pos = $len; //记录每一次数据交换的位置
for($i=0;$i<$len;$i++){
for($j=0;$j<$last_pos-1;$j++){
if($value[$j] > $value[$j+1]){
//进行交换
$temp = $value[$j];
$value[$j] = $value[$j+1];
$value[$j+1] = $temp;
$next_pos = $j+1;
}
}
//如果该轮循环得到的最后的数据交换位置等于上一轮循环得到的数据交换的位置，就意味着数组全部有序了
if($last_pos == $next_pos){
break;
}else{//如果没有全部有序，就将last_pos设置为next_pos
$last_pos = $next_pos;
}
}
三
解决了上面的问题，我们还能不能进一步的提高冒泡算法的排序速度嘛？答案是可以的。我们可以采用双向排序的方式，进一步加快排序的速度。
第一次循环过程，计算出最大值并将该值移动到数组最右边，计算出最小值并将该值移动到数组的最左边。第二次循环过程中，计算出第二大的值并将数据移动到数组右边第二个的位置，计算出第二小的值并将数据移动到数组左边第二个的位置。也会说在一次双向排序循环过程中，求出数组左边以及数组右边各个位置响应的元素，并且移动到响应的位置。
具体的实现代码如下:
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
$len = count($value);
$index = 0; //从左到右排序过程中起始的位置
$first_pos = 0; //从右到左排序过程中最后进行数据交换的位置
$up = $len-1; //从左到右排序过程中结束的位置
$last_pos = $up; //从左到右排序过程中最后进行数据交换的位置
while($up >= $index){
//从头开始扫描
for($i=$index;$i<$up;$i++){
if($value[$i]>$value[$i+1]){
//进行交换
$temp = $value[$i];
$value[$i] = $value[$i+1];
$value[$i+1] = $temp;
$last_pos = $i;
}
}
if($up == $last_pos){
break;
}
$up = $last_pos;
//从尾部开始扫描
for($j=$up;$j>1;$j--){
if($value[$j-1]>$value[$j]){
//进行交换
$temp = $rand_arr[$j];
$value[$j] = $value[$j-1];
$value[$j-1] = $temp;
$first_pos = $j;
}
}
if($index == $first_pos){
break;
}
$index = $first_pos;
}
