思路

给定一个数组，内容都为数字
外层函数
1. 若传入数组只有一个元素，则直接返回当前数组
2. 取数组第一个值为中间值，循环判断其余值与中间值的大小比较
  1. 大于中间值存入当前右数组
  2. 小于中间值存入当前左数组
递归将循环判断结束得到的左右数组再执行取数组第一个值为中间值，循环判断其余值与中间值的大小比较的操作
1. 由上至下循环分隔数组为左右，最后返回拼接的数组(一个元素时左右拼接上仍为该元素)
2. 由下至上从一个元素的数组开始拼接拼接好左右数组的数组
由下至上结束递归时将两个有序数组拼接
得到一个升序数组

代码

<?php 
    $array = array(1,2,5,3,7,1,8);
    
    function quick_sort($array){
        if(count($array) <= 1){ //数组只有一个元素，直接返回该数组
            return $array;
        }
        $left = array();
        $right = array();
        $pivot = $array[0];
        
        for($i = 1;$i < count($array);$i++){ //当前数组第一位为中间值
            if($array[$i] > $pivot){ //左右数组存放比中间值小或大的数组成的数组
                $right[] = $array[$i];
            }else{
                $left[] = $array[$i];
            }
        }
        
        $left = quick_sort($left); //左数组不停再隔分直到满足只有一个元素
        /*
            quick_sort( quick_sort(quick_sort( ... )) )
            递归就是从外括号到内括号直到不满足条件，再从内括号到外括号执行
            最内层将直接返回(只有一个元素)
            每次递归内部都有两个递归(左右)
            
            1,2,3
            (1 | 2,3)
            (1) |  (2 | 3)
            (1) |  (2)  |  (3)
            
        */
        $left[] = $pivot;
        return array_merge($left,quick_sort($right));
    }

    $array = quick_sort($array);
    var_dump($array);
?>

算法学习之路 | 快速排序[Php]

Subscribe

Comments