0

我正在学习考试（算法和数据结构），我正在努力quicksort工作，LinkedList但它给了我ListIndexOutOfBoundsException.

前段时间的作业，我用于straightinsertion排序ArrayList和Vector，现在我想了解QuickSort（我理论上是这样做的）LinkedList。我不太熟悉linkedlist，但应该不会太不同ArrayList？

public class Sort {

public static void quickSort(LinkedList<Oseba> a) {
    sort(a, 0, a.size() - 1); // this is line 16
}

public static void sort(LinkedList<Oseba> a, int l, int r) {
    int i = l;
    int j = r;

    Oseba x = a.get((l + r) / 2), w;

    do {
        while (a.get(i).mlajsi(x)) {
            ++i;
        }
        while (x.mlajsi(a.get(j))) { // this is line 31
            --j;
        }
        if (i <= j) {
            w = a.get(i);
            a.set(i, a.get(j));
            a.set(j, w);
            ++i;
            --j;
        }
    } while (i <= j);

    if (l < j) {
        sort(a, l, j);
    }

    if (i < r) {
        sort(a, i, r);
    }
}
}

Oseba意思是“一个人”，这是我为测试各种方法（如排序、比较）而制作的一个类

public class Oseba implements Comparable<Oseba> {

protected String priimekIme; //surnameName
protected int letoRojstva; //year of birth
protected Spol spol; //gender (enum)

public Oseba(String priimekIme, int letoRojstva, Spol spol) {
    this.priimekIme = priimekIme;
    this.letoRojstva = letoRojstva;
    this.spol = spol;
}

@Override
public int compareTo(Oseba o) {
    if (this.letoRojstva < o.letoRojstva) {
        return -1;
    } else if (this.letoRojstva > o.letoRojstva) {
        return 1;
    } else {
        return this.priimekIme.compareTo(o.priimekIme);
    }
}

public boolean mlajsi(Oseba o) { //younger
    return (o.letoRojstva - this.letoRojstva <= 0);
}

@Override
public String toString() {
    String s = priimekIme + ", " + spol.getKratko() + ", " + letoRojstva;
    return s;
}
}

这是我得到的错误：

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: -1, Size: 6
    at java.util.LinkedList.checkElementIndex(LinkedList.java:553)
    at java.util.LinkedList.get(LinkedList.java:474)
    at javaapplication1.Sort.sort(Sort.java:31)
    at javaapplication1.Sort.quickSort(Sort.java:16)
    at javaapplication1.JavaApplication1.main(JavaApplication1.java:55)
Java Result: 1

这种quicksort方法应该与Vectoror一起使用ArrayList，我不知道为什么它不会与 一起使用LinkedList？

谢谢！

4

2 回答 2

1

好吧，您不会在循环期间检查边界。

   while (a.get(i).mlajsi(x)) {
        ++i;
    }
    while (x.mlajsi(a.get(j))) { // this is line 31
        --j;
    }

应该

   while (i <= r && a.get(i).mlajsi(x)) {
        ++i;
    }
    while (j >= l && x.mlajsi(a.get(j))) { // this is line 31
        --j;
    }

和

} while (i <= j);

严格来说，还应该考虑到这一点i并且j在边界之内（但我认为这不是必需的）。它将解决异常问题，但我没有验证算法的正确性。

于 2013-01-25T14:39:55.760 回答
0

Java（以及一般的 OO）的一大规则是“代码到接口，而不是实现”。现在，您正在LinkedList对接口的实现进行编码List。保证此代码适用于任何 List ( , 等) 的唯一方法Vector是ArrayList更改​​您的声明。例如：

public static void quickSort(LinkedList<Oseba> a) {

应该成为

public static void quickSort(List<Oseba> a) {

与排序类似：

public static void sort(List<Oseba> a, int l, int r) {

现在，每当您声明一个人时，它应该如下所示：

List<Oseba> a = LinkedList<Oseba>();

但是在 的地方LinkedList，您可以替换任何其他类型的列表。

这并不能回答您的代码为什么会失败的问题——我认为 UmNyobe 的建议很好，尽管我没有对其进行测试——但它回答了你关于为什么此代码不像其他列表类型那样的次要问题. 这是因为您正在对实现进行编码，您应该在其中使用接口。

于 2013-01-25T14:52:27.690 回答