在 Java 中就地快速排序
Inplace Quicksort in Java
为了刷新一些 Java,我尝试实现一个可以对整数数组进行排序的快速排序(就地)算法。以下是我到目前为止的代码。您可以通过 sort(a,0,a.length-1)
.
来调用它
如果 'pointers' i,j
都指向一个与主元具有相同值的数组条目,则此代码显然会失败(进入无限循环)。枢轴元素 v
始终是当前分区的最右边(具有最大索引的那个)。
但我不知道如何避免这种情况,有人看到解决方案吗?
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);
}
}
在执行快速排序时,我强烈建议创建一个单独的分区方法,以使代码更易于理解(我将在下面展示一个示例)。除此之外,避免最坏情况 运行 时间的一个好方法是在执行快速排序之前对要排序的数组进行洗牌。我还使用第一个索引而不是最后一个作为分区项。
例如:
public static void sort (int[] a)
{
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
}
private static void sort(int[] a, int lo, int hi)
{
if (hi <= lo) return;
int j = partition(a, lo, hi) // the addition of a partitioning method
sort(a, lo, j-1);
sort(a, j+1, hi);
}
private static int partition(int[] a, int lo, int hi)
{
int i = lo, j = hi + 1, tmp = 0;
int v = a[lo];
while (true)
{
while (a[i++] < v) if (i == hi) break;
while (v < a[j--]) if (j == lo) break;
if (i >= j) break;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
tmp = a[lo];
a[lo] = a[j];
a[j] = temp;
return j;
}
最重要的是,如果您想要一个关于快速排序如何工作的非常好的示例(作为复习),请参阅 here。
这应该有效(稍后会检查正确性,有效!):
编辑:我之前在错误检查中犯了一个错误。我忘了再添加2个条件,这里是修改后的代码。
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);
}
}
This Code in the IDEOne online compiler
基本上 我们确保如果 i/j 的值与主元相同,我们也交换值,并跳出递归。
伪代码中还检查了长度,就好像我们有一个只有 1 个项目的数组,它已经排序了(我们忘记了基本情况),我想我们需要它,但由于您传入索引和整个数组,而不是子数组,我们只是递增 i 和 j,这样算法就不会停留在 0(它们已完成排序),但仍会继续对 1 的数组进行排序。 :)
此外,我们必须添加 2 个条件来检查数组是否已经为递归调用排序。没有它,我们将永远对一个已经排序的数组进行排序,因此会出现另一个无限循环。看看我是如何添加检查 if left less than j 和 if i less right 的。此外,在传入 i 和 j 时,i 实际上是我们分而治之的中间索引,j 将是中间值之前的值。
它的伪代码取自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 question
另读this for a quick refresher, it's implemented differently with an oridnary while loop
这很有趣 :)
这是我写的一些简单代码,没有初始化很多指针,并且以简单的方式完成了工作。
public int[] quickSort(int[] x ){
quickSortWorker(x,0,x.length-1);
return x;
}
private int[] quickSortWorker(int[] x, int lb, int ub){
if (lb>=ub) return x;
int pivotIndex = lb;
for (int i = lb+1 ; i<=ub; i++){
if (x[i]<=x[pivotIndex]){
swap(x,pivotIndex,i);
swap(x,i,pivotIndex+1);
pivotIndex++;
}
}
quickSortWorker(x,lb,pivotIndex-1);
quickSortWorker(x,pivotIndex+1,ub);
return x;
}
private void swap(int[] x,int a, int b){
int tmp = x[a];
x[a]=x[b];
x[b]=tmp;
}
为了刷新一些 Java,我尝试实现一个可以对整数数组进行排序的快速排序(就地)算法。以下是我到目前为止的代码。您可以通过 sort(a,0,a.length-1)
.
如果 'pointers' i,j
都指向一个与主元具有相同值的数组条目,则此代码显然会失败(进入无限循环)。枢轴元素 v
始终是当前分区的最右边(具有最大索引的那个)。
但我不知道如何避免这种情况,有人看到解决方案吗?
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);
}
}
在执行快速排序时,我强烈建议创建一个单独的分区方法,以使代码更易于理解(我将在下面展示一个示例)。除此之外,避免最坏情况 运行 时间的一个好方法是在执行快速排序之前对要排序的数组进行洗牌。我还使用第一个索引而不是最后一个作为分区项。
例如:
public static void sort (int[] a)
{
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
}
private static void sort(int[] a, int lo, int hi)
{
if (hi <= lo) return;
int j = partition(a, lo, hi) // the addition of a partitioning method
sort(a, lo, j-1);
sort(a, j+1, hi);
}
private static int partition(int[] a, int lo, int hi)
{
int i = lo, j = hi + 1, tmp = 0;
int v = a[lo];
while (true)
{
while (a[i++] < v) if (i == hi) break;
while (v < a[j--]) if (j == lo) break;
if (i >= j) break;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
tmp = a[lo];
a[lo] = a[j];
a[j] = temp;
return j;
}
最重要的是,如果您想要一个关于快速排序如何工作的非常好的示例(作为复习),请参阅 here。
这应该有效(稍后会检查正确性,有效!):
编辑:我之前在错误检查中犯了一个错误。我忘了再添加2个条件,这里是修改后的代码。
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);
}
}
This Code in the IDEOne online compiler
基本上 我们确保如果 i/j 的值与主元相同,我们也交换值,并跳出递归。
伪代码中还检查了长度,就好像我们有一个只有 1 个项目的数组,它已经排序了(我们忘记了基本情况),我想我们需要它,但由于您传入索引和整个数组,而不是子数组,我们只是递增 i 和 j,这样算法就不会停留在 0(它们已完成排序),但仍会继续对 1 的数组进行排序。 :)
此外,我们必须添加 2 个条件来检查数组是否已经为递归调用排序。没有它,我们将永远对一个已经排序的数组进行排序,因此会出现另一个无限循环。看看我是如何添加检查 if left less than j 和 if i less right 的。此外,在传入 i 和 j 时,i 实际上是我们分而治之的中间索引,j 将是中间值之前的值。
它的伪代码取自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 question
另读this for a quick refresher, it's implemented differently with an oridnary while loop
这很有趣 :)
这是我写的一些简单代码,没有初始化很多指针,并且以简单的方式完成了工作。
public int[] quickSort(int[] x ){
quickSortWorker(x,0,x.length-1);
return x;
}
private int[] quickSortWorker(int[] x, int lb, int ub){
if (lb>=ub) return x;
int pivotIndex = lb;
for (int i = lb+1 ; i<=ub; i++){
if (x[i]<=x[pivotIndex]){
swap(x,pivotIndex,i);
swap(x,i,pivotIndex+1);
pivotIndex++;
}
}
quickSortWorker(x,lb,pivotIndex-1);
quickSortWorker(x,pivotIndex+1,ub);
return x;
}
private void swap(int[] x,int a, int b){
int tmp = x[a];
x[a]=x[b];
x[b]=tmp;
}