快速排序: 选择支点

在实现 Quicksort 时，您必须做的事情之一是选择一个轴心。但是，当我查看下面这样的伪代码时，我不清楚应该如何选择枢轴。列表的第一个元素？还有别的事吗？

 function quicksort(array)
var list less, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return concatenate(quicksort(less), pivot, quicksort(greater))

有没有人能帮我理解选择支点的概念，以及不同的情景是否需要不同的策略。

181097 次浏览
小开
最佳答案

选择一个随机的轴心可以最小化遇到最坏情况 O (n2)性能的可能性(总是选择第一个或最后一个会导致接近排序或接近反向排序的数据的最坏情况性能)。在大多数情况下，选择中间元素也是可以接受的。

另外，如果您自己实现这个，那么就有适当的算法版本(即不需要创建两个新列表，然后将它们连接起来)。

小开

这取决于你的要求。随机选择一个轴心会使创建一个产生 O (N ^ 2)性能的数据集变得更加困难。“三中位数”(第一，最后，中间)也是一种避免问题的方法。不过，要注意比较的相对性能; 如果比较代价高昂，那么 Mo3随机进行的比较比选择(单个枢轴值)多。比较数据库记录的成本可能很高。

更新: 回复评论。

Mdkess 断言:

“3的中位数”不是倒数第一个中位数。选择三个随机索引，取其中值。关键是要确保您的枢轴选择不是确定性的——如果是确定性的，那么可以非常容易地生成最坏情况下的数据。

我回答说:

谢谢你提供的信息; 我以前只遇到过确定性的“三分之一”。

小开

如果要对随机访问的集合(如数组)进行排序，通常最好选择物理中间项。通过这种方法，如果数组已经排序完毕(或者几乎排序完毕) ，那么这两个分区将接近于偶数，您将获得最佳速度。

如果您只使用线性访问(如链表)对某些内容进行排序，那么最好选择第一个项，因为它是访问速度最快的项。然而，在这里，如果列表已经排序，那么您就完蛋了——一个分区将始终为 null，而另一个分区具有所有内容，从而产生最糟糕的时间。

然而，对于一个链表来说，除了第一个链表，选择其他的链表只会让事情变得更糟。它选择一个列表中的中间项，你必须在每个分区步骤中逐步通过它——添加一个 O (N/2)操作，这个操作执行 logN 乘以总时间 O (1.5 N * log N) ，如果我们在开始之前知道列表有多长的话——通常我们不知道，所以我们必须一步一步地通过来计算它们，然后一步一步地通过一半来找到中间，然后一步一步地通过第三次来完成实际的分区: O (2.5 N * log N)

小开

这完全取决于您的数据从一开始就是如何排序的。如果你认为它将是伪随机的，那么你最好的选择是要么选择一个随机选择或选择中间。

小开

我刚教完这门课。

有几种选择。
简单: 选择范围中的第一个或最后一个元素 更好: 选择范围中间的项目。(对于部分排序的输入更好)

但是，选择任何任意的元素都有将大小为 n 的数组分割为大小为1和 n-1的两个数组的风险。如果你经常这样做，你的快速排序冒着变成 O (n ^ 2)的风险。

我看到的一个改进是选择中间值(第一，最后，中间) ; 在最坏的情况下，它仍然可以到 O (n ^ 2) ，但概率上，这是一个罕见的情况。

对于大多数数据，选择第一个或最后一个就足够了。但是，如果您发现经常遇到最糟糕的情况(部分排序的输入) ，第一个选项将是选择中心值(这对于部分排序的数据来说是一个统计上很好的支点)。

如果你仍然遇到问题，那么走中间路线。

小开

永远不要选择一个固定的枢轴-这可能会被攻击，利用您的算法的最坏情况 O (n2)运行时，这只是自找麻烦。当分区产生一个包含1个元素的数组和一个包含 n-1个元素的数组时，就会出现快速排序的最坏情况运行时。假设您选择第一个元素作为分区。如果有人按照递减顺序将数组提供给您的算法，那么您的第一个枢轴将是最大的，因此数组中的其他所有内容都将移动到它的左边。然后，当您递归时，第一个元素将再次成为最大的元素，因此再次将所有元素放在它的左边，以此类推。

更好的技术是 3中位数法3中位数法，您可以随机选择三个元素，然后选择中间的元素。你知道你选择的元素不会是第一个或者最后一个，但是，根据中心极限定理，中间元素的分布是正常的，这意味着你将趋向于中间(因此，nlog (n) time)。

如果你绝对想保证算法的 O (nlog (n))运行时间，那么找到数组中值的 列为5的方法在 O (n)时间内运行，这意味着在最坏的情况下快速排序的递归方程将是:

T(n) = O(n) (find the median) + O(n) (partition) + 2T(n/2) (recurse left and right)

根据主定理，这是 O (nlog (n))。然而，常数因素将是巨大的，如果最糟糕的情况下性能是你的主要关注，使用合并排序，这只是一点点慢于快排平均，并保证 O (nlog (n))时间(将比这个蹩脚的中值快排快得多)。

中位数算法的中值解释

小开

不要试图变得过于聪明，并结合旋转策略。如果你把3的中位数和随机数结合起来，选择第一个、最后一个的中位数和中间的一个随机指数，那么你仍然容易受到许多发送中位数为3的二次分布的影响(所以它实际上比普通的随机数更糟糕)

例如管风琴分布(1,2,3... N/2。. 3,2,1)第一个和最后一个都是1，随机指数将是一些大于1的数字，取中位数给出1(第一个或最后一个) ，你会得到一个极不平衡的分区。

小开

这样做更容易将快排分为三个部分

  1. 交换或交换数据元素函数
  2. 配分函数
  3. 处理分区

它只比一个长函数稍微低效一些，但是更容易理解。

守则如下:

/* This selects what the data type in the array to be sorted is */


#define DATATYPE long


/* This is the swap function .. your job is to swap data in x & y .. how depends on
data type .. the example works for normal numerical data types .. like long I chose
above */


void swap (DATATYPE *x, DATATYPE *y){
DATATYPE Temp;


Temp = *x;        // Hold current x value
*x = *y;          // Transfer y to x
*y = Temp;        // Set y to the held old x value
};




/* This is the partition code */


int partition (DATATYPE list[], int l, int h){


int i;
int p;          // pivot element index
int firsthigh;  // divider position for pivot element


// Random pivot example shown for median   p = (l+h)/2 would be used
p = l + (short)(rand() % (int)(h - l + 1)); // Random partition point


swap(&list[p], &list[h]);                   // Swap the values
firsthigh = l;                                  // Hold first high value
for (i = l; i < h; i++)
if(list[i] < list[h]) {                 // Value at i is less than h
swap(&list[i], &list[firsthigh]);   // So swap the value
firsthigh++;                        // Incement first high
}
swap(&list[h], &list[firsthigh]);           // Swap h and first high values
return(firsthigh);                          // Return first high
};






/* Finally the body sort */


void quicksort(DATATYPE list[], int l, int h){


int p;                                      // index of partition
if ((h - l) > 0) {
p = partition(list, l, h);              // Partition list
quicksort(list, l, p - 1);        // Sort lower partion
quicksort(list, p + 1, h);              // Sort upper partition
};
};
小开

理想情况下，pivot 应该是整个数组中的中间值。 这将减少获得最差情况下性能的机会。

小开

在一个真正优化的实现中，选择枢轴的方法应该取决于数组的大小——对于大型数组，花更多的时间选择一个好的枢轴是值得的。如果不进行全面的分析，我认为“ O (log (n))元素的中间”是一个好的开始，而且这还有不需要任何额外内存的额外好处: 在更大的分区和就地分区上使用尾部调用，我们在算法的几乎每个阶段都使用相同的 O (log (n))额外内存。

小开

随着枢轴值的选择，快速排序的复杂度变化很大。例如，如果你总是选择第一个元素作为支点，算法的复杂度会变得和 O (n ^ 2)一样糟糕。这里有一个聪明的方法来选择枢轴元素- 选择数组的第一个、中间的、最后一个元素。 2. 比较这三个数字，找出大于一和小于另一个的数字，即中位数。 3. 把这个元素作为枢轴元素。

通过这种方法选择枢轴，可以将数组分成将近两半，从而增加了数组的复杂度 减少到 O (nlog (n))。

小开

平均来说，小 n 的中位数为3是好的，大 n 的中位数为5是好一点的。第九个，即“三个中位数的三个中位数的中位数”，对于非常大的 n 来说更好。

随着样品数量的增加，样品数量越高，效果越好，但是随着样品数量的增加，效果的提高速度明显放慢。而且您还要承担采样和分类样品的开销。

小开

我建议使用中间索引，因为它可以很容易地计算。

您可以通过舍入(array.length/2)来计算它。


提交答案