关于 Robert Sedgewick 中插入排序的改进

Question

我正在阅读 Robert Sedgewick 的关于算法的书。

public static void sort(Comparable[] a)
{   // Sort a[] into increasing order.
    int N = a.length;
    for (int i = 1; i < N; i++)
    { // Insert a[i] among a[i-1], a[i-2], a[i-3]... ..
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--)
            exch(a, j, j-1);
    }
}

以上是java中的插入排序实现。这里作者提到如下改进。

通过缩短其内部循环将较大的条目移动到正确的位置而不是进行完全交换（从而将数组访问次数减少一半），大幅加快插入排序并不难

我很难理解上述改进。作者是什么意思

1. 将大条目移动到正确的一个位置，而不是完全交换，以及这将如何将数组访问减少一半。

请求以简单的例子举例，以便更好地理解。

Answer 1

我认为他指的是您不需要继续实际交换元素的事实，因为您最终会反复移动相同的元素。

例如，您可以i最初缓存-th 元素的值，并在内循环中仅引用此值：

public static <C extends Comparable<C>> void insertionSort(C[] a) {
  for (int i = 1; i < a.length; i++) {
    C ithElement = a[i];
    int j = i;
    for (j = i; j > 0 && ithElement.compareTo(a[j - 1]) < 0; --j) {
      // This is "moving the larger entry to the right 1 position"
      a[j] = a[j - 1];
    }
    a[j] = ithElement;
  }
}

Demo