5

我阅读了快速排序算法，但我不明白如何选择枢轴元素。从教程中我得到了 quciksort 的示例代码：

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

但是为什么我们选择使用 this 的 pivot A[left + (right - left) / 2];呢？

为什么不A[(right - left) / 2]

4

6 回答 6

11

考虑left=6, right=10，然后(right-left)/2是 2。您正在选择一个不在您的子数组范围内的元素？

您可以选择 6 到 10 之间的任何元素进行快速排序。但是如果您选择第一个或最后一个元素并且数组已排序，那么您的算法可能会运行 O(n^2) 时间。所以最好选择中间元素。

于 2013-07-03T07:37:03.613 回答
5

假设left=3and right=9then right-left/2 = 3that 不是中间的，但它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
于 2013-07-03T07:34:29.193 回答
1

左 = 最小值 右 = 最大值 你如何得到中间？（最大 - 最小）/ 2

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

由于数组不是从 0 开始，并且最小值不是一个常数，因此您将最小值添加到结果中 - 这就是当前数组的中间值。

于 2013-07-03T07:34:25.047 回答
1

可能你应该理解这个函数的意思是：将数组 A 从索引左到索引右快速排序。而 A[(right - left) / 2] 是什么？可能它不是数组 A 的元素。

于 2013-07-03T07:40:32.293 回答
1 
( left + right ) / 2

可能会因溢出而导致错误。

假设left = 1& right = INT_MAXthen ( left + right ) / 2 = 0，这是不正确的。这是由于溢出引起的，为了避免这种情况我们选择 left + (right - left) / 2. 从数学上讲，这两个表达式对于选择中间元素都是正确的。

于 2015-02-26T16:50:12.977 回答
0

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

在这个特定的示例中，本教程选择了正在排序的段中间的元素作为枢轴，但可能没有特别的理由这样做。

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

于 2013-07-03T07:35:02.490 回答