浅谈PHP第二弹---经典算法的运用(冒泡排序和快速排序)

首先说说冒泡排序的思想,那很多同学会问什么是冒泡排序法呢?

下面我来解释下:

所谓的冒泡排序法,就是依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

咱们来看个例子:
有一个数组array(23,34,12,56,43,98,89),下面我们来使用冒泡排序法来对其元素进行排序.
$arr = Array(23,34,12,56,43,98,89);
for($i=0;$i for($j=0;$j if($arr[$j]>$arr[$j+1]){
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
}
}
}
?>

在上面的例子中,里面的for循环,是将本数组中的所有元素依次两两相比,也就是将数组中的第一个元素和第二个元素相比,第二个元素与第三个元素相比,
依此类推,直到数组的倒数第二个元素与最后一个元素相比,如果前面的元素大于后面的元素就让前面的元素与后面的元素位置交换,
那我们想,怎么让数组中的两个元素位置交换呢,
我们可以使用一个中间的容器变量来解决这个问题,
也就是将需要交换的第一个变量的值放入容器变量,然后将需要交换的第二个变量的值赋给第一个变量,再将容器变量中的值赋给第二个变量即可.

为了让大家更深刻的理解,请看下面的模拟图:

第一步:声明一个中间容器变量$tmp:

第二步:将$arr[$j]的值赋给$tmp

第三步:将$arr[$j+1]赋值给$arr[$j]

第四步:将中间变量的值赋给$arr[$j+1],完成交换

依次类推,一直到数组的倒数第二个元素与最后一个元素比较完成.总共比较count($arr)-1次
至此,我们数组的第一趟排序也就完成,此时数组中最大的数已经放到了数组的最后.也就是说,内层的for循环已经执行完成. www.2cto.com
接下来我们需要进行第二趟,第三趟....排序,每排一趟,出一个最大的数放在数组后面,只要排完,总共排count($arr)趟.
说到这里,大家是不是明白外层for循环的意思了呢!
好,我们思考一个问题,如果数组内的元素两两比较完,每比较一趟排出一个最大数,
那我们是不是在下趟比较的时候,不执行和上趟排出来的最大数的比较呢,
也就是说,第一趟排序完,98已经被放到了数组的最后,下趟排序就无需再把98拿来比较了,这样会提高效率,节省资源,
因此我们可以这样写:
$arr = Array(23,34,12,56,43,98,89);
for($i=0;$i for($j=0;$j if($j==count($arr)-1){
continue;
}
if($arr[$j]>$arr[$j+1]){
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
}
}
}
?>

上述代码中,内层循环执行次数变成了count($arr)-$i,
也就是说每趟把数组内的所有元素两两比较完之后,下趟再进行此排序时,排序的次数会减一,
也就是排除上一趟比较得出的最大的数的比较,这样一来,效率会提升不少,
我们可以使用php的内建函数microtime()在执行排序前执行一次,在排序后执行一次,将两次的时间相减,即得出运算时间,
通过比较可以得出冒泡排序的第二种排序方法的效率要高于第一种排序方法,但不是很明显,大家下来可以验证下,这里就不多讲了.

下面我们使用快速排序法对以上数组进行排序:
$arr = Array(23,34,12,56,43,98,89);
function quick($arr){
$left = array();
$right = array();
if(count($arr) return $arr;
}
for($i=1;$i if($arr[0]>$arr[$i]){
$left[] = $arr[$i];
}else{
$right[] = $arr[$i];
}
}
$left = quick($left);
$right = quick($right);
return array_merge($left,array($arr[0]),$right);
}
?>

所谓快速排序,就是在$arr数组中任意取一个值作为中间值,然后将这个值与数组内其他所有元素相比较,比这个值小的放到左边,比这个值大的放到这个值的右边, 此时完成一趟排序.以此类推,再将这个值左边的数进行上述排序,同样对右边的数进行上述排序.直到将所有的值都比较完.

我们来看上面的代码:
首先使用快速排序的理念就需要使用递归,说到递归,就是用函数自己调用自己,逐层深入,最后将拿到的值返回的思想.
下面我们来看,首先我们需要自定义一个函数quick(),让此函数自己调用自己.
这里中间值我们用$arr[0],这个是随意取的,不是必须的,
为了让大家思路清晰,我们先定义两个空数组,就相当于两个杯子,
让$arr[0]与数组内所有的值进行比较,比$arr[0]小的值放到第一个杯子中,比$arr[0]大的放到第二个杯子中,在程序中分别为$left和$right,
我们判断,如果给定的数组元素只有一个或为空,此数组将被quick函数返回,不再执行下面的内容,
接下来我们对数组进行遍历,并用遍历出来的值分别与$arr[0]进行比较,比$arr[0]小的值存入$left数组,比$arr[0]大的的值存入$right数组,此时完成一趟排序,
接下来再对$left数组和$right数组进行同样的操作,也就是调用函数自己,将$left数组和$right数组传入,直到$left数组或$right数组的数组元素为一个时,不再调用自己,直接返回,
最后将左边的数组,$arr[0],$right数组合并,即可得到最终的排序结果.

修正:
纠正效率方面的问题,在测试效率的时候,发生一个错误,导致效率测试不准确,经各位同学提醒,又一再测试,最终发现对此数组排序时运用快速排序的运算效率与冒泡排序的第二种相差不多,但是冒泡的第一种还是要比第二种明显的高一些,这个测试结果只能作为参考,要精确地算出每种算法的效率,需要对算法内部进行排序次数的统计.
再次感谢各位同学的关注,以及对于此问题的纠正,这是一个开放的平台,请大家畅所欲言,多多交流,共同进步...



摘自 zdrjlamp