PHP 实现快速排序


快速排序是由东尼·霍尔发展的一种排序算法。

在平均状况下,排序 n 个项目要Ο(n log n)次比较。

在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。

事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环可以在大部分的架构上,很有效率地被实现出来。

快速排序采用分治法实现排序,具体步骤:

  1. 从数列中挑出一个数作为基准元素。通常选择第一个或最后一个元素。

  2. 扫描数列,以基准元素为比较对象,把数列分成两个区。规则是:小的移动到基准元素前面,大的移到后面,相等的前后都可以。分区完成之后,基准元素就处于数列的中间位置。

  3. 然后再用同样的方法,递归地排序划分的两部分

递归的结束条件是数列的大小是01,也就是永远都已经被排序好了。

PHP代码实现


function quickSort($arr) {
   // 先设定结束条件,判断是否需要继续进行
   if(count($arr) <= 1) {
       return $arr;
   }

   // 选择第一个元素作为基准元素
   $baseValue = $arr[0];

   // 初始化小于基准元素的左数组
   $leftArray = array();

   // 初始化大于基准元素的右数组
   $rightArray = array();

   // 遍历除基准元素外的所有元素,按照大小关系放入左右数组内
   array_shift($arr);
   foreach ($arr as $value) {
       if ($value < $baseValue) {
           $leftArray[] = $value;
       } else {
           $rightArray[] = $value;
       }
   }

   // 再分别对左右数组进行相同的排序
   $leftArray = quickSort($leftArray);
   $rightArray = quickSort($rightArray);

   // 合并基准元素和左右数组
   return array_merge($leftArray, array($baseValue), $rightArray);
}


本人主要从事APP,小程序开发,有专业的团队。微信:wqy0601415 (请注明需求);

上一篇: php 实现杨辉三角
下一篇: PHP 冒泡排序