java - 关于 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中的插入排序实现。这里作者提到如下改进。

It is not difficult to speed up insertion sort substantially, by shortening its inner loop to move the larger entries to the right one position rather than doing full exchanges (thus cutting the number of array accesses in half)

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

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

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

Answer 1

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

例如，您可以最初缓存第 i 个元素的值，并在内部循环中仅引用它:

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