Java中的Inplace Quicksort [英] Inplace Quicksort in Java
问题描述
为了刷新一些Java,我试图实现一个可以对整数数组进行排序的快速排序(inplace)算法。以下是我到目前为止的代码。您可以通过 sort(a,0,a.length-1)
调用它。
For refreshing some Java I tried to implement a quicksort (inplace) algorithm that can sort integer arrays. Following is the code I've got so far. You can call it by sort(a,0,a.length-1)
.
此代码显然失败(进入无限循环)如果两个'指针' i,j
将每个指向与数据透视表具有相同值的数组条目。 pivot元素 v
始终是当前分区中最右边的分区(索引最大的分区)。
This code obviously fails (gets into an infinite loop) if both 'pointers' i,j
point each to an array entry that have the same values as the pivot. The pivot element v
is always the right most of the current partition (the one with the greatest index).
但我无法弄清楚如何避免这种情况,是否有人看到了解决方案?
But I just cannot figure out how to avoid that, does anyone see a solution?
static void sort(int a[], int left, int right) {
if (right > left){
int i=left, j=right-1, tmp;
int v = a[right]; //pivot
int counter = 0;
do {
while(a[i]<v)i++;
while(j>0 && a[j]>v)j--;
if( i < j){
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
} while(i < j);
tmp = a[right];
a[right] = a[i];
a[i] = tmp;
sort(a,left,i-1);
sort(a,i+1,right);
}
}
推荐答案
这应该有用(将检查一点的正确性,它可以工作!):
This should work (will check for correctness in a bit, it works!):
编辑:我以前在错误检查中犯了一个错误。我忘了添加2个条件,这里是修改后的代码。
I previously made a mistake in error checking. I forgot to add 2 more conditions, here is the amended code.
public static void main (String[] args) throws java.lang.Exception
{
int b[] = {10, 9, 8, 7, 7, 7, 7, 3, 2, 1};
sort(b,0,b.length-1);
System.out.println(Arrays.toString(b));
}
static void sort(int a[], int left, int right) {
if (right > left){
int i=left, j=right, tmp;
//we want j to be right, not right-1 since that leaves out a number during recursion
int v = a[right]; //pivot
do {
while(a[i]<v)
i++;
while(a[j]>v)
//no need to check for 0, the right condition for recursion is the 2 if statements below.
j--;
if( i <= j){ //your code was i<j
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
//we need to +/- both i,j, else it will stick at 0 or be same number
}
} while(i <= j); //your code was i<j, hence infinite loop on 0 case
//you had a swap here, I don't think it's needed.
//this is the 2 conditions we need to avoid infinite loops
// check if left < j, if it isn't, it's already sorted. Done
if(left < j) sort(a,left,j);
//check if i is less than right, if it isn't it's already sorted. Done
// here i is now the 'middle index', the slice for divide and conquer.
if(i < right) sort(a,i,right);
}
}
基本上我们确保如果i / j的值与pivot相同,我们也交换值,并且突破递归。
Basically we make sure that we also swap the value if the value of i/j is the same as the pivot, and break out of the recursion.
此外还检查了伪代码的长度,好像我们有一个只有1个项目的数组已经排序了(我们忘记了基本情况),我认为我们需要它,但是因为你传入了索引和整个数组,而不是子数组,我们只增加i和j所以算法不会坚持0(它们已经完成排序)但仍然继续排序1的数组。:)
Also there was a check in the pseudocode for the length, as if we have an array of just 1 item it's already sorted (we forgot the base case), I thought we needed that but since you pass in the indexes and the entire array, not the subarray, we just increment i and j so the algorithm won't stick at 0 (they're done sorting) but still keep sorting an array of 1. :)
另外,我们必须添加2个条件来检查数组是否已经为递归调用排序。没有它,我们将永远排序已排序的数组,因此另一个无限循环。看看我是如何添加检查,如果留下小于j,如果我小于正确。此外,在传递i和j的那一点上,我实际上是我们为分而治之分裂的中间指数,而j将是中间值之前的值。
Also, we had to add 2 conditions to check if the array is already sorted for the recursive calls. without it, we'll end up sorting an already sorted array forever, hence another infinite loop. see how I added checks for if left less than j and if i less than right. Also, at that point of passing in i and j, i is effectively the middle index we split for divide and conquer, and j would be the value right before the middle value.
它的伪代码取自 RosettaCode :
function quicksort(array)
if length(array) > 1
pivot := select any element of array
left := first index of array
right := last index of array
while left ≤ right
while array[left] < pivot
left := left + 1
while array[right] > pivot
right := right - 1
if left ≤ right
swap array[left] with array[right]
left := left + 1
right := right - 1
quicksort(array from first index to right)
quicksort(array from left to last index)
参考:此 SO问题
同时阅读这是一个快速的复习,它与oridnary while循环实现不同
这很有趣:)
这篇关于Java中的Inplace Quicksort的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!