Java 插入排序算法从数组后面开始

Question

所以我一直在尝试编写插入排序算法，以便将值插入到数组的后面而不是前面（将最大值放在后面而不是将最小值放在前面）并且我一直无法确定我是否做对了。如果有人能告诉我我的想法是否正确，那就太好了。这是我的代码，它似乎没有像我想要的那样工作：

public static void insertionSort(Comparable[] item, int size) {
    for (int k = size - 1; k > 0; k--)
        insertInOrder(item, k);
}

private static void insertInOrder(Comparable[] item, int m) {
    Comparable save = item[m];
    for (; m > 0 && item[m-1].compareTo(save) > 0; m--)
        item[m] = item[m - 1];
    item[m] = save;
}

Answer 1

您的代码有两个问题。这是固定版本：

public static void insertionSort(Comparable[] item, int size) {
    // Changed to k >= 0, otherwise we would have ignored the 0th
    // element and not move it to higher positions in the array
    for (int k = size - 1; k >= 0; k--)
        insertInOrder(item, k, size);
}

// Added size as a parameter
private static void insertInOrder(Comparable[] item, int m, int size) {
    Comparable save = item[m];
    // This loop needs to count upward, because you
    // want to move large values towards the back
    for (; m + 1 < size && item[m+1].compareTo(save) < 0; m++)
        item[m] = item[m + 1];
    item[m] = save;
}

补充说明：

通常我们将数组的名称复数化，即：Comparable[] items.
考虑对 Comparable 类型使用泛型。
下次在 Code Review Stack Exchange 上提问。

Java 插入排序算法从数组后面开始

Java insertion sort algorithm from the back of the array

java

algorithm

insertion-sort