我们将探索分而治之(divide and conquer,D&C)——一种著名的递归式问题解决方法
欧几里得算法:适用于这小块地的最大方块,也是适用于整块地的最大方块。 可汗学院很清楚地阐述了这种算法 https://www.khanacademy.org/computing/computer-science/ryptography/modarithmetic/a/the-euclidean-algorithm
提示:编写涉及数组的递归函数时,基线条件通常是数组为空或只包含一个元素。陷入困境时,请检查基线条件是不是这样的 函数式编程一瞥:为何还要使用递归方式呢?看看函数式编程你就明白了!诸如Haskell等函数式编程语言没有循环,因此你只能使用递归来编写这样的函数。如果你对递归有深入的认识,函数式编程语言学习起来将更容易
首先,从数组中选择一个元素,这个元素被称为基准值 (pivot),接下来,找出比基准值 小的元素以及比基准值 大的元素
这被称为分区(partitioning)。现在你有
class QuickSort
{
static public function sort($array)
{
if (count($array) <= 1) {
return $array;
}
$leftArray = $rightArray = [];
$key = array_shift($array);
foreach ($array as $item) {
$key > $item ? ($leftArray[] = $item) : ($rightArray[] = $item);
}
return array_merge(self::sort($leftArray), [$key], self::sort($rightArray));
}
}
$array = [5, 3, 6, 2, 10, 7, 9, 20, 15];
echo join(QuickSort::sort($array), ',') . PHP_EOL;
快速排序的独特之处在于,其速度取决于选择的基准值。快速排序在最糟糕情况下,其运行时间为O(n2)。与选择排序一样慢!但这是最糟情况。在平均情况下,快速排序的运行时间为O(n log n)
快速查找的速度确实更快,因为相对于遇上最糟情况,它遇上平均情况的可能性要大得多
快速排序的性能高度依赖于你选择的基准值 。假设你总是将第一个元素用作基准值 ,且要处理的数组是有序的。由于快速排序算法不检查输入数组是否有序,因此它依然尝试对其进行排序
注意,数组并没有被分成两半,相反,其中一个子数组始终为空,这导致调用栈非常长 在最糟情况下,栈长为O(n),而在最佳情况下,栈长为O(log n) 在这个示例中,整个算法需要的时间为O(n)O(log n)=O(n log n),这是最佳情况。在最糟情况下,有O(n)层,因此该算法的运行时间为O(n)O(n)=O(n2)`