排序算法-快速排序

快速排序是对冒泡排序算法的一种改进。

基本思想：通过一趟排序将要排序的数组分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据小，然后再按此方法对两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序。

快速排序平均算法时间复杂度为O(nlogn)，它最坏的情况为O(n^2).

代码实现

方法一:

function quickSort($arr) {
    $count = count($arr);
    if ($count<2) {
        return $arr;
    }
    //创建临时数组，以基准值为分界线，大于基准值的放在右侧，
    //小于基准值的放在左侧
    $leftArr = $rightArr = [];
    //基准值， 一般取数组第一个元素
    $middle = $arr[0];
    for($i=1;$i<$count; $i++) {
        if ($arr[$i]<$middle) {
            $leftArr[] = $arr[$i];
        } else {
            $rightArr[] = $arr[$i];
        }
    }
    //递归，将左右数组排序
    $leftArr = quickSort($leftArr);
    $rightArr = quickSort($rightArr);
    //将排好序的临时数组合并
    return array_merge($leftArr,[$middle],$rightArr);
}

方法二：

function quick_sort($arr) {
    $count = count($arr);
    if($count<2) {
        return $arr;
    }
    $i = 0;
    $j = $count - 1;
    //基准值
    $key = $arr[0];
    while($i<$j) {
        //首先从后往前比较，比基准值大的放过，比基准值小的做交换
        while($i<$j && $arr[$j]>=$key) {
            $j--;
        }
        //交换
        $arr[$i] = $arr[$j];
        $arr[$j] = $key;
        //再从前往后比较，比基准值小的放过，比基准值大的做交换
        while($i<$j && $arr[$i] <= $key) {
            $i++;
        }
        $arr[$j] = $arr[$i];
        $arr[$i] = $key;
    }
    //经过一轮交换，基准值左侧全部比基准值小，基准值右侧比基准值大，但左右两侧并不一定是排好序的，
    //然后进行递归，将基准值左右两侧进行排序
    if ($i==0) {
        $left = [];
    } else {
        $left = quick_sort(array_slice($arr,0,$i));
    }
    if($i == $count-1) {
        $right = [];
    } else {
        $right = quick_sort(array_slice($arr, $i+1, $count+1-$i));
    }
    //将排好序的数组进行合并返回
    return array_merge($left, [$key], $right);
}