1

我有几个关于插入排序的不同实现的问题。

实施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 的性能要好得多。

4

1 回答 1

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

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

于 2010-01-28T12:12:00.743 回答