1

我正在阅读介绍排序。我了解其中的大部分内容，但我不明白为什么大多数实现倾向于对其中的快速排序部分进行一次递归。快速排序的标准实现使用两个递归进行快速排序。

Intro sort, main logic:
  private static void introsort_loop (int[] a, int lo, int hi, int depth_limit)
    {
      while (hi-lo > size_threshold)
      {
        if (depth_limit == 0)
        {
          heapsort(a, lo, hi);
          return;
        }
        depth_limit=depth_limit-1;
        int p=partition(a, lo, hi, medianof3(a, lo, lo+((hi-lo)/2)+1, hi-1));
        introsort_loop(a, p, hi, depth_limit);
        hi=p;
      }
      insertionsort(a, lo, hi);
    }

在这里，我尝试将其修改为：

  private static void introsort_loop (int[] a, int lo, int hi, int depth_limit)
    {
      if (hi-lo > size_threshold)
      {
        if (depth_limit == 0)
        {
          heapsort(a, lo, hi);
          return;
        }
        depth_limit=depth_limit-1;
        int p=partition(a, lo, hi, medianof3(a, lo, lo+((hi-lo)/2)+1, hi-1));
        introsort_loop(a, p + 1, hi, depth_limit);
        introsort_loop(a, lo , p-1 , depth_limit);
      }
      insertionsort(a, lo, hi);
    }

我做了两个修改，一个是我现在使用两个递归，第二个是我跳过了递归的枢轴元素，因为它已经在正确的位置。

无论有没有我的修改，程序似乎都运行良好。但我想知道为什么他们在大多数在线实现中使用单递归。

4

1 回答 1

2

许多快速排序的实现实际上确实使用单个递归和 while 循环作为节省空间和时间的技巧。

在数学上，快速排序算法看起来像这样：

 Partition elements.
 Quicksort(elements less than pivot)
 Quicksort(elements greater than pivot)

如果您注意到，在两个递归调用返回后没有需要执行的代码。

现在，想想如果你直接把这个伪代码翻译成真实代码会发生什么。最初调用快速排序时的原始堆栈帧将一直存在，直到对快速排序的两个子调用都返回。这意味着堆栈帧的内存将一直持续到整个算法运行完毕，这会占用大量空间。此外，如果快速排序遇到退化的情况（在 introsort 中不可能，但只等待一秒钟），那么您最终将触发堆栈溢出。

解决这个问题的一个聪明的方法是意识到上面对快速排序的描述实际上是适合尾调用消除的。也就是说，实现可以直接覆盖初始调用的参数，而不是第二次调用快速排序，然后坐在一个while循环中并重用堆栈帧中的空间。这最终显着减少了空间使用并消除了递归调用，递归调用（虽然不是非常昂贵）通常比 while 循环花费更多。通常，实现将在数组的两半中较小的一个上触发递归调用，并使用 while 循环来处理较大的调用，即使遇到退化情况也能保证空间使用 O(log n)。

您在上面列出的 introsort 实现看起来只是将这个技巧改编为适用于 introsort 而不是快速排序。一个递归调用与两个递归调用并不意味着该算法没有使用快速排序，而只是意味着它使用了一种标准的快速排序优化技术。

于 2015-08-25T19:20:42.860 回答