继罗伯特S​​edwick从快速排序部分算法书中的文字。

Following text from quick sort section in algorithms book by Robert Sedwick.

通过选择从左侧的阵列，中，右的三要素中，我们可以将哨兵到这个方案。排序三个要素，然后在中间交换一个 A [R-1] ，然后再运行 A分区算法[1 + 1] ，...，A [R-2] 。这种改进被称作3方法的中位数。

By choosing the three elements from the left, middle, and right of the array, we can incorporate sentinels into this scheme. Sort three elements, then exchange one in the middle with a[r-1], and then run the partitioning algorithm on a[l+1],...,a[r-2]. This improvement is called the median of three method.

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

The median of three method helps quick sort in three ways.

有使最坏的情况下更不可能发生在任何实际的排序。对于排序采取 O（N ^ 2）时，三分之二的检查必须是中最​​大或文件中的最小元素间的三大要素，而本次活动必须始终发生最彻底的分区。

It makes the worst case much more unlikely to occur in any actual sort. For the sort to take O(N^2) time, two out of the three elements examined must be among the largest or among the smallest elements in the file, and this event must happen consistently thorough most of the partitions.

有省去了一个前哨键分割，因为这个功能由服务该分区之前被检查的三要素中的一个。

It eliminates the need for a sentinel key for partitioning, because this function is served by one of the three elements that are examined before partitioning.

它由5％降低算法的总平均运行时间。

It reduce the total average running time of algorithm by about 5 percent.

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); }   

我在上面的文字问题，可以用简单的例子任何一种解释

My questions on above text, Can any one explain with simple example

什么是笔者通过意味着最坏的情况下更不可能发生在任何实际的排序。对于排序取N多的时间，三分之二的检查必须是其中最大的三要素？

What does author mean by "worst case much more unlikely to occur in any actual sort. For the sort to take N square time, two out of the three elements examined must be among the largest" ?

什么是笔者的它省去了一个定点键分区是什么意思？

What does author mean by "It eliminates the need for a sentinel key for partitioning" ?

在上面的程序是什么，我们正在实现在1号线，2，3，4这是在评论上述code？

In above program what we are achieving in line 1, 2, 3, and 4 which is commented in above code?

感谢您的时间和帮助！

推荐答案

快速排序算法的强度是将数据分割成两半，然后排序每一半，合并的结果。这种行为是什么给它一个O（N日志N）的复杂性。然而，这是基于事实的时候，当你除以一半的数据你实际上分割了一半。然而，这并不总是正确的。你不只是除数组，你是分割成两部分，但每个元素进行比较，以分隔件（比如P）。如果元素是小于或等于为P然后它进入左子阵列中否则就是进入右子阵列中。所以子阵列的尺寸在很大程度上依赖分隔元件上。如果P是等于所述阵列中的最大或最小值，那么所述子阵列中的一个将是空的，而快速排序将获得什么从分相。如果这种情况持续下去，每次则算法的运行时间变成了O（N ^ 2）

The strength of the quicksort algorithm is that is divides the data in half and then sorts each half and merges the results. This behaviour is what gives it an O(N log N) complexity. However this is based on the fact when when you divide that data in half you actually divide it in half. However this is not always true. You aren't just dividing the array, you are partitioning into two pieces but comparing each element to the partition element (say P). If an element is less than or equal to P then it goes in the left sub-array otherwise is goes in the right sub-array. So the size of the sub-arrays is heavily dependent on the partition element. If P is equal to the largest or smallest value in the array then one of the sub-arrays will be empty and the quicksort will gain nothing from the "divide phase". If this continues each time then the running time of the algorithm becomes O(N^2)

的中间的三个方法prevent从通过使三个选择元素的中间值元素作为阵列的最大或最小元素分隔元件。

The "median of three" methods prevent the partition element from being the largest or smallest element of the array by making it the middle valued element of three chosen elements.

在code四号位线被有效地整理到位三个要素，选择中间的一个作为新的分区。如果你要比较三个要素来确定位数，你还不如在同一时间对它们进行排序。

The fours lines in the code are effectively sorting three elements in place and choosing the middle one as the new partition. If you are going to compare three elements to determine the median you might as well sort them at the same time.