InsertionSort與InsertionSort與BinaryInsertionSort

Question

我有幾個關於插入排序實現的問題。

實現1：

public static void insertionSort(int[] a) { 
    for (int i = 1; i < a.length; ++i) { 
     int key = a[i]; 
     int j = i - 1; 

     while (j >= 0 && a[j] > key) { 
      a[j + 1] = a[j]; 
      --j; 
     } 

     a[j + 1] = key; 
    } 
} 

實現2：

public static void insertionSort(int[] a) { 
    for (int i = 1; i < a.length; ++i) { 
     for (int j = i; j > 0 && a[j - 1] > a[j]; --j) { 
      swap(a, j, j - 1); 
     } 
    } 
} 

private static void swap(int[] a, int i, int j) { 
    int tmp = a[i]; 

    a[i] = a[j]; 
    a[j] = tmp; 
} 

這是我的第一個問題：每個人都應該思考的是，第一個版本應該是快一點，第二版（因爲較少分配）但它不是（或者至少它的差異是微不足道的）。但爲什麼？其次，我想知道Java的Arrays.sort（）方法也使用第二種方法（可能是因爲代碼重用，因爲swap方法在不同的地方使用，也許是因爲它更容易理解）。

實施3（binaryInsertionSort）：

public static void binaryInsertionSort(int[] a) { 
    for (int i = 1; i < a.length; ++i) { 
     int pos   = Arrays.binarySearch(a, 0, i, a[i]); 
     int insertionPoint = (pos >= 0) ? pos : -pos - 1; 

     if (insertionPoint < i) { 
      int key = a[i]; 

      // for (int j = i; i > insertionPoint; --i) { 
      //  a[j] = a[j - 1]; 
      // } 
      System.arraycopy(a, insertionPoint, a, insertionPoint + 1, i - insertionPoint); 

      a[insertionPoint] = key; 
     } 
    } 
} 

是二進制插入排序任何實際用途的，或者是更加的理論嘛？在小陣列上，其他方法要快得多，而在更大的陣列上，mergesort/quicksort具有更好的性能。

Answer 1

1. 刪除虛假權利要求
2. 比較在前兩個數目是1/2 * N（N-1），但不包括那些用於外迴路。
3. 這些程序都不符合他們的實際工作，因爲他們沒有使用這些信息。例如，很容易在內部循環中添加一個檢查以查看是否進行了任何交換：如果沒有，那麼數組將被排序，並且您可以完成，也許可以節省大部分工作。在實踐中，這種考慮可以支配一般情況。

後記 錯過關於Java的問題：據我瞭解，Java的排序是一個相當複雜的算法，它使用了大量的特殊情況下，如專門分揀小數組的情況下，利用快速排序來完成其舉重。