2

以下来自 Robert Sedwick 的算法书中的快速排序部分的文本。

通过从数组的左侧、中间和右侧选择三个元素，我们可以将哨兵纳入该方案。对三个元素进行排序，然后将中间的一个与 交换，a[r-1]然后在 上运行分区算法a[l+1],...,a[r-2]。这种改进称为三方法中值。

三种方法的中位数有助于以三种方式快速排序。

  1. 它使最坏的情况在任何实际排序中都不太可能发生。为了使排序花费O(N^2)时间，所检查的三个元素中的两个必须在文件中最大或最小的元素中，并且该事件必须在大多数分区中始终如一地发生。

  2. 它消除了分区前哨键的需要，因为此功能由分区前检查的三个元素之一提供服务。

  3. 它将算法的总平均运行时间减少了大约 5%。

    template <class Item> 
void exch(Item &A, Item &B) 
      { Item t = A; A = B; B = t; } 

template <class Item> 
void compexch(Item &A, Item &B) 
      { if (B < A) exch(A, B); }

static const int M = 10;
template <class Item>
void quicksort(Item a[], int l, int r)
  {
    if (r-l <= M) return;
    exch(a[(l+r)/2], a[r-1]);  // line 1
    compexch(a[l], a[r-1]);   // line 2.
    compexch(a[l], a[r]);     // line 3.
    compexch(a[r-1], a[r]);   // line 4.
    int i = partition(a, l+1, r-1);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
  }

template <class Item>
void hybridsort(Item a[], int l, int r)
  { quicksort(a, l, r); insertion(a, l, r); }

我对上述文字的问题，任何人都可以用简单的例子来解释

  1. 作者所说的“在任何实际排序中都不太可能发生最坏的情况。对于需要 N 平方时间的排序，所检查的三个元素中有两个必须是最大的”是什么意思？

  2. 作者所说的“它消除了对分区的哨兵键的需要”是什么意思？

  3. 在上面的程序中，我们在上面代码中注释的第 1、2、3 和 4 行实现了什么？

感谢您的时间和帮助！

4

1 回答 1

3

快速排序算法的优势在于将数据分成两半，然后对每一半进行排序并合并结果。这种行为赋予了它 O(N log N) 的复杂性。然而，这是基于这样一个事实，当您将数据分成两半时，您实际上将其分成两半。然而，这并不总是正确的。您不仅要划分数组，还要将其划分为两部分，而是将每个元素与分区元素（例如 P）进行比较。如果一个元素小于或等于 P 则它进入左子数组，否则进入右子数组。所以子数组的大小很大程度上取决于分区元素。如果 P 等于数组中的最大值或最小值，则子数组之一将为空，并且快速排序不会从“除法阶段”中获得任何收益。

“三的中位数”方法通过使分区元素成为三个选定元素的中间值元素来防止分区元素成为数组的最大或最小元素。

代码中的四行有效地对三个元素进行了适当的排序，并选择中间的一个作为新的分区。如果您要比较三个元素以确定中位数，您不妨同时对它们进行排序。

于 2012-11-15T15:10:33.870 回答