我已经编写了快速排序的代码,但它显示异常数组索引超出界限。当用C编写时,它可以正常工作,但在Java中它不起作用。请告诉我有什么问题。任何建议都是赞赏的。它是一种双向划分的标准CLRS算法。
package Sorting;
public class QuickSort {
public static void main(String arg[]) {
int a[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
Sort(a, 0, a.length - 1);
for (int i = 0; i < 9; i++) {
System.out.print(" " + a[i]);
}
}
private static void Sort(int[] a, int i, int j) {
// TODO Auto-generated method stub
if (i < j) {
int k = Partition(a, i, j);
Sort(a, i, k - 1);
Sort(a, k + 1, j);
}
}
private static int Partition(int[] a, int i, int j) {
// TODO Auto-generated method stub
int temp;
int x = a[j];
int l = i - 1;
for (int n = i; n < j; n++) {
if (a[n] >= x) {
l++;
temp = a[l];
a[l] = a[n];
a[n] = temp;
}
}
temp = a[x];
a[x] = a[l + 1];
a[l + 1] = temp;
return l + 1;
}
}
输出:9 3 5 7 4 1 6 2 8
你的代码中有一些小错误,下面是更新后的代码:
private static int Partition(int[] a, int i, int j) {
// TODO Auto-generated method stub
int temp;
int x = a[j];
int l = i - 1;
for (int n = i; n < j; n++) {
if (a[n] <= x) { /*******Condition was wrong******/
l++;
temp = a[l];
a[l] = a[n];
a[n] = temp;
}
}
temp = a[j]; /******a[j] not a[x] x is value of pivot element******/
a[j] = a[l + 1];
a[l + 1] = temp;
return l + 1;
}
在partition
:
for (int n = i; i < j; n++)
你可能指的是n<j
而不是i<j
。i
永远不变,所以i<j
总是正确的。n
最终变成9
。a[9]
不存在,所以
i
总是小于j
,因为i anj不会改变
for (int n = i; i < j; n++)
所以你有一个无限循环。