插入排序有什么问题？

Question

我正在尝试使用基于插入的排序算法对大型数据文件进行排序,代码运行正常,但输出不正确.我一遍又一遍地研究它完全无济于事,谁能看到我出错的地方？

public void sort(Comparable[] items) {
    for (int i = 1; i < items.length; i++) {
        Comparable temp = items[i];
        int j = i - 1;
        while (j >= 0 && items[j].compareTo(items[j]) > 0) {
            items[j + 1] = items[j];
            j = j - 1;
        }
        items[j] = temp;
    }
}

我制作的一个示例数据文件是......

2
1
3
5
9
6
7
4
8

显然输出应该是1,2,3,4 ... - 但我得到1 3 5 9 6 7 4 8 8

Answer 1

items[j].compareTo(items[j])应该是items[j].compareTo(temp),否则你只是将项目与自身进行比较 - 你需要将它与你想要插入的对象进行比较.

然后items[j] = temp;也会导致一个ArrayIndexOutOfBoundsException因为,在循环结束时,items[j]小于temp,或者j == -1,因此我们需要在之后的位置插入 - 最简单的修复只是将其更改为items[j+1] = temp;.