algorithm - 使用三中位数的快速排序改进 Robert sedwick

Question

以下文本来自 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 行中实现了什么？

感谢您的时间和帮助!

Answer 1

快速排序算法的优点在于，它将数据分成两半，然后对每一半进行排序并合并结果。这种行为使其复杂度为 O(N log N)。然而，这是基于这样一个事实:当您将数据一分为二时，您实际上将其一分为二。然而这并不总是正确的。您不只是将数组划分，而是将其划分为两部分，并将每个元素与划分元素(例如 P)进行比较。如果一个元素小于或等于P，则它进入左子数组，否则进入右子数组。因此子数组的大小很大程度上取决于分区元素。如果 P 等于数组中的最大值或最小值，则子数组之一将为空，并且快速排序将不会从“除法阶段”获得任何结果。如果每次都这样，那么算法的运行时间就变成了 O(N^2)

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

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