logo标签列表

快速排序。如何选择枢轴元素？

javaalgorithmlanguage-agnosticquicksort
5

我了解了快速排序算法，但不知道如何选择枢轴元素。从教程中，我获取了快速排序的示例代码：

public void quicksort(int[] A, int left, int right) {
    int pivot = A[left + (right - left) / 2];
    int i = left;
    int j = right;
    while (i <= j) {
        while (A[i] < pivot) {
            i++;
        }
        while (A[j] > pivot) {
            j--;
        }
        if (i <= j) {
            exchange(i, j);
            i++;
            j--;
        }
    }

    if(left < j)
        quicksort(A,left,j);
    if(i < right)
        quicksort(A,i,right);
}

为什么我们选择使用 A[left + (right - left) / 2]; 做为轴点呢？

而不是 A[(right - left) / 2] 呢？

以 left 为基础打印中间索引。 - Grijesh Chauhan
2
为什么不呢？因为那样是不正确的。运行一些示例（手动或在调试器中）以查看原因。 - Oliver Charlesworth
@OliCharlesworth，你能解释一下为什么它是不正确的吗？ - WelcomeTo
@MyTitle 读取banarun的答案可能是不正确的。 - Grijesh Chauhan
6个回答
11
考虑 left=6, right=10，那么 (right-left)/2 是 2。你选择的元素不在子数组范围内？
在快速排序中，您可以选择从6到10之间的任何元素。但是，如果您选择第一个或最后一个元素，并且数组已排序，则您的算法可能需要 O(n ^2) 的运行时间。因此，始终最好选择中间元素。
5
假设left=3和right=9，那么right-left/2 = 3并不是中间值，而是6，即left + (right - left) / 2。（只是加上基准值left）。
感谢@Dukeling：
你可以简单地写成(left + right) / 2。
    left + (right-left)/2 
=>  2*left/2 + (right-left)/2    //multiply (left * 2/2)
=>  (2*left + right-left)/2 
=>  (left + right)/2
3
left + (right-left)/2 = 2*left/2 + (right-left)/2 = (2*left + right-left)/2 = (left + right)/2。 这段代码的翻译是将左侧值与右侧值之和除以二，即为左右两个值的平均数。在计算机编程中，通常使用此公式来确定一个范围的中间位置。 - Bernhard Barker
@Dukeling 哇！！有趣，谢谢：），我想在我的答案中添加。 - Grijesh Chauhan
3
如果left和right是整数，那么(left+right)/2不等同于left+(right-left)/2。使用left+right可能会导致整数溢出。 - banarun
@banarun 再学一点 :) 从数学上讲它们是相同的，但在抽象的计算机世界中它们可能不同。谢谢Banarun。 - Grijesh Chauhan
1
@banarun 是的，我很少对超过“1 073 741 824”个元素的数组进行排序。 - Bernhard Barker
2
@Dukeling：您可能会感兴趣了解这是Java的binarySearch内部存在多年的一个错误：http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582。 - Oliver Charlesworth
1
( left + right ) / 2

可能会由于溢出而导致错误。
假设 left = 1 和 right = INT_MAX，那么 ( left + right ) / 2 = 0，这是不正确的。这是由于溢出引起的，为了避免这种情况，我们选择 left + (right - left) / 2。数学上两个表达式都是选择中间元素的正确方法。
1

左边界 = 最小值 右边界 = 最大值 如何获取中间值？(最大值 - 最小值) / 2

基本上，它将数组的中间作为枢轴点进行搜索。

由于数组不是从0开始的，并且最小值不是一个固定的数字，因此您需要将最小值加到结果中 - 这就是当前数组的中间位置。

1
是的，我的错，忘记添加最小值了。 中间值实际上是（max-min）/2，但由于最小值不为0且可能会改变，因此需要加上最小值。感谢您在有人误解之前提醒我错误。 - Adam Cohen
1
也许你需要了解这个函数的意思：对数组A从索引left到索引right进行快速排序。而A[(right - left) / 2]是什么？也许它不是数组A中的一个元素。
0

实际上，选择一个枢轴元素是快速排序中最重要的部分之一。通常情况下，最优选择取决于您接收到的数组结构，而且通常很难找到适合每个数组的枢轴位置。

在这个特定的例子中，教程选择作为枢轴的元素是正在排序的段中间的元素，但可能没有特别的原因。

我通常选择段的最后一个元素 pivot = A[right]，只是为了避免算术错误。

1
始终选择最后一个元素会导致已排序数组的性能非常糟糕... - Oliver Charlesworth
1
这就是为什么我说选择取决于接收到的数组的结构... - cgledezma
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接