Сортировка вставками против.Сортировка вставками против.Двоичная сортировка вставкой

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;
        }
    }
}

Имеет ли двоичная вставка какое-либо практическое применение или это скорее теоретическая вещь?На небольших массивах другие подходы работают намного быстрее, а на больших массивах сортировка слиянием/быстрая сортировка имеет гораздо лучшую производительность.

Answer 1

1. удалить ложное утверждение
2. Количество сравнений в первых двух составляет 1/2*n(n-1), не считая сравнений для внешних циклов.
3. Ни одна из этих программ не имеет особого смысла для реальной работы в их нынешнем виде, поскольку они не используют имеющуюся в их распоряжении информацию.Например, во внутренний цикл легко добавить проверку, были ли сделаны какие-либо замены:если нет, то массив сортируется, и вы можете закончить, возможно, сохранив большую часть работы.На практике подобные соображения могут доминировать в среднем случае.

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