algorithm - 插入排序与插入排序与二进制插入排序

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

二进制插入排序是否有任何实际用途，还是更多的是理论上的东西？在小型数组上，其他方法要快得多，而在更大的数组上，归并排序/快速排序具有更好的性能。

Answer 1

1. 删除虚假声明
2. 前两次比较次数为1/2*n(n-1)，不包括外层循环。
3. 这些程序目前对实际工作都没有多大意义，因为它们没有利用它们所掌握的信息。例如，很容易在内部循环中添加检查以查看是否进行了任何交换:如果没有，则对数组进行排序，然后您就可以完成，也许可以节省大部分工作。在实践中，这些考虑可能会主导一般情况。

后记错过了有关 Java 的问题:我知道 Java 的排序是一种非常复杂的算法，它使用了很多特殊情况，例如小型数组的专门排序情况，并使用快速排序来完成繁重的工作。