你好,我正在尝试编写 QuickSort 代码,但我总是遇到索引越界? 我的代码如下:
public class QuickSort
{
public void quickSort(ArrayList<Integer> A, int p, int r)
{
if (p < r) {
int q = partition(A, p, r);
quickSort(A, p, q - 1);
quickSort(A, q + 1, r);
}
}
public int partition(ArrayList<Integer> A, int p, int r) {
int x = A.get(r);
int i = p - 1;
for (int j = p ; j < r; j++) {
if (A.get(j) <= x) {
i++;
Collections.swap(A, A.get(i), A.get(j));
}
}
Collections.swap(A, A.get(i + 1), A.get(r));
return (i + 1);
}
}
我用的是书里的代码:《算法导论》
我正在尝试对 ArrayList
A 进行快速排序
public class TestDriver
{
public static void testQuick() {
//Laver et random array A
ArrayList<Integer> A = new ArrayList<>();
for (int i = 1; i <12; i++) {
A.add(i);
}
Collections.shuffle(A);
int n = A.size();
QuickSort qs = new QuickSort();
System.out.println("The Array");
System.out.println(A);
qs.quickSort(A, 0, (n - 1));
System.out.println("The Array after QuickSort");
System.out.println(A);
System.out.println("");
}
}
最佳答案
问题是 Collections.swap(A, A.get(i), A.get(j));
- 这将尝试使用 A.get 中的值(i)
作为列表中的索引,如果 i
的值大于 A.size()
,显然会抛出越界异常。
所以只用你想交换的位置替换它们:
Collections.swap(A, i, j);
和
Collections.swap(A, (i + 1), r);
关于java - QuickSort IndexOutOfBound 异常数组列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52647306/