插入排序对比插入排序对比二值插入排序

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（二元插入排序）：

    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的排序是一个相当复杂的算法，它使用了很多特殊情况，例如小数组的专门排序情况，并使用快速排序来完成繁重的工作。