使用PHP实现快速排序

<?php

/**
 * 快速排序(不去重)
 * @param $arr
 * @return array|false
 */
function quickSort1($arr)
{
    if (!is_array($arr)) {
        throw new Exception('参数不正确！');
    }

    if (count($arr) <= 1) {
        return $arr;
    }

    $first = $arr[0];
    $left = [];
    $right = [];
    foreach ($arr as $key => $val) {
        if ($key==0) {
            continue;
        }
        if ($val <= $first) {
            $left[] = $val;
        } elseif ($val > $first) {
            $right[] = $val;
        }
    }

    $left = quickSort1($left);
    $right = quickSort1($right);

    return array_merge($left,[$first],$right);
}

$arr = [2,3,1,6,8,3];
var_dump(quickSort1($arr));

/**
 * 快速排序(去重)
 * @param $arr
 * @return array|false
 */
function quickSort2($arr)
{
    if (!is_array($arr)) {
        throw new Exception('参数不正确！');
    }

    if (count($arr) <= 1) {
        return $arr;
    }

    $first = $arr[0];
    $left = [];
    $right = [];
    foreach ($arr as $key => $val) {
        if ($val < $first) {
            $left[] = $val;
        } elseif ($val > $first) {
            $right[] = $val;
        }
    }

    $left = quickSort2($left);
    $right = quickSort2($right);

    return array_merge($left,[$first],$right);
}

$arr = [2,3,1,6,8,3];
var_dump(quickSort2($arr));

/*
 * 快速排序的基本思想
 * 通过一趟排序将待排序的记录分割成独立的两部分
 * 其中一部分记录的关键字均比另一部分的关键字小
 * 则可分别对这个两部分记录继续进行排序
 * 以达到整个序列有序的目的
 */

$list = array(50, 10, 90, 30, 70, 40, 80, 60, 20);
QuickSearch($list, 0, count($list) - 1);
var_export($list);

function QuickSearch(array &$list, int $low, int $high)
{
    // 这个判断一定要加上, 递归才能结束
    if ($low < $high)
    {
        $pivot = Partition($list, $low, $high);
        QuickSearch($list, $low, $pivot);
        QuickSearch($list, $pivot + 1, $high);
    }
}

/**
 * 这个取中间值的算法很有趣
 * 首先取一个中间值, 把比中间值小的放左边, 大的放右边
 * 程序运行的结果就是, 中间值左边的关键字都比中间值小, 右边的关键字都比中间值大
 *
 * 程序对比的过程是：当中间值在左边时, 将其与右边的关键字 从右向左逐一比较, 直到有值比中间值小时
 * 将中间值换到右边(与比它小的那个值对换), 此时, 右边那些比较过的值就不再参与后面的比较
 * 当中间值在右边时, 将其与左边没比较过的关键字 从左到右逐一比较, 直到有值比中间值大时,
 * 将中间值换到左边
 * 一左一右一左一右重复对比之后, 中间值就慢慢跑到中间去了
 *
 * @param $list
 * @param int $low
 * @param int $high
 * @return int
 */
function Partition(&$list, int $low, int $high)
{
    // 用第一个记录作为枢轴记录
    $pivot = $list[$low];
    while ($low < $high)
    {
        while ($low < $high && $list[$high] > $pivot)
            $high--;
        swap($list, $low, $high);
        while ($low < $high && $list[$low] < $pivot)
            $low++;
        swap($list, $low, $high);
    }
    return $low;
}

function swap(array &$arr, $x, $y)
{
    $temp = $arr[$x];
    $arr[$x] = $arr[$y];
    $arr[$y] = $temp;
}

/**
     * 快速排序
     */
    public function Quick_sort($arr = array(50, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2)){
        //判断参数是否是一个数组
        if(!is_array($arr)) return false;

        //递归出口:递归至数组长度为1，则返回数组
        $length = count($arr);
        if($length<=1) return $arr;

        //数组元素有多个,则定义两个空数组
        $left = array();
        $right = array();

        //使用for循环遍历数组
        for($i=1; $i<$length; $i++) {
            $value = $arr[0] ; //把 第一个元素 当做 比较对象

            if($arr[$i] < $value){
                $left[]=$arr[$i];    //小于 比较对象放入 $left 数组
            }else{
                $right[]=$arr[$i];    //大于 比较对象放入 $right 数组
            }
        }

        //不断递归 $left、$right数组知道数组长度为1
        $left = $this->Quick_sort($left);
        $right = $this->Quick_sort($right);


        //将所有的结果合并
        return array_merge($left,array($arr[0]),$right);
    }