快速排序不排序
所以我试图创建一个快速排序方法,但是,它没有正确排序。这是我的输入和输出
原始数组:
80.0 10.0 50.0 70.0 60.0 90.0 20.0 30.0 40.0 0.0
排序数组:
0.0 30.0 20.0 80.0 40.0 60.0 70.0 10.0 90.0 50.0
我尝试将 for 循环更改为 for(int i = left; i < right; i++)
但现在输出是:
0.0 20.0 30.0 40.0 80.0 10.0 60.0 90.0 70.0 50.0
public static void sort(double[] a)
{
quickSort(a, 0, a.length-1);
}
public static void quickSort(double [] a, int left, int right)
{
if (left < right)
{
int pivotIndex = (left+right)/2;
int pos = partition(a,left,right,pivotIndex);
quickSort(a,left,pos-1);
quickSort(a,pos+1,right);
}
}
private static int partition(double [] a, int left,int right,int pivotIndex)
{
double temp = a[pivotIndex];
a[pivotIndex] = a[right];
a[right] = temp;
int pos = left;//represents boundary between small and large elements
for(int i = left; i < right-1; i++)
{
if (a[i] <= a[pivotIndex])
{
double temp2 = a[i];
a[i] = a[pos];
a[pos] = temp2;
pos++;
}
}
double temp3 = a[pivotIndex];
a[pivotIndex] = a[pos];
a[pos] = temp3;
return pos;
}
So I am trying to create a quicksort method, however, it is not sorting properly. Heres my input and output
Original array:
80.0 10.0 50.0 70.0 60.0 90.0 20.0 30.0 40.0 0.0
Sorted array:
0.0 30.0 20.0 80.0 40.0 60.0 70.0 10.0 90.0 50.0
I tried changing the for loop to for(int i = left; i < right; i++)
but now the output is:
0.0 20.0 30.0 40.0 80.0 10.0 60.0 90.0 70.0 50.0
public static void sort(double[] a)
{
quickSort(a, 0, a.length-1);
}
public static void quickSort(double [] a, int left, int right)
{
if (left < right)
{
int pivotIndex = (left+right)/2;
int pos = partition(a,left,right,pivotIndex);
quickSort(a,left,pos-1);
quickSort(a,pos+1,right);
}
}
private static int partition(double [] a, int left,int right,int pivotIndex)
{
double temp = a[pivotIndex];
a[pivotIndex] = a[right];
a[right] = temp;
int pos = left;//represents boundary between small and large elements
for(int i = left; i < right-1; i++)
{
if (a[i] <= a[pivotIndex])
{
double temp2 = a[i];
a[i] = a[pos];
a[pos] = temp2;
pos++;
}
}
double temp3 = a[pivotIndex];
a[pivotIndex] = a[pos];
a[pos] = temp3;
return pos;
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
这就是您想要做的:
我通过使用辅助
swap
方法使代码更加清晰。原始代码中有 3 个错误:This is what you want to do:
I made the code clearer by having a helper
swap
method. You had 3 bugs in the original code:更改
为
change
to