快速排序

发表于 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
$arr = [11, 8, 43, 23, 10, 100];
function quickSort($arr)
{
    $count = count($arr);
    if ($count <= 1) {
        return $arr;
    }

    //选个轴
    $comparedNum = $arr[0];
    $smallList   = $bigList   = array();

    for ($i = 1; $i < $count; $i++) {
        //小于对比数的放一起，大于的放一起
        if ($arr[$i] < $comparedNum) {
            $smallList[] = $arr[$i];
        } else {
            $bigList[] = $arr[$i];
        }
    }

    $smallList = quickSort($smallList);
    $bigList   = quickSort($bigList);

    return array_merge($smallList, array($comparedNum), $bigList);
}

print_r(quickSort($arr)); //Array ( [0] => 8 [1] => 10 [2] => 11 [3] => 23 [4] => 43 [5] => 100 )

//重点是理解这里的递归，这里可以举个例子：比如$arr = [2,1,4,3]
// 1，第一次执行 $smallList[] = 1；$bigList = [4,3]
// 2，调用quickSort($smallList，因为它只有一个元素)，函数会直接返回$smallList，因为它只有一个元素
// 3，调用quickSort($bigList) 它会执行然后返回一个 array_merge合并后的数组 [3,4]
// 3.1 因为这个时候$bigList有2个元素，于是它就会进入到for循环里，然后和对比数对比，
// 照样分为$smallList和$bigList 两个数组，这个时候$smallList = [3];$bigList = [],
// 然后继续分别调用 $smallList = quickSort($smallList);    $bigList   = quickSort($bigList); 
// 但是这个时候他们分别为$smallList为1个元素，$bigList为0个元素，这时候
//    $count = count($arr);
//    if ($count <= 1) {
//        return $arr;
//    }
//这个条件将直接返回，不会再继续递归下去了。然后 array_merge 合并返回
// 最后 3 这个步骤里调用的quickSort($bigList) 将会得到一个合并后的结果 [3,4]
//最后在把 2 和 3的结果 和 选择的对比数($comparedNum),合并即得到我们最后的结果了。