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() также использует второй подход (возможно, из-за повторного использования кода, потому что метод подкачки используется в разных местах, возможно, потому, что это проще понять).

Реализация 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 * п (п-1), за исключением тех, для внешних контуров.
3. Ни одна из этих программ не имеет большого смысла для реальной работы, поскольку они стоят, потому что они не используют информацию в их распоряжении. Например, легко добавить проверку во внутренний цикл, чтобы узнать, были ли сделаны какие-либо свопы: если нет, то массив сортируется, и вы можете закончить, возможно, сохранив большую часть работы. На практике эти виды рассмотрения могут доминировать в среднем случае.

Postscript пропущенный вопрос о Java: Я понимаю, что вроде Java является довольно сложный алгоритм, который использует много особых случаев, таких как специализированная сортировка случаев для небольших массивов, а также с помощью быстрой сортировки, чтобы сделать его тяжелая атлетика.