1
傍晚。我正在做一些关于算法分析的项目。它关于quickSort，并将两种不同的分区算法转换为代码，然后在报告中进行比较。QuickSort分区提供例外
第一种算法是这样的：
To partition a[left…right] such that a[left…j–1] are all less than or
equal to a[j], and a[j+1…right] are all greater than or equal to a[j]:
1. Set pivot to a[left].
2. Set i = left + 1 and j = right.
3. While i ≤ j, repeat:
3.1. While i ≤ j and a[i] ≤ pivot, increment i.
3.2. While j ≥ i and a[j] ≥ pivot, decrement j.
3.3. If i < j, swap a[i] and a[j].
4. If j ≠ left, set a[left] to a[j], and a[j] to pivot.
5. Terminate with answer j
而且我用下面，这似乎没有错误编码它...
public class TestQuickSort {
public static int partition(Comparable[] a, int left, int right) {
Comparable p = a[left];
int i = left + 1;
int j = right;
while (i <= j) {
while (i <= j && a[i].compareTo(p) < 0) {
i++;
}
while (j >= i && a[j].compareTo(p) > 0) {
j--;
}
if (i < j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
if (j != left) {
a[left] = a[j];
a[j] = p;
}
return j;
}
public static void quickSort(Comparable[] a, int left, int right) {
// Sort a[left…right] into ascending order.
if (left < right) {
int p = partition(a, left, right);
quickSort(a, left, p - 1);
quickSort(a, p + 1, right);
}
}
public static void main(String[] args) {
// TODO code application logic here
Comparable[] a = {1, 2, 6, -9, 0};
quickSort(a, 0, a.length);
}
}
...直到我运行它，我遇到3例外
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5
at TestQuickSort.partition(TestQuickSort.java:22)
at TestQuickSort.quickSort(TestQuickSort.java:41)
at TestQuickSort.main(TestQuickSort.java:50)
Java Result: 1
有人可以帮我出来，我不明白为什么？这是我的while循环的问题吗？我应该使用不同类型的循环吗？
感谢任何能回复的人。