递归算法：快速排序算法及其思想运用的查找第K大数【leetcode-215】PHP

快速排序

今天说一下快速排序算法，这个例子实现了从小到大的排序。也是使用了递归的思想。如果你对一个数组进行排序。就是把这个数组把它考虑成一个个区间，对每个区间分别排序，最终完成整个数组的排序。

class Solution {

    function quickSort($arr) {
        $len = count($arr);
        $this->_quickSort($arr, 0, $len-1);
        return $arr;

    }
   
    function _quickSort(&$arr,$l, $r){
        if($l>=$r){
            return ;
        }
        //echo join(',', $arr);echo "\n";
        $p = $this->partition($arr, $l, $r);
        //echo "p:$p,$arr[$p]\n";
        $this->_quickSort($arr, $l, $p-1);
        $this->_quickSort($arr, $p+1, $r);
    }

    function partition(&$arr, $l, $r){
        $v = $arr[$l];
        $j = $l;    //j是大于v和小于v的分界点
        //arr[l+1,j] < v , arr[j+1,i) > v ,i是待考察元素，不包括i。这样初始化， <v的是空，>v的也是空

        for($i=$l+1; $i<=$r;$i++){
            if($arr[$i] < $v){
                list($arr[$j+1], $arr[$i]) = [$arr[$i], $arr[$j+1]];
                $j++;
            }
        }
        $arr[$l] = $arr[$j];
        $arr[$j] = $v;
        return $j;
    }
}

$arr = [5,0,77,7,3,-20,8,4,6,2,9,-1];
$sorted = (new Solution())->quickSort($arr);

_quickSort函数

比如这个数组的长度是n。从0到n-1这个索引范围内进行排序，也就是说我对这个数组的整个区间先进行一次快速排序，看看这个_quickSort函数，有三个参数，第一个参数待排序的数组，第二个参数是需要排序的区间的最左边的索引位置left，第三个参数需要排序的区间的最右边的索引位置right。如果left >= right就是递归终止条件，说明[left,right]闭区间不需要排序了。
快速排序的思路是：递归，把一个大的问题，分解为更小的问题，直到递归终止条件，完成一部分的排序；全部递归完成，整个数组排序完成。

代码详解

_quickSort函数，一开始咱们考察这个区间段是从数组的0索引到n-1索引，先需要一个partition操作。partition这个函数的作用是在数组的这里找到一个值v，然后把数组里面的left到right区间里的数进行分类，一部分比v小，一部分比v大。为了实现这个，需要对数组进行交换操作，然后partition函数返回了v这个值所在的数组索引p。
此时数组的[left,right]这个闭区间就被索引p分为了两部分，从left到p-1的索引的数组区间比v小，就是它的左边。从p+1到right的索引的数组区间都大于等于v。
这样，就完成了[p左边、p、p右边]的从小到大的排序。根据递归的思想，我们就可以继续调用_quickSort函数，对p的左边区间，即[left,p-1]进行快速排序；对p的右边区间，即[p+1,right]进行快速排序；这是一种分解问题规模的方法。
直到left >= right，结束递归，这个数组arr的自顶向下的完成了排序。

partition函数

理解了快速排序的递归思路之后，我们看一下这个partition函数，partition函数每次把数组区间分为了2部分。这个函数也是三个参数。第一个参数是整个数组，这里引用传值保证了对数组的操作，而不是副本；第二个参数是partition的区间的left，第三个参数是partition的区间的right。需要从[left,right]中找到一个标定值v作为参考，把区间里的数分为两部分。

代码详解

我们这里就用这个区间最左边那个left这个位置的值。v = arr[left];
然后呢，我们设置一个变量 j 标记位置作为，j=left。

因为我们标定值v取得最左边left的值，然后我们就用for循环从i = left+1这个位置开始考察，看i的值是不是比v小，如果比v小的话，我们就把这个位置的值和j+1进行交换。如果i的值比v大的话，那样的话就不需要交换，直接i++就行了，这样i等于right时，还结束for循环。
此时，从left+1到j的区间的值都小于v，从j+1到right的区间的值都大于等于v。再把left的位置的值和j的位置进行交换，j在的位置就等于v，j把left到riht的区间分成了两部分，完成了partition操作，返回j就OK了。

例子

例子说明一下，概述_quickSort函数：【文本里面的变量前的$没写】
对数组arr = [5,0,77,7,3,-20,8,4,6,2,9,-1]进行，快速排序。
第一次调用_quickSort(&arr, 0, 11)，先partition操作，标定值left位置的，即5，经过partition之后，5被排到了索引6这个位置了。
此时arr是这样的[-1,0,3,-20,4,2,5,77,6,7,9,8]。
然后递归的调用_quickSort(&arr, 0,5);_quickSort(&arr, 7,11);
其中先_quickSort(&arr, 0,5); 执行partition操作之后数组arr是这样的
[-20,-1,3,0,4,2,5,77,6,7,9,8], 最左边的-1被排到了索引1的位置。
然后递归调用_quickSort(&arr, 0,0);_quickSort(&arr, 2,5);
其中先_quickSort(&arr, 0,0); 直接返回了，不需要partition操作。
然后开始_quickSort(&arr, 2,5)，对从索引2到5，即3,0,4,2这段进行partition操作，3是标定值，得到了2,0,3,4，最左边的3被排到了索引4的位置，是根据标定值3分成了两部分，左边比3小，右边大于等于3。
执行partition操作之后数组arr是这样的[-20,-1,2,0,3,4,5,77,6,7,9,8]。
递归执行继续进行，先左再右。
[-20,-1,0,2,3,4,5,77,6,7,9,8]
[-20,-1,0,2,3,4,5,8,6,7,9,77]
[-20,-1,0,2,3,4,5,7,6,8,9,77]
完成了排序，这个递归就像树结构。

你以为这就完了吗？No

快速排序get到之后，我们看一下leetcode-215。

问题描述

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

思路

找数组中第K大元素。这个题呢。如果一般想想的话，把数组直接元素排序，从大到小排，然后取到第K大元素。但是这样做效率不是很高啊。如果给你一个百万个数让你取第20大元素的话，你得把所有的数排序之后，在取第20个元素。

我们刚学过快速排序算法，如果是从大到小排序，快速排序时的partition操作就是找到数组中的某个元素在整个数组中排好序之后所在的索引位置p。这个索引p的元素，就是这个元素在数组中从0开始的第p大元素。每次你要从这个数组中找到第K大的元素，其实就是从0开始的第K-1大元素，这样第一次调用_quickSelect(nums,0, count-1,k-1)时，最后一个参数传K-1。
进行partition操作之后获取到了第p大的元素，比较K和p，如果 K > p，就在 [p+1,right] 里面再次调用_quickSelect；如果 K > p，就在 [left,p-1] 里面再次调用_quickSelect；不断的缩小查找范围，正巧如果K== p，就说明找到了第K大元素的位置，返回这个元素的值就行了。

代码

class Solution {

    public $arr;

    /**
     * @param Integer[] $nums
     * @return TreeNode
     */
    function findKthLargest($nums,$k) {
        $count = count($nums);
        if($count < $k ){
            return '没有啊';
        }
        //k-1是因为数组索引是从0开始的，第k大的索引其实是k-1。
        $k_big = $this->_quickSelect($nums,0, $count-1,$k-1);
        return $k_big;
    }

    function _quickSelect(&$nums, $left, $right,$k){    
        if($left < $right){
            $p = $this->partition($nums, $left, $right);
            //p是从0开始第p个元素，k是从0开始要找的第K个元素
            if($p == $k){
                return $nums[$p];
            }else if($p < $k ){
                return $this->_quickSelect($nums, $p+1,$right, $k);
            }else{
                return $this->_quickSelect($nums, $left, $p-1, $k);
            }

        }
        //left,right 相等时，我要找的数所在这个的区间只有一个数，不需要partition，这个数就是我要找的。就是partition了，还是得到这个数。
        //不会出现left > right的情况，说明k不在区间里面，上一步就错了，不可能，矛盾了。
        return $nums[$left];
    }

    function partition(&$nums, $left, $right){
        //随机取一个数作为标准，可能会撞大运哟，还可以减少分的不均匀的情况。
        $random = rand($left, $right);
        list($nums[$left], $nums[$random]) = [$nums[$random],$nums[$left]];
        $v = $nums[$left];
        $j = $left;
        //[$l+1,$j] < $v , [$j+1,$i) >v
        for($i=$left+1;$i <= $right;$i++){
            if($nums[$i] > $v){
                //上面的>和<决定了升序还是降序
                $j++;
                list($nums[$i], $nums[$j]) = [$nums[$j], $nums[$i]];
            }
        }
        $nums[$left] = $nums[$j];
        $nums[$j] = $v;
        return $j;
    }
}

//$nth = 900;
//$nums = [];
//for($i=0;$i<1000000;$i++){
//    $nums[] = rand(1,100000000);
//}
$nth = 2;
$nums = [3,2,1,5,6,4];

$obj = new Solution();
$res = $obj->findKthLargest($nums,$nth);

总结

递归算法是计算机处理擅长问题的缩影，通过甚少的代码多次执行，快速完成简单重复的任务，如果递归或循环不能搞定的问题，代码量就大，就复杂。这是就需要数学家发挥聪明，想象出一个公式来解决。计算机程序套公式实现。
如果对这个算法不熟悉的话，仔细阅读，绝对可以读懂。写的不好的地方，请大家多包涵。