快速排序分析与行为

Question

我正在阅读关于快速排序algoritm的书名为算法第四版罗伯特塞奇威克。

快速排序之所以流行，是因为它不太难实现，对于各种不同类型的输入数据都能很好地工作，并且在典型应用程序中比任何其他排序方法都要快得多。快速排序算法的可取特性是，它是就地的(只使用一个小的辅助堆栈)，并且平均需要与N个log成比例的时间来排序一个长度N的数组。到目前为止，我们考虑过的任何算法都没有结合这两个属性。 此外，与大多数排序算法相比，quicksort具有更短的内循环，这意味着它在实践和理论上都是快速的。它的主要缺点是，它是脆弱的，因为在实现中涉及到一些注意，以确保避免糟糕的性能。

我对以上案文的问题是

1. 作者所说的“只使用一个小的辅助堆栈”是什么意思？
2. 作者所说的“快速排序比大多数其他排序算法具有更短的内部循环”是什么意思？

请求用简单的例子来解释。

谢谢

Answer 1

作者所说的“只使用一个小的辅助堆栈”是什么意思？

作者的意思是，除了要排序的数据之外，只需要很少的额外内存。因此，在排序过程中生成的数据结构没有很大的开销。

1. 作者所说的“快速排序比大多数其他排序算法具有更短的内部循环”是什么意思？

作者的意思是，在最里面的循环中执行的指令数量是相当可观的，这对于例如cpu缓存是一个好处。

在下面的代码中，内部循环中只有一个索引是递增/递减的。当然，循环条件会被检查。

作为一个例子，，我以维基百科中提到的实现为例

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p – 1)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo – 1
j := hi + 1
loop forever
    do
        i := i + 1
    while A[i] < pivot
    do
        j := j – 1
    while A[j] > pivot
    if i >= j then
        return j
    swap A[i] with A[j]

Answer 2

1. 作者所说的“只使用一个小的辅助堆栈”是什么意思？

您还需要考虑quick-sort是in-place排序算法。

in-place的意思是：

• 这个in-place特性大大减少了存储需求。
• 它使用恒定的存储量(读:额外变量的固定数量)来简化排序过程。

因此，由于存储量小且固定，它说quick-sort“只使用一个小的辅助堆栈”。

1. 作者所说的“快速排序比大多数其他排序算法具有更短的内部循环”是什么意思？

这样，可能意味着内部循环中的逻辑很简单，因此需要更少的代码。这个“较短的内循环”不应与循环的迭代次数混淆。因为在递归树的任何级别上，迭代的总次数仅为"n“。

Answer 3

作者所说的“只使用一个小的辅助堆栈”是什么意思？

在理想情况下，快速排序在堆栈上使用O(log2(n))空间，在最坏的情况下，它在堆栈上使用O(n)空间，比排序的数组占用更多的空间。

1. 作者所说的“快速排序比大多数其他排序算法具有更短的内部循环”是什么意思？

这在现代系统中可能并不重要，因为任何合理大小的内部循环都适合大多数处理器上的代码缓存。条件分支将影响管道性能，这取决于分支预测。

快速排序..。在典型应用程序中比任何其他排序方法都要快得多。

这不是真的，在最好的情况下，快速排序只比合并排序稍微快一些(小于10%)，在最坏的情况下，O(n^2)和O(n log(n))则要慢得多。合并排序的主要问题是它需要一个大小相同的临时数组，或者是原始数组大小的1/2。