Java:LinkedList 上的 QuickSort 给了我异常

Question

我正在准备考试(算法和数据结构)，我正在尝试让quicksort适用于LinkedList，但它给了我ListIndexOutOfBoundsException.

前一段时间的作业，我使用了straightinsertion来排序ArrayList和Vector，现在我想了解QuickSor t(理论上我是这样做的)对于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 意思是“一个人”，它是我为测试各种方法(如排序、比较)而创建的类<​​/p>

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方法应该可以与Vector或ArrayList一起使用，我不知道为什么它不能与一起使用链表？

谢谢!

Answer 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在边界之内(但我认为这是没有必要的)。 会解决异常问题，但我没有验证算法的正确性。