在 java 中编写插入排序算法

Question

我正在尝试在 Java 中实现插入排序。我觉得我的代码不太对劲。

public int[] sort(int[] unsorted) {
    int i, j, v;
    for (i = 1; i < unsorted.length - 1; i++) {
        v = unsorted[i];
        j = i;

        while (unsorted[j-1] > v && j >= 1) {
            unsorted[j] = unsorted[j -1];
            j--;
        }
        unsorted[j] = v;
    }
    return unsorted;
}

我的 while 循环 ([j-1]) 得到一个 IndexOutOfBoundsException。但是我怎样才能重写代码使其真正起作用？

Answer 1

对于索引 i，您可以简单地从 i-1 开始索引 j。在 while 循环中，始终先检查索引有效性，然后再从该索引访问数据。以下代码解决了您的问题：

public int[] sort(int[] unsorted) {
    int i, j, v;
    for (i = 1; i < unsorted.length; i++) {
        v = unsorted[i];
        j = i - 1;

        while (j >= 0 && unsorted[j] > v) {
            unsorted[j + 1] = unsorted[j];
            j--;
        }
        unsorted[j + 1] = v;
    }
    return unsorted;
}

在 java 中编写插入排序算法

Writing an algorithm for insertion sort in java

java

algorithm

sorting

insertion-sort