algorithm - 哨兵插入排序

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 < strong>元素比较 + n^2/2 i索引比较 在普通情况下)。

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