PHP递归实现快速排序的方法示例

2024-12-18 22:18:48

本文实例讲述了PHP递归实现快速排序的方法。分享给大家供大家参考，具体如下：

首先我们要理解一下快速排序的原理：找到当前数组中的任意一个元素（一般选择第一个元素），作为标准，新建两个空数组，遍历整个数组元素，如果遍历到的元素比当前的元素要小，那么就放到左边的数组，否则放到右面的数组，然后再对新数组进行同样的操作。

不难发现，这里符合递归的原理，所以我们可以用递归来实现。

使用递归，则需要找到递归点和递归出口：

递归点：如果数组的元素大于1，就需要再进行分解，所以我们的递归点就是新构造的数组元素个数大于1

递归出口：我们什么时候不需要再对新数组不进行排序了呢？就是当数组元素个数变成1的时候，所以这就是我们的出口。

理解了原理，来看一下代码实现~

<?php
//快速排序
//待排序数组
$arr=array(6,3,8,6,4,2,9,5,1);
//函数实现快速排序
function quick_sort($arr)
{
    //判断参数是否是一个数组
    if(!is_array($arr)) return false;
    //递归出口:数组长度为1，直接返回数组
    $length=count($arr);
    if($length<=1) return $arr;
    //数组元素有多个,则定义两个空数组
    $left=$right=array();
    //使用for循环进行遍历，把第一个元素当做比较的对象
    for($i=1;$i<$length;$i++)
    {
      //判断当前元素的大小
      if($arr[$i]<$arr[0]){
        $left[]=$arr[$i];
      }else{
        $right[]=$arr[$i];
      }
    }
    //递归调用
    $left=quick_sort($left);
    $right=quick_sort($right);
    //将所有的结果合并
    return array_merge($left,array($arr[0]),$right);
}
//调用
echo "<pre>";
print_r(quick_sort($arr));

运行结果：

Array
(
  [0] => 1
  [1] => 2
  [2] => 3
  [3] => 4
  [4] => 5
  [5] => 6
  [6] => 6
  [7] => 8
  [8] => 9
)

PS：这里再为大家推荐一款关于排序的演示工具供大家参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多关于PHP相关内容感兴趣的读者可查看本站专题：《php排序算法总结》、《PHP数据结构与算法教程》、《php程序设计算法总结》、《PHP数组(Array)操作技巧大全》、《php字符串(string)用法总结》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

希望本文所述对大家PHP程序设计有所帮助。

php使用递归与迭代实现快速排序示例

复制代码代码如下: /** * 递归法实现的快速排序 * @param $seq * @return array */function quicksort($seq){ if (count($seq) > 1) { $k = $seq[0]; $x = array(); $y = array(); $_size = count($seq); //do not use count($seq) in loop for. f
php关联数组快速排序的方法

本文实例讲述了php关联数组快速排序的方法.分享给大家供大家参考.具体如下: <?php function qsort($a,$f) { qsort_do(&$a,0,Count($a)-1,$f); } function qsort_do($a,$l,$r,$f) { if ($l < $r) { qsort_partition(&$a,$l,$r,&$lp,&$rp,$f); qsort_do(&$a,$l,$lp,$f); qsort_do(&am
PHP常用排序算法实例小结【基本排序，冒泡排序，快速排序，插入排序】

php三种基础算法:冒泡,插入和快速排序法 $array = array(2,3,5,6,9,8,1); //冒泡排序思想,前后元素比较 function sort_bulldle($array){ $num = count($array); for($i=0; $i<$num; $i++){ $tmp = $array[$i]; for ($j=$i-1; $j>=0; $j--) { if ($tmp < $array[$j]) { $arr[$j+1] = $arr[$j]; $a
PHP 快速排序算法详解

概念这里借用百度百科的一张图来,非常形象: 快速排序算法是对冒泡算法的一个优化.他的思想是先对数组进行分割, 把大的元素数值放到一个临时数组里,把小的元素数值放到另一个临时数组里(这个分割的点可以是数组中的任意一个元素值,一般用第一个元素,即$array[0]),然后继续把这两个临时数组重复上面拆分,最后把小的数组元素和大的数组元素合并起来.这里用到了递归的思想. PHP实现复制代码代码如下: /* 快速排序 */ function quickSort($array) {
排序算法之PHP版快速排序、冒泡排序

一.快速排序 1.简介快速排序是由东尼·霍尔所发展的一种排序算法.在平均状况下,排序 n 个项目要Ο(n log n)次比较.在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见.事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来.快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists).2.步骤从数列中挑出一个元素,称为 "基准&quo
php排序算法(冒泡排序,快速排序)

冒泡排序实现原理 ① 首先将所有待排序的数字放入工作列表中.② 从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换. ③ 重复步骤②,直至再也不能交换. 代码实现复制代码代码如下: <?php function bubbingSort(array $array) { for($i=0, $len=count($array)-1; $i<$len; ++$i) { for($j=$len; $j>$i;
php冒泡排序、快速排序、快速查找、二维数组去重实例分享

一.冒泡排序复制代码代码如下: //冒泡排序function bubble_sort($array){ $count=count($array); if($count <= 0){ return false; } for($i=0;$i<$count;$i++){ for($j=0;$j<$count-$i-1;$j++){ if( $array[$j] > $array[$j+1] ){
php快速排序原理与实现方法分析

本文实例讲述了php快速排序方法.分享给大家供大家参考,具体如下: <?php $n = array('13','14','55','10','54','2','79','106','89','90','22','60','111','77777','-110','-10','123'); function partition($n,$left,$right) { global $n; $pivot = $n[$left]; $lo=$left; $hi=$right+1; while($lo+
php实现快速排序法函数代码

代码1: 复制代码代码如下: <?php function quicksort($str){ if(count($str)<=1) return $str;//如果个数不大于一,直接返回 $key=$str[0];//取一个值,稍后用来比较: $left_arr=array(); $right_arr=array(); for($i=1;$i<count($str);$i++){//比$key大的放在右边,小的放在左边: if($str[$i]<=$key) $left_arr[
PHP两种快速排序算法实例

虽然在PHP这样的web应用开发中,我们不是太强调排序的重要性,因为PHP自身已经带了例如sort()等这样强大的排序函数,但是在一些重要的场合,例如某些高并发的场合,我想排序算法的影响已经不能忽略.所以在此介绍递归排序和迭代排序. 递归法: /** * 递归法实现的快速排序 */ function quicksort($seq) { $k = $seq[0]; $x = array(); $y = array(); for($i=1; $i< $_size; $i++) { if($seq[$
php实现快速排序的三种方法分享

写了三种php快速排示例,第一种效率低但最简单最容易理解,第二个是算法导论上提供的单向一次遍历找中值方法,第三种是双向遍历找中值经典快排算法.三组算法实现和比较如下: 方法一:该方法比较直观,但损失了大量的空间为代价,使用了效率较低的merge函数.在三种方法中效率最低.最坏情况下算法退化为(O(n*n)) 复制代码代码如下: function quick_sort($array) { if(count($array) <= 1) return $array; $key = $array[0]

PHP递归实现快速排序的方法示例

相关推荐

随机推荐