• 售前

  • 售后

热门帖子
入门百科

PHP四种排序算法实现及效率分析【冒泡排序,插入排序,选择排序和快速排序】

[复制链接]
Besson 显示全部楼层 发表于 2021-10-25 20:16:17 |阅读模式 打印 上一主题 下一主题
本文实例报告了PHP四种排序算法实现及服从分析。分享给各人供各人参考,具体如下:
PHP的四种根本排序算法为:冒泡排序、插入排序、选择排序和快速排序。
下面是我整理出来的算法代码:
1. 冒泡排序:
思路:对数组进行多轮冒泡,每一轮对数组中的元素两两比力,调整位置,冒出一个最大的数来。
  1. //简单版:
  2. function bubbleSort($arr)
  3. {
  4.    $n = count($arr);
  5.    for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮)
  6.      for($j=0;$j<$n-1;$j++) { //每一轮冒泡(两两比较,大者后移)
  7.        if($arr[$j] > $arr[$j+1]) { //前者大于后者,交换位置
  8.           $tmp = $arr[$j];
  9.           $arr[$j] = $arr[$j+1];
  10.           $arr[$j+1] = $tmp;
  11.        }
  12.      }
  13.    }
  14.    return $arr;
  15. }
复制代码
  1. //改进版:
  2. function bubbleSort($arr)
  3. {
  4.    $n = count($arr);
  5.    for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮)
  6.      $flag = 0;  //是否发生位置交换的标志
  7.      for($j=0;$j<$n-$i;$j++) { //每一轮冒泡(两两比较,大者后移)
  8.        if($arr[$j] > $arr[$j+1]) { //前者大于后者,交换位置
  9.           $tmp = $arr[$j];
  10.           $arr[$j] = $arr[$j+1];
  11.           $arr[$j+1] = $tmp;
  12.           $flag = 1;
  13.        }
  14.      }
  15.      if($flag == 0) {  //没有发生位置交换,排序已完成
  16.        break;
  17.      }
  18.    }
  19.    return $arr;
  20. }
复制代码
为了进步冒泡排序算法的服从,主要必要改进的地方有:
(1)淘汰冒泡的轮数:当一轮冒泡排序中没有发生位置互换时体现数组已排好序了,应立即退出循环。
(2)淘汰每一轮比力的次数:对数组中已经排好序的部门元素不再对它们进行比力。
2. 插入排序:
思路:假设数组前面的元素是排好序的,遍历数组反面的元素,在已排好序的元素队列中找到符合的位置,插入此中。
  1. function insertSort($arr)
  2. {
  3.    $n = count($arr);
  4.    for($i=1;$i<$n;$i++) { //从第二个元素开始插入
  5.      for($j=$i-1;$j>=0;$j--) { //与前面的数比较,找到插入的位置
  6.        if($arr[$j] > $arr[$j+1]) { //比前面的数小,交换位置
  7.           $tmp = $arr[$j];
  8.           $arr[$j] = $arr[$j+1];
  9.           $arr[$j+1] = $tmp;
  10.        } else { //大于或等于前面的数,表示已找到插入的位置
  11.           break;
  12.        }
  13.      }
  14.    }
  15.    return $arr;
  16. }
复制代码
3. 选择排序:
思路:进行多次选择,每次选出最大元素放入指定位置。
  1. function selectSort($arr)
  2. {
  3.    $n = count($arr);
  4.    for($i=$n-1;$i>0;$i--) { //选择排序的轮数($n-1轮)
  5.      $pos = $i; //假设最大元素的位置
  6.      for($j=0;$j<$i;$j++) { //每一轮:从未选择过的元素中选择最大的数
  7.        if($arr[$j] > $arr[$pos]) { //所在位置元素比目前最大元素大,标志其位置
  8.           $pos = $j;
  9.        }
  10.      }
  11.      if($pos != $i) { //将最大元素放入指定的位置
  12.        $tmp = $arr[$pos];
  13.        $arr[$pos] = $arr[$i];
  14.        $arr[$i] = $tmp;
  15.      }
  16.    }
  17.    return $arr;
  18. }
复制代码
4. 快速排序:
思路:递归算法。先选择数组的第一个元素作为标准,然后把小于或即是它和大于它的数分别放入两个数组中,对这两个数组也进行类似的处理,末了归并这两个数组和第一个元素。
  1. function quickSort($arr)
  2. {
  3.    $n = count($arr);
  4.    if($n <= 1) { //若数组只有一个元素,直接返回
  5.      return $arr;
  6.    }
  7.    $largeArr = array(); //存放大数
  8.   $smallArr = array(); //存放小数
  9.    $cur = $arr[0];  //分类基数
  10.    for($i=1;$i<$n;$i++) { //遍历数组元素,对每个元素进行归类
  11.      if($arr[$i] > $cur) {
  12.        $largeArr[] = $arr[$i];
  13.      } else {
  14.        $smallArr[] = $arr[$i];
  15.      }
  16.    }
  17.    //分别对大数组和小数组进行相同的处理
  18.    $smallArr = quickSort($smallArr);
  19.    $largeArr = quickSort($largeArr);
  20.    //合并小数组、分类基数和大数组
  21.    return array_merge($smallArr,array($cur),$largeArr);
  22. }
复制代码
各个排序算法的时间复杂度和空间复杂度:
排序算法最好时间分析最差时间分析均匀时间复杂度稳定度空间复杂度
冒泡排序O(n)O(n2)O(n2)稳定O(1)
插入排序O(n)O(n2)O(n2)稳定O(1)
选择排序O(n2)O(n2)O(n2)稳定O(1)
快速排序O(nlog2n)O(n2)O(nlog2n)不稳定O(log2n)~O(n)

注:快速排序在数组乱序是服从是最好的,在数组有序时服从是最差的。
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技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作