对取对数的快速排序的混淆 space

Question

如果只调用较小的分区数组，那么较大的数组如何排序？如果递归完成，我只看到更改 b 位置的代码（QS 在 if 和 else 语句中调用）。

 public static void QS(int[] b, int h, int k) {
     int h1= h; int k1= k;
     // invariant b[h..k] is sorted if b[h1..k1] is sorted
     while (b[h1..k1] has more than 1 element) {
         int j= partition(b, h1, k1);
         // b[h1..j-1] <= b[j] <= b[j+1..k1]
         if (b[h1..j-1] smaller than b[j+1..k1])
             QS(b, h, j-1); h1= j+1; 
         else
             QS(b, j+1, k1); k1= j-1; 
     }
}

Answer 1

注意在递归调用 QS 之后，如果 b[h1..] 小于 b[j+1..] 则更新 h1，如果 b[h1..] 大于或更新 k1等于 b[j+1..] 。

代码有bug，if之后的第一个调用应该是QS(b, h1, j-1);

对数space用法指的是由于递归而被快速排序使用的堆栈space。在示例代码中，只有较小的分区使用递归调用进行排序，然后代码循环返回将较大的分区分成两部分，再次，只对现在拆分较大的分区的较小部分使用递归调用.

Link 转文章：

http://en.wikipedia.org/wiki/Quicksort#Optimizations

http://blogs.msdn.microsoft.com/devdev/2006/01/18/efficient-selection-and-partial-sorting-based-on-quicksort

我不确定对尾递归的引用，因为代码包含一个实际循环而不是使用尾递归。尾递归看起来像是在函数中执行的最后一行的递归调用，编译器可以将其优化为循环。

Answer 2

这是一些难以阅读的伪代码。这可能更容易理解：

QuickSort(b[], low, hi)
  while the range low..hi contains more than 1 element
    1: Pick a random pivot 'j' from the array
    2: Re-order the array so that all elements less than the pivot are in
       b[low..j-1], and all elements greater than the pivot are in b[j+1..hi]
    3: Call quicksort on the side with less elements, and update the range to
       exclude the sorted side

大约一半的值将小于主元，一半的值将大于主元。这意味着在步骤 3 之后，范围 low..hi 的大小大致减半。因此，需要 log|N|范围之前的迭代仅包含一个元素。

很难解释这一点，但是看看第 3 步如何只对数组的一半调用快速排序？这是因为 while 循环的剩余部分对另一半进行了排序。该函数可以很容易地重写如下：

QuickSort(b[], low, hi)
  if the range low..hi contains more than 1 element
    1: Pick a random pivot 'j' from the array
    2: Re-order the array so that all elements less than the pivot are in
       b[low..j-1], and all elements greater than the pivot are in b[j+1..hi]
    3: Call quicksort on both sides

while 循环已被 if 语句和第二个递归调用所取代。我希望从这里你可以看到复杂度大约是 N log|N|.

编辑

那么while循环如何对剩余的元素进行排序呢？在第 3 步之后，范围已更新以排除较小的一半，因为我们只是通过调用 QuickSort 对其进行了排序。这意味着该范围现在只包含较大的一半 - 未排序的元素。所以我们对这些未排序的元素重复步骤 1 - 3，并再次更新范围。

随着每次迭代，未排序元素的数量越来越少，最终我们将只剩下一个未排序元素。但是当然，一个元素是排序的，所以此时我们知道我们已经对数组中的每个元素进行了排序。

对取对数的快速排序的混淆 space

Confusion on quicksort that takes logarithmic space

java

sorting

algorithm

big-o

quicksort