快速排序：选择枢轴

StackOverflow https://stackoverflow.com/questions/164163

题

当实现快速排序时，你必须做的事情之一就是选择一个枢轴。但是当我查看下面的伪代码时，不清楚应该如何选择枢轴。列表的第一个元素？还有别的事吗？

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

有人可以帮助我理解选择支点的概念以及不同的场景是否需要不同的策略。

有帮助吗？

解决方案

选择随机数据会最大限度地减少您遇到最坏情况O（n 2 ）性能的可能性（总是选择第一个或最后一个会导致几乎排序或接近逆转的最坏情况性能分类数据）。在大多数情况下，选择中间元素也是可以接受的。

此外，如果您自己实现此功能，则有一些算法的版本可以就地工作（即不创建两个新列表然后连接它们）。

其他提示

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

更新：将评论拉入答案。

麦克斯 断言：

“3 的中位数”不是第一个最后一个中间值。随机选择三个指标，取其中的中间值。重点是确保您对枢轴的选择不是确定性的 - 如果是确定性的，则可以很容易地生成最坏情况的数据。

我对此回应：

  • 霍尔三中位数划分查找算法分析 (1997) 作者：P Kirschenhofer、H Prodinger、C Martínez 支持您的论点（“三的中位数”是三个随机项目）。

  • 有一篇文章描述于 门户网站acm.org 这是关于 Hannu Erkiö 的《三中位数快速排序的最坏情况排列》，发表于《计算机杂志》，第 27 卷，第 3 期，1984 年。[2012年2月26日更新：得到了文本 文章. 。第 2 节“算法”开始：'通过使用 A[L:R] 的第一个、中间和最后一个元素的中值，在大多数实际情况下可以实现有效划分为大小相当相等的部分。' 因此，它正在讨论第一个-中间-最后一个 Mo3 方法。]

  • 另一篇有趣的短文是 M 写的。D .麦克罗伊, “快速排序的杀手对手”, ，发表于《软件实践与经验》，卷。29(0), 1–4 (0 1999)。它解释了如何使几乎所有快速排序都表现出二次函数。

  • AT&T 贝尔实验室技术杂志，1984 年 10 月“构建工作排序例程的理论与实践”指出“霍尔建议围绕几个随机选择的行的中位数进行划分。Sedgewick [...] 建议选择第一个 [...] 最后一个 [...] 和中间的中位数”。这表明“三中位数”的两种技术在文献中都是已知的。（2014年11月23日更新：该文章似乎可以在 IEEE探索 或来自 威利 — 如果您有会员资格或准备支付费用。）

  • “设计排序函数” J L Bentley 和 M D McIlroy 于 1993 年 11 月发表在 Software Practice and Experience，第 23(11) 卷上，对这些问题进行了广泛的讨论，他们选择了部分基于数据集大小的自适应分区算法。对于各种方法的权衡有很多讨论。

  • 在谷歌上搜索“三的中位数”对于进一步跟踪非常有效。

感谢您的信息;我之前只遇到过确定性的“三中位数”。

嘿，我刚刚上课了。

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

但是，选择任意元素会冒大规模将n数组分成两个大小为1和n-1的数组的风险。如果你经常这样做，你的快速排序就有可能成为O（n ^ 2）。

我看到的一个改进是挑选中位数（第一，最后，中期）; 在最坏的情况下，它仍然可以转到O（n ^ 2），但概率上，这是一种罕见的情况。

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

如果您仍然遇到问题，请转到中间路线。

永远不要选择一个固定的数据透视 - 这可能会被攻击以利用你的算法的最坏情况O（n ^ 2）运行时，这只是在寻找麻烦。 Quicksort的最坏情况运行时发生在分区导致一个1个元素的数组和一个n-1个元素的数组时。假设您选择第一个元素作为分区。如果有人向您的算法提供递减顺序的数组，则您的第一个数据透视图将是最大的，因此数组中的其他所有内容都将移动到其左侧。然后当你递归时，第一个元素将再次成为最大元素，所以再一次将所有内容放在它的左边，依此类推。

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

如果你绝对想要保证算法的O（nlgn）运行时间，那么用于查找数组中值的5列方法在O（n）时间运行，这意味着快速排序的递归方程在最坏的情况是T（n）= O（n）（找到中位数）+ O（n）（分区）+ 2T（n / 2）（左右递归。）通过主定理，这是O（n lg n）。但是，常数因素将是巨大的，如果最坏情况下性能是您的主要考虑因素，请使用合并排序，它平均比快速排序慢一点，并保证O（nlgn）时间（并且会更快）比这个跛脚中位数快速排序）。

中位数算法中位数解释

不要试图过于聪明并结合旋转策略。如果你通过选择中间的第一个，最后一个和一个随机指数的中位数，将中位数3与随机支点相结合，那么你仍然会受到许多发送三次方的中位数的分布的影响（所以它实际上比普通随机支点）

例如，管风琴分布（1,2,3 ... N / 2..3,2,1）首先和最后都是1，随机指数将是一些大于1的数字，取中位数为1（无论是第一个还是最后一个）你都会得到一个非常不平衡的分区。

完全取决于数据的排序方式。如果您认为它是伪随机的，那么您最好的选择是选择随机选择或选择中间。

如果要对随机可访问的集合（如数组）进行排序，通常最好选择物理中间项。有了这个，如果数组已经准备好排序（或接近排序），两个分区将接近均匀，你将获得最佳速度。

如果您只对线性访问（如链接列表）进行排序，则最好选择第一项，因为它是访问速度最快的项目。但是，如果列表已经排序，那么你就搞砸了 - 一个分区总是为空，另一个分区就是一切，产生了最糟糕的时间。

但是，对于链接列表，选择除第一个之外的任何内容，只会使事情变得更糟。它选择列表列表中的中间项，你必须在每个分区步骤中逐步执行它 - 添加一个O（N / 2）操作，完成logN次，使总时间为O（1.5 N * log N）如果我们知道列表在我们开始之前已经有多长时间了 - 通常我们不会这样做，我们必须一步一步地计算它们，然后逐步找到中间位置，然后逐步完成第三次做实际分区：O（2.5N * log N）

将快速排序分为三个部分更容易实现此目的

  1. 交换或交换数据元素功能
  2. 分区功能
  3. 处理分区

    4. 它只比一个长函数略微无效，但更容易理解。

    代码如下：

    /* 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（n ^ 2）一样最差。这是一种选择枢轴元素的智能方法 - 1.选择数组的第一个，中间的，最后一个元素。 2.比较这三个数字，找出大于1且小于其他数字的数字，即中位数。 3.将此元素设为枢轴元素。

通过这种方法选择枢轴将阵列分成近两半，因此复杂性 减少到O（nlog（n））。

平均而言，3的中位数对小n来说是好的。对于较大的n，5的中位数更好一些。 ninther，即“三个三个中位数的中位数”。对于非常大的n来说甚至更好。

采样越高，n越大越好，但随着样本量的增加，改善速度会急剧下降。而且你会产生抽样和分类样本的开销。

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

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

在一个真正优化的实现中，选择数据透视的方法应该取决于数组大小 - 对于大型数组，花费更多时间选择一个好的数据透镜是值得的。如果不进行全面分析，我会猜测“O（log（n））元素的中间值”。是一个很好的开始，这有额外的好处，不需要任何额外的内存：在较大的分区和就地分区上使用尾调用，我们几乎在每个阶段使用相同的O（log（n））额外内存算法。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top