在我的quickSort算法java中更改pivot
我已经实现了一个有效的quickSort算法，使用数组中的第一个元素作为枢轴，如下所示：
public int[] quickSort( int[] a, int start, int end){
int l = start;
int r = end;
int pivotIndex = start; //<---- first element in the array as pivot!
// must be at least two elements
if ( end - start >= 1){
// set pivot
int pivot = a[pivotIndex];
while ( r > l ){
// scan from the left
while ( a[l] <= pivot && l <= end && r > l ){
l++;
}
while ( a[r] > pivot && r >= start && r >= l){
r--;
}
if ( r > l ){
this.swap(a, l, r);
}
}
this.swap(a, pivotIndex, r);
System.out.println("calling quickSort on " + start + " and " + (r-1));
quickSort(a, pivotIndex, r - 1); // quicksort the left partition
System.out.println("calling quickSort on " + (r+1) + " and " + end);
quickSort(a, r + 1, end); // quicksort the right partition
} else {
return a;
}
return a;
} 这很好用，但如果我将pivotIndex更改为int pivotIndex = end;，我会得到以下结果：
run:
2, 8, 7, 1, 3, 5, 6, 4,
2, 8, 7, 1, 3, 5, 6, 4,
swapping l:8 and r:4
2, 4, 7, 1, 3, 5, 6, 8,
swapping l:7 and r:3
2, 4, 3, 1, 7, 5, 6, 8,
swapping l:8 and r:1
calling quickSort on 0 and 2
calling quickSort on 4 and 7
2, 4, 3, 8, 7, 5, 6, 1,
swapping l:7 and r:1
2, 4, 3, 8, 1, 5, 6, 7,
swapping l:7 and r:1
calling quickSort on 4 and 3
calling quickSort on 5 and 7
2, 4, 3, 8, 7, 5, 6, 1,
swapping l:5 and r:1
2, 4, 3, 8, 7, 1, 6, 5,
swapping l:5 and r:1
calling quickSort on 5 and 4
calling quickSort on 6 and 7
2, 4, 3, 8, 7, 5, 6, 1,
swapping l:6 and r:1
2, 4, 3, 8, 7, 5, 1, 6,
swapping l:6 and r:1
calling quickSort on 6 and 5
calling quickSort on 7 and 7
2, 4, 3, 8, 7, 5, 6, 1,
BUILD SUCCESSFUL (total time: 1 second)如何使算法与任意索引0 to a.length一样使用pivotIndex
回答 3
Stack Overflow用户
发布于 2012-03-04 04:36:21
在开始排序之前，您可以简单地将您选择的轴心与数组中的第一个元素交换，这样它就会像以前一样工作。
int l = start;
int r = end;
this.swap(a, choosePivot(), start);
int pivotIndex = start; Stack Overflow用户
发布于 2012-03-03 22:44:29
如果您选择从旋转任意元素开始，则必须更改分区循环的行为。请参见以下代码：
/* Selecting the pivot to be a random-ish element
and pivotIndex to be beginning, since we don't know
where it will be until we loop through the list */
int pivot = a[someInt];
int pivotIndex = begin-1;
//have to keep track of where the pivot actually is in the list
int currentPivotIndex = someInt;
for(int i = begin; i <= end; i++) {
if(a[i] <= pivot) {
//for each element less than the pivot
//the pivotIndex moves by one
pivotIndex++;
//place the element to the left of the pivot
this.swap(a, pivotIndex, i);
//update currentPivotIndex if needed
if(a[pivotIndex] == pivot) {
currentPivotIndex = pivotIndex;
}
}
}
//put the pivot in its place
this.swap(a, pivotIndex, currentPivotIndex);Stack Overflow用户
发布于 2012-03-03 22:24:40
这是一些奇怪的行为，很可能是因为您的pivot元素参与了分区。
输出的第一行是swapping l:8 and r:4，但它应该是swapping l:8 and r:3。因为4是枢轴元素，它既不属于左边的分区，也不属于右边的分区。它是分区中间的元素。它必须在分区过程中被隔离。
若要解决此问题，请在选择轴后将其移动到末尾。也就是说，首先，用数组的最后一个元素替换pivot。因此，您可以将其与分区过程隔离。然后使用l = start and r = end - 1启动while循环，因为end当前是pivot。别管它了。完成分区后，恢复两个分区中间的pivot。中间是l和r的交汇点。
我相信遵循上面的方法可以解决你的问题。如果没有，请告诉我。
虽然不是直接相关的，但是您对pivot元素的选择对快速排序的性能有很大的影响。在目前的版本中，很可能会遇到最坏的情况(O(n^2))。最简单的是，你可以随机选择，这会带来很高概率的O(nlogn)复杂度。
https://stackoverflow.com/questions/9546645
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号