算法图解阅读笔记-递归与快速排序算法

递归

1 只是让解决方案更加清晰，本身并没有性能上的提升。
2 递归最主要的就是基线条件与递归条件。

• 基线条件为到某一步骤破掉递归调用，正常返回常量。用于结束递归调用，避免无限循环的发生
• 递归条件为调用持续下去的条件，避免递归调用不执行。

快速排序

原理：选择待排序集中一个元素作为基点，将所有比基点元素大的元素划到一个结果集，将所有比基点元素小的元素划到另一个结果集，最后顺序合并小结果集，基点，大结果集。完成一次排序。对大小结果集中的元素循环上述处理，最终得到排序后的结果集。
快速排序的时间复杂度平均值为 O (n*log n) 最糟糕情况时间复杂度为O（N^2）

示例 递归实现

function quickSort($arr_info = array())
{
    if (sizeof($arr_info) < 2) {
        return $arr_info;
    }
    $mid = $arr_info[0];
    $max = array();
    $min = array();

    for ($i = 1; $i < sizeof($arr_info); $i++) {
        if ($arr_info[$i] >= $mid) {
            $max[] = $arr_info[$i];
        } else {
            $min[] = $arr_info[$i];
        }
    }
    return array_merge(quickSort($min), array($mid), quickSort($max));

}