哨兵插入排序

Question

我想知道在这段代码中添加哨兵是否有目的？

public void Sort(ArrayToSort<T> array) {
    for (var i = 0; i < array.Length; i++) {
        for (var j = i; j > 0; j--) {
            if (array.isLess(j, j - 1)) {
                array.Swap(j, j - 1);
            } else {
                break;
            }
        }
    }
}

如果答案是肯定的，我应该怎么做？因为如果我复制所有选项卡，我很确定没有哨兵更好...... 谢谢 ;)

Answer 1

有办法在插入排序中生成自然哨兵。第一次遍历整个数组，找到最小的元素移到第一个位置

在那之后你摆脱了内循环中的索引检查。 Sedgewick 书中第二阶段的示例代码（C 中的算法）：

for (i = l+2; i <= r; i++)
  { int j = i; Item v = a[i];
    while (less(v, a[j-1]))
      { a[j] = a[j-1]; j--; }
    a[j] = v;
  }

另请注意，为了提高效率，插入排序使用元素移位而不是交换。

在最坏的情况下使用此方法，您有大约 n^2/2 元素比较 与 (n^2/2 元素比较 + n^2/2 i索引比较在普通情况下）。

我认为速度增益应该存在，但不是很大（元素比较可能更重，并且两种情况下的移位操作次数相同）。您可以分析这两种方法并了解您的特定案例的结果。

哨兵插入排序

Insertion sort with sentinel

algorithm

sorting

insertion-sort