现在的位置: 主页 > 新闻中心 > 文章正文

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

作者:成都昌德装饰工程有限公司 来源:www.cdchangde.com 发布时间:2017-09-07 12:50:32
浅谈PHP第二弹---经典算法的运用(冒泡排序和快速排序)

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


下面我来解释下:

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


咱们来看个例子:
有一个数组array(23,34,12,56,43,98,89),下面我们来使用冒泡排序法来对其元素进行排序.
<?php
$arr = Array(23,34,12,56,43,98,89);
for($i=0;$i<count($arr);$i++){
for($j=0;$j<count($arr)-1;$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循环已经执行完成.
接下来我们需要进行第二趟,第三趟....排序,每排一趟,出一个最大的数放在数组后面,只要排完,总共排count($arr)趟.
说到这里,大家是不是明白外层for循环的意思了呢!
好,我们思考一个问题,如果数组内的元素两两比较完,每比较一趟排出一个最大数,
那我们是不是在下趟比较的时候,不执行和上趟排出来的最大数的比较呢,
也就是说,第一趟排序完,98已经被放到了数组的最后,下趟排序就无需再把98拿来比较了,这样会提高效率,节省资源,
因此我们可以这样写:
<?php
$arr = Array(23,34,12,56,43,98,89);
for($i=0;$i<count($arr);$i++){
for($j=0;$j<count($arr)-$i;$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()在执行排序前执行一次,在排序后执行一次,将两次的时间相减,即得出运算时间,
通过比较可以得出冒泡排序的第二种排序方法的效率要高于第一种排序方法,但不是很明显,大家下来可以验证下,这里就不多讲了.

下面我们使用快速排序法对以上数组进行排序:
<?php
$arr = Array(23,34,12,56,43,98,89);
function quick($arr){
$left = array();
$right = array();
if(count($arr)<=1){
return $arr;
}
for($i=1;$i<count($arr);$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数组中任意取一个值作为中间值,然后将这个值与数组内其他所有元素相比较,比这个值小的放到左边,比这个值大的放到这个值的右边, 此时完成一趟排序.以此类推,再将这个值左边的数进行上述排序,同样对右边的数进行上述排序.直到将所有的值都比较完.

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉网站建设 https://www.feimao666.com

上一篇:安全套的安全不是互联网思维,营销才是 下一篇:最后一页