PHP快速排序算法

重要思想:
分而治之和递归思想

原理:
1: 选择一个基准值
2: 将数组分成两个子数组: 小于基准值的元素和大于基准值的元素
3: 利用递归对两个子数组进行快速排序
4: 合并三个数组

(注意:当子数组个数小于2时,终止递归直接返回子数组)

代码demo:

<?php
for ($i=0; $i < 100; $i++) { 
    $arr[] =  rand(1,1000);
}
print_r(quick_sort($arr));

/**
 * 快速排序
 * @param  array $arr 要排序的数组
 * @return array      排序后的数组
 */
function quick_sort($arr)
{
    $middle = $arr[0];// 获取基准值
    $count  = count($arr);// 元素个数
    $left   = $right = array();
    // 循环比较
    for ($i=1; $i < $count; $i++) { 
        if ($middle < $arr[$i]) {
            // 大于基准值
            $right[] = $arr[$i];
        } else {
            // 小于基准值
            $left[] = $arr[$i];
        }
    }
    // 元素个数大于二,进行递归
    $left = count($left) > 1 ? quick_sort($left) : $left;
    $right = count($right) > 1 ? quick_sort($right) : $right;
    // 合并排序后的数据
    return array_merge($left, array($middle), $right);
}