快速排序

image.png

---

快速排序原理：在要排序的数字中取一个值，把大于这个这个值和小于这个值得数字分别放到数组里，在递归执行，执行取值，在把大于这个这个值和小于这个值得数字分别放到数组里，最后执行的时候数组就一个元素,执行效率快排平均效率O(nlogn),最好情况O(nlogn)每次取中间值得,最坏情况是当数组有序时,退化成O(n^2)

---

代码部分如下：

public function quickSort($data)
{
    $size = count($data);
    if($size>1) {
        $key = $data[0];
        $l = $r = [];
        for ($i = 1; $i < $size; $i++) {
            if ($data[$i] >= $key)
                $r[] = $data[$i];
            else
                $l[] = $data[$i];
        }
        $l_re = quickSort($l);
        $r_re = quickSort($r);

        return array_merge($l_re, [$key], $r_re);
    }
    else
        return $data;
}