比较插入排序的两个（几乎相同的）实现；其中一个失败

Question

基本上我在非工作实现中用aData[i]替换了n。我错过了一些根本性的错误吗？第二次实施在相同的测试数据上失败。

通过实施：

static long[] sort(long[] aData) {
    for (int i = 1; i < aData.length; i++) {
        long n = aData[i];

        int j = i - 1;
        while (j >= 0 && aData[j] > n) {
            aData[j + 1] = aData[j];
            j--;
        }
        aData[j + 1] = n;
    }
    return aData;
}

实施失败：

static long[] sort(long[] aData) {
    for (int i = 1; i < aData.length; i++) {
        int j = i - 1;
        while (j >= 0 && aData[j] > aData[i]) {
            aData[j + 1] = aData[j];
            j--;
        }
        aData[j + 1] = aData[i];
    }
    return aData;
}

Answer 1

在 while 循环的第一次迭代中，j + 1 == i。所以当你写 aData[j + 1] = aData[j] 时，你在循环内改变了 aData[i] 的值。

在初始版本中，n在整个操作过程中是不变的。另请注意，使用 aData[i] 而不是 n 不太可能提高性能（如果有的话，它可能会更慢）。

比较插入排序的两个（几乎相同的）实现；其中一个失败

Comparing two (almost identical) implementations of Insertion Sort; one of them fails

java

insertion-sort