插入排序在最好的情况下

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

如果数组已经排序，然后在具体实施中，你提供插入排序，每个元素将仅比其立即前身。由于它不小于该前任，因此内部立即中止，而不需要任何进一步的比较或交换。

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

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

如何能的数相比较是N-1在最好的情况下？

当你有一个已经排序好的数组时，会发生最好的情况。比较的数量是n-1，因为比较是从第二个元素开始直到最后一个元素。

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

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