java - 我的插入排序有什么问题？

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;.