php实现快速排序

php实现快速排序

这几上代码

一、代码

代码一：

<?php
function q($array) {
  if (count($array) <= 1) {return $array;}
//以$key为界，分成两个子数组
  $key = $array[0];
  $l = array();
  $r = array();
//分别进行递归排序，然后合成一个数组
  for ($i=1; $i<count($array); $i++) {
  if ($array[$i] <= $key) { $l[] = $array[$i]; }
  else { $r[] = $array[$i]; }
 }
  $l = q($l);
  $r = q($r);
  return array_merge($l, array($key), $r);
}
$arr = array(1,2,44,3,4,33);
print_r( q($arr) );

代码二：在thinkphp的控制器中

<?php
namespace appindexcontroller;

use appindexcontrollerBase;

class Exercise extends Base
{
    public function index()
    {
        // return view('insert_array');
        $this->quickSortDemo();
    }

    //快速排序（递归）
    public function quickSort($arr){
        //0、递归返回条件
        if(count($arr)<=1) return $arr;
        //1、找到分割点
        $mid = $arr[0];
        $l = array();
        $r = array();
        //2、对数据进行分割，也就是对除分割点外的每个数据进行遍历
        for($i=1;$i<count($arr);$i++){
            if($arr[$i]<$mid) $l[] = $arr[$i];
            else  $r[] = $arr[$i];
        }
        $l=$this->quickSort($l);
        $r=$this->quickSort($r);
        //3、对分割的数据进行组合
        return array_merge($l,array($mid),$r);
    }

    public function quickSortDemo(){
        $arr=array(19,65,2,5,1,456,32,64564,2,7,9,2);
        dump($this->quickSort($arr));
    }
}

1、第20行，这里是用新数组来存分割出来的数据，而不是在原数据的基础上交换，一种典型的那空间换低算法复杂度

2、第27行，实在容易忘记接收返回值

3、第27行，因为在thinkphp中，这个this->好像都不能省的样子，后者还有什么别的原因

4、第30行，array的那些函数，前缀都是array_，而不是arr_，array_merge()的参数必须是数组

5、第30行，array()参数是变量的时候可以将变量化为数组，其实就和array的定义那样

6、第24行，数组添加值，稍微注意一下就好

7、快排的核心点，找好分割点，可以拿第一个点做分割点

截图