java - 插入排序和哨兵

我在试着理解插入排序我听说我可以用哨兵来改进它。
这是我没有哨兵的密码：

public static int[] insertionSort(int[] sortieren) {
    int temp;
    for (int i = 1; i < sortieren.length; i++) {
        temp = sortieren[i];
        int j = i;
        while (j > 0 && sortieren[j - 1] > temp) {
            sortieren[j] = sortieren[j - 1];
            j--;
        }
        sortieren[j] = temp;
    }
    return sortieren;
}

我正在尝试理解在哪种情况下可以得到ArrayIndexOutOfBounds异常你能帮助我理解为什么需要一个哨兵来改进代码，以及我必须在哪里输入它吗？我要说的是，我必须在数组的左边缘放置一个Integer.MIN_值，但我不确定，因为我没有看到它在数组中用完的情况。
如果你能帮助我理解哨兵在插入训练中的用法，我将不胜感激。
有哨兵…

    public void insertionSort(int[] array) {

    int temp;
    int arraySentinel[] = new int[array.length+1];
    for(int i = 0; i < array.length; i++){
        arraySentinel[i+1] = array[i];
    }
    arraySentinel[0] = Integer.MIN_VALUE;

    for (int i = 1; i < arraySentinel.length; i++) {
            temp = arraySentinel[i];
            int j = i;
            /**
             * Stabil weil sortieren[j-1] > temp!
             * Wäre nicht stabil wenn >=!
             */
            while (arraySentinel[j - 1] > temp) {
                arraySentinel[j] = arraySentinel[j - 1];
                j--;
            }
            arraySentinel[j] = temp;
    }

    for (int i = 1; i < arraySentinel.length; i++){
        array[i-1] = arraySentinel[i];
    }
}

最佳答案

静态哨兵将是一个非常低的值，它将被放置为数组的第一个元素，即在数组[0]中这样做的好处是不检查代码中的条件“j>0”。
添加j>0条件，这样程序就不会给出arrayindexoutofbounds异常。通过在数组[0]添加一个填充元素，并从数组[1….n]运行循环，我们节省了检查j>0条件的开销。
请注意，无症状地，它不会影响插入排序的复杂性。
编辑：您修改后的实现是正确的我假设你很困惑，因为现在你必须再次填充整个数组，这将需要额外的θ（n）时间所以您担心添加sentinel实际上会使速度变慢但是，您需要理解这是Java的问题。Java数组的大小是不可变的，因此需要创建一个新数组。这不是算法的监视算法与语言无关如果您想使用其他一些具有可变数组大小设置或使用java列表的语言，那么可以在o（1）时间内添加sentinel。在这种情况下，生成的程序将更快。