gpt4 book ai didi

java - 在 Java 中就地快速排序

转载 作者:搜寻专家 更新时间:2023-11-01 02:24:14 24 4
gpt4 key购买 nike

为了刷新一些 Java,我尝试实现一种可以对整数数组进行排序的快速排序(就地)算法。以下是我到目前为止的代码。您可以通过 sort(a,0,a.length-1) 调用它。

如果两个“指针”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 .

关于java - 在 Java 中就地快速排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29609909/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com