插入排序和哨兵

Question

我正在尝试了解插入排序。我听说我可以用一个哨兵来改进它。

这是我没有哨兵的代码：

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 异常。你能帮我理解为什么需要一个 Sentinel 来改进该代码，以及我必须在哪里输入它吗？我会说我必须在数组的左边缘放置一个 Integer.MIN_Value 但我不确定，因为我没有看到它用完数组的情况。

如果你能帮助我理解标记在插入排序中的用法，我将不胜感激。

有了 Sentinel...

    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];
    }
}

Answer 1

静态 Sentinel 将是一个非常低的值，它将作为数组的第一个元素放置，即在数组 [0] 中。这具有不检查代码中的条件 "j>0" 的优点。

添加了 j>0 条件，以便程序不会给出 ArrayIndexOutOfBounds 异常。通过在数组 [0] 和运行数组 [1....n] 的循环中添加一个填充元素，我们节省了检查 j>0 条件的开销。

请注意，无症状地，它不会影响插入排序的复杂性。

编辑： 您修改后的实施是正确的。我假设您感到困惑，因为现在您必须再次填充整个数组，这将花费额外的 theta(n) 时间。所以你担心添加哨兵实际上会使它变慢。但是，您需要了解这是 Java 的问题。 Java 数组的大小不可变，因此您需要创建一个新数组。这不是算法的监视点。算法与语言无关。如果您使用了其他具有可变数组大小规定的语言或使用了 Java 的列表，则可以在 O(1) 时间内添加哨兵。在那种情况下，生成的程序会更快。

Answer 2

您不需要创建更大尺寸的新数组。

通过数组做一个运行，找到最小元素移到第0位

现在这个元素作为哨兵，你可以在不检查边界的情况下对数组的其余部分进行排序。

插入排序和哨兵

Insertionsort and Sentinels

java

algorithm

insertion-sort

sentinel