• 售前

  • 售后

热门帖子
入门百科

PHP排序算法之冒泡排序(Bubble Sort)实现方法详解

[复制链接]
球死禁严 显示全部楼层 发表于 2021-10-25 19:30:19 |阅读模式 打印 上一主题 下一主题
本文实例报告了PHP排序算法之冒泡排序(Bubble Sort)实现方法。分享给各人供各人参考,详细如下:
根本思想:
冒泡排序是一种交换排序,它的根本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。
最简朴排序实现:
我们先来看看在没有学习各种排序方法前经常使用的排序方法(至少我是如许。。。。):
  1. //这里使用了类型提示(type hint) array,不熟悉或者不习惯的同学大可去掉,不影响运算结果
  2. function MySort(array &$arr){
  3.   $length = count($arr);
  4.   for($i = 0;$i < $length - 1;$i ++){
  5.     for($j = $i + 1;$j < $length;$j ++){
  6.       //将小的关键字放前面
  7.       if($arr[$i] > $arr[$j]){
  8.         $temp = $arr[$i];
  9.         $arr[$i] = $arr[$j];
  10.         $arr[$j] = $temp;
  11.       }
  12.     }
  13.   }
  14. }
  15. $arr = array(9,1,5,8,3,7,4,6,2);
  16. MySort($arr);
  17. print_r($arr);
复制代码
上面的这段代码严酷意义上说,不算是尺度的冒泡排序,由于它不满足“两两比较相邻记录”的冒泡排序思想,它仅仅是一个简朴的交换排序。思绪不过是:从第一个关键字开始,将每一位关键字与它背面的所有关键字相比较,交换得到其中的最小值。但这个算法黑白常低效的。
冒泡排序算法:
它重复地走访过要排序的数列,一次比较两个元素,如果他们的次序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
这个算法的名字由来是由于数组中越大的元素会由于一次次排序后徐徐“沉”到数组的背面,而越小的元素会徐徐“浮”到数组的前面,故名。
冒泡排序算法的运作如下:(从后往前)
1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2.对每一对相邻元素作同样的工作,从开始第一对到末了的最后一对。在这一点,最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步调,除了最后一个。
4.连续每次对越来越少的元素重复上面的步调,直到没有任何一对数字需要比较。
看笔墨描述不肯定看得懂,看代码吧:
  1. //交换方法
  2. function swap(array &$arr,$a,$b){
  3.   $temp = $arr[$a];
  4.   $arr[$a] = $arr[$b];
  5.   $arr[$b] = $temp;
  6. }
  7. //冒泡排序
  8. function BubbleSort(array &$arr){
  9.   $length = count($arr);
  10.   for($i = 0;$i < $length - 1;$i ++){
  11.     //从后往前逐层上浮小的元素
  12.     for($j = $length - 2;$j >= $i;$j --){
  13.       //两两比较相邻记录
  14.       if($arr[$j] > $arr[$j + 1]){
  15.         swap($arr,$j,$j+1);
  16.       }
  17.     }
  18.   }
  19. }
复制代码
冒泡排序算法改进:
《大话数据布局》果然是本好书,还给我们先容了冒泡排序算法的改进,这里我就直接搬它的报告:
  1. 上面的冒泡排序算法是否还可以优化呢?答案是肯定的。试想一下,如果我们待排序的序列是{2,1,3,4,5,6,7,8,9},也就是说,除了第一和第二个关键字需要交换外,别的都已经是正常的顺序了。当 i = 0 时,交换了 2 和 1 ,此时的序列已经是有序的了,但是算法仍然不依不挠地将 i = 2 到 9 以及每个循环中的 j 循环都执行了一遍,尽管并没有交换数据,但是之后的大量比较还是大大地多余了。
  2. 当 i = 2 时,我们已经对 9 与 8,8 与 7,·······,3 与 2 做了比较,没有任何数据交换,这就说明此序列已经有序,不需要再继续后面的循判断工作了(后面的工作也是不会发生任何数据交换,再做也是没有意义了)。为了实现这个想法,我们需要改进一下代码,增加一个标记变量 flag 来实现这一算法的改进:
复制代码
  1. //交换方法
  2. function swap(array &$arr,$a,$b){
  3.   $temp = $arr[$a];
  4.   $arr[$a] = $arr[$b];
  5.   $arr[$b] = $temp;
  6. }
  7. /冒泡排序的优化(如果某一次循环的时候没有发生元素的交换,则整个数组已经是有序的了)
  8. function BubbleSort1(array &$arr){
  9.   $length = count($arr);
  10.   $flag = TRUE;
  11.   for($i = 0;($i < $length - 1) && $flag;$i ++){
  12.     $flag = FALSE;
  13.     for($j = $length - 2;$j >= $i;$j --){
  14.       if($arr[$j] > $arr[$j + 1]){
  15.         swap($arr,$j,$j+1);
  16.         $flag = TRUE;
  17.       }
  18.     }
  19.   }
  20. }
复制代码
代码改动的关键就是在 i 变量的for循环中,增加了对flag是否为 true 的判定,经过如许的改进,冒泡排序在性能上就有了一些提拔,可以制止因已经有序的情况下的无意义循环判定。
冒泡算法总的时间复杂度是 O(n^2)
冒泡排序是稳定排序。
本文参考自《大话数据布局》,在此仅作记录,方便以后查阅,大神勿喷!
PS:这里再为各人推荐一款关于排序的演示工具供各人参考:
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys
更多关于PHP相干内容感爱好的读者可检察本站专题:《php排序算法总结》、《PHP数据布局与算法教程》、《php步伐计划算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)利用本领大全》、《PHP常用遍历算法与本领总结》及《PHP数学运算本领总结》
盼望本文所述对各人PHP步伐计划有所资助。

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作