最佳情况下的插入排序

Question

参考 算法 - 第四版 罗伯特和凯文，我很难理解插入排序的最佳情况复杂度按照下面的代码：

    public class Insertion
{
    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);
        }
    }
// See page 245 for less(), exch(), isSorted(), and main().
}

书上说最好情况下（有序数组），交换次数为0次，比较次数为N-1次。虽然我知道交换是 0，但我很难 在最好的情况下，比较次数怎么能是 N-1？

Answer 1

如果数组已经排序，那么在您提供的插入排序的具体实现中，每个元素只会与其紧邻前身进行比较。由于它不小于那个前任，因此内部 for-loop 然后立即中止，不需要任何进一步的比较或交换。

请注意，插入排序的其他实现不一定具有属性。

Answer 2

具体实现的源码为：

    public class Insertion
{
    public static void sort(Comparable[] a)
    { // Sort a[] into increasing order.
        int N = a.length;
        bool exc = false;
        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);
                    exc = true;
                }
             if (!exc)
                 break;
        }
    }
// See page 245 for less(), exch(), isSorted(), and main().
}

Answer 3

how can number of compares be N-1 in best case?

最好的情况发生在您有一个已经排序的数组时。比较的次数是n-1，因为是从第2个元素开始比较到最后一个元素

这也可以从您给定的代码中观察到：

for (int i = 1; i < N; i++)    //int i=1 (start comparing from 2nd element)

最佳情况下的插入排序

Insertion sort in best case

algorithm

insertion-sort