Java 插入排序 - 向下复制数组中的值

Question

我需要让这个插入排序函数从本质上将元素复制到右边，直到需要移动的值位于正确的位置，但是，对于我使用的代码，我通常最终会得到垃圾，并尝试了多次迭代，结果相同。我无能为力，因为我看不出为什么这不起作用。

public static void Sort(Comparable[] a) {
    int n = a.length;
    Comparable temp = 0;
    int x;
    // Starting with the element at index 1...
    for (int i = 1; i < n; i++) {
        // ...move to the left until we find one less
        // than the current element.
        for (int j = i; j > 0; j--) {
            if (less(a[j], a[j - 1]))
            {
                temp = a[j];
                for(x = j; x > 0 && less(temp, a[x]); x--)
                {
                    a[x] = a[x - 1];
                }

                a[x] = temp;
                //exch(a, j, j - 1);
            }
            else
                break;
        }
    }
}

less(a, b) 顺便检查是否 a < b。

Answer 1

在最内层循环的第一次迭代中，在这种情况下：x > 0 && less(temp, a[x]) 您正在检查您刚刚存储在 temp 中的值...是否小于您刚刚存储在 temp 中的值，参考以另一个名字。这将始终 return false，导致循环永远不会开始。最终结果是整个方法是一个代价高昂的空操作。如果你通过发送一个随机混乱的数组来测试它，你最终会得到这个数组，当它完成时仍然是随机混乱的。

要解决此问题，只需从该条件下的索引中减去 1，使其成为 x > 0 && less(temp, a[x - 1])。

我认为您的其余代码看起来是正确的，尽管带有 j 的循环是多余的并且可以删除。

Answer 2

这应该可以解决问题

public static void Sort(Comparable[] a) {
    int n = a.length;
    Comparable temp = 0;
    int x;
    // Starting with the element at index 1...
    for (int i = 1; i < n; i++) {
        // ...move to the left until we find one less
        // than the current element.
        for (int j = i; j > 0; j--) {
            if (less(a[j], a[j - 1]))
            {
                temp = a[j];
                for(x = j; x > 0 && less(temp, a[x-1]); x--)
                {
                    a[x] = a[x - 1];
                }

                a[x] = temp;
                //exch(a, j, j - 1);
            }
            else
                break;
        }
    }
}

Java 插入排序 - 向下复制数组中的值

Java Insertion Sort - copying values down array

java

insertion-sort