PHP 算法之快速排序

答案

• 从数列中挑出一个元素，称为“基准”（pivot），通常选择第一个或最后一个元素。
• 扫描数列，以基准元素为比较对象，把数列分成两个区，小于基准元素的移动到基准元素前面，大的移到后面，相等的前后都可以。分区完成之后，基准元素就处于数列的中间位置。
• 再用同样的方法，递归地排序划分的两个区。

在分区过程中，为了不使用额外的空间，左右同时扫描基准之外的元素，在得到一个左边大于基准，右边小于基准的时候，把他们两个进行交换。

function quickSort(&$arr, $leftIndex, $rightIndex)
{
    if ($leftIndex < $rightIndex) {
        $index = partition($arr, $leftIndex, $rightIndex);
        quickSort($arr, $leftIndex, $index - 1);
        quickSort($arr, $index, $rightIndex);
    }
}
function partition(&$arr, $leftIndex, $rightIndex)
{
    $pivot = $arr[($leftIndex + $rightIndex) / 2];
    while ($leftIndex <= $rightIndex) {
        while ($arr[$leftIndex] < $pivot) {
            $leftIndex++;
        }
        while ($arr[$rightIndex] > $pivot) {
            $rightIndex--;
        }
        if ($leftIndex <= $rightIndex) {
            list($arr[$leftIndex], $arr[$rightIndex]) = [$arr[$rightIndex], $arr[$leftIndex]];
            $leftIndex++;
            $rightIndex--;
        }
    }
    return $leftIndex;
}

时间复杂度：

• 最坏：O(n2)
• 平均：O(n lg n)
• 最好：O(n)