java 快速排序。如何选择枢轴元素？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17442139/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Quicksort. How to choose pivot element?
提问by MyTitle
I read about quicksort algorithm and I don't understand how to choose pivot element. From tutorials I get example code of quciksort:
我阅读了快速排序算法，但我不明白如何选择枢轴元素。从教程中我得到了 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);
}
But why we choose pivot using this A[left + (right - left) / 2];?
但是为什么我们选择使用这个支点 A[left + (right - left) / 2];？
Why not A[(right - left) / 2]
为什么不 A[(right - left) / 2]
回答by banarun
Consider left=6, right=10, then (right-left)/2is 2. You are choosing an element which is not in the range of your sub-array?
考虑left=6, right=10，然后(right-left)/2是 2。您正在选择一个不在您的子数组范围内的元素？
You can choose any element between 6 and 10 as for quick sort.But if you choose first or last element and if the array is sorted, then your algorithm may go to O(n^2) running time. So it is always better to choose middle element.
对于快速排序，您可以选择 6 到 10 之间的任何元素。但是如果您选择第一个或最后一个元素，并且如果数组已排序，那么您的算法可能会运行时间为 O(n^2)。所以选择中间元素总是更好。
回答by Grijesh Chauhan
Suppose left=3and right=9then right-left/2 = 3that is not middle but its 6that is = left + (right - left) / 2. (just added base value left).
假设left=3和right=9再right-left/2 = 3不是中间，但它6是= left + (right - left) / 2。（刚刚添加了基值left）。
Thanks to @Dukeling:
You can simple write (left + right) / 2.
感谢@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
回答by Adam Cohen
Left = minimum Right = maximum How do you get the middle? (Maximum - minimum) / 2
左 = 最小 右 = 最大 你是如何得到中间的？（最大值 - 最小值）/ 2
Basically it searches for the middle of the array as the pivot point.
基本上它搜索数组的中间作为枢轴点。
Since the array does not start from 0, and the minimum is not a constant number, you add the minimum to the result - and that's the middle of the current array.
由于数组不是从 0 开始，并且最小值不是常数，因此将最小值添加到结果中 - 这就是当前数组的中间部分。
回答by leiyufeng
may be you should understand this function means:quicksort the array A from index left to index right.And what is A[(right - left) / 2]?may be it is not an element of array A.
可能你应该明白这个函数的意思是：将数组 A 从索引左快速排序到索引右。A[(right - left) / 2] 是什么？可能它不是数组 A 的一个元素。
回答by ajaysaini
( left + right ) / 2
may cause error due to overflow.
可能会因溢出而导致错误。
Suppose left = 1& right = INT_MAXthen ( left + right ) / 2 = 0, which is incorrect. This is caused due to overflow and to avoid this we choose left + (right - left) / 2. Mathematically both expressions are correct to choose the middle element.
假设left = 1& right = INT_MAXthen ( left + right ) / 2 = 0，这是不正确的。这是由于溢出引起的，为了避免这种情况，我们选择了 left + (right - left) / 2。从数学上讲，选择中间元素的两个表达式都是正确的。
回答by cgledezma
Actually the selection of a pivot element is one of the most important parts of quicksort. An optimal selection usually depends on the structure of the arrays that you are receiving, and in general it is very hard to find a position for the pivot that suits every array.
实际上，枢轴元素的选择是快速排序最重要的部分之一。最佳选择通常取决于您接收的数组的结构，通常很难找到适合每个数组的枢轴位置。
In this particular example the tutorial is choosing as pivot the element in the middle of the segment being ordered, but probably there is no particular reason for doing so.
在这个特定的例子中，教程选择了要排序的段中间的元素作为主元，但可能没有特别的理由这样做。
Me, I usually choose the last element of the segment pivot = A[right], only to avoid errors in arithmetics.
我，我通常选择段的最后一个元素pivot = A[right]，只是为了避免算术错误。
