6

我到处读到，对于像Merge-Sortand这样的分而治Quicksort之的排序算法，与其递归直到只剩下一个元素，不如转移到Insertion-Sort达到某个阈值（比如 30 个元素）时。这很好，但为什么只有Insertion-Sort？为什么不Bubble-Sort或Selection-Sort，两者具有相似的O(N^2)性能？Insertion-Sort只有在对许多元素进行预排序时才应该派上用场（尽管这种优势也应该伴随着Bubble-Sort），但除此之外，为什么它应该比其他两个更有效？

其次，在这个链接上，在第二个答案及其随附的评论中，它说与upto a certainO(N log N)相比表现不佳。怎么来的？应该总是表现得比 差，因为对于所有 N >= 2，对吧？O(N^2)NN^2N log NN > log N

4

6 回答 6

11

如果您在分治法快速排序的每个分支达到阈值时退出，您的数据将如下所示：

[the least 30-ish elements, not in order] [the next 30-ish ] ... [last 30-ish]

插入排序具有相当令人愉悦的属性，您可以在整个数组上只调用一次，并且它的执行基本上与为每个 30 块调用一次时相同。因此，您不必在循环中调用它，而是最后调用它的选项。这可能不会更快，特别是因为它通过缓存拉取整个数据额外的时间，但取决于代码的结构，它可能很方便。

冒泡排序和选择排序都没有这个属性，所以我认为答案可能很简单，就是“方便”。如果有人怀疑选择排序可能更好，那么举证责任就在于他们“证明”它更快。

请注意，这种插入排序的使用也有一个缺点——如果你这样做并且你的分区代码中有一个错误，那么只要它不会丢失任何元素，只是将它们分区不正确，你永远不会注意到。

编辑：显然这个修改是由 Sedgewick 完成的，他于 1975 年在 QuickSort 上写了博士学位。Musser（Introsort 的发明者）最近对其进行了分析。参考https://en.wikipedia.org/wiki/Introsort

Musser 还考虑了 Sedgewick 的延迟小排序对缓存的影响，其中小范围在最后一次插入排序中进行排序。他报告说它可以使缓存未命中的数量增加一倍，但它的双端队列性能要好得多，应该保留给模板库，部分原因是在其他情况下立即进行排序的收益并不大。

无论如何，我不认为一般建议是“无论你做什么，都不要使用选择排序”。建议是，“插入排序胜过快速排序，因为输入的大小非常小”，当你实现快速排序时，这很容易向你自己证明。如果你想出另一种在相同的小数组上明显优于插入排序的排序，那么这些学术资料都没有告诉你不要使用它。我想令人惊讶的是，该建议始终针对插入排序，而不是每个来源都选择自己喜欢的来源（坦率地说，入门教师有一个令人惊讶的对冒泡排序的喜爱——如果我再也没有听说过它，我不会介意）。插入排序通常被认为是小数据的“正确答案”。问题不在于它是否“应该”快，而在于它是否真的快，而且我从来没有特别注意到任何基准消除了这个想法。

寻找此类数据的一个地方是 Timsort 的开发和采用。我很确定 Tim Peters 选择插入是有原因的：他没有提供一般性建议，他正在优化库以供实际使用。

于 2012-09-27T14:28:06.803 回答
7
  1. 在实践中，插入排序至少比冒泡排序更快。它们的渐近运行时间是相同的，但插入排序具有更好的常数（每次迭代的操作更少/更便宜）。最值得注意的是，它只需要线性数量的元素对交换，并且在每个内部循环中，它执行每个n / 2 元素和可以存储在寄存器中的“固定”元素之间的比较（而冒泡排序必须从内存中读取值）。即插入排序在其内部循环中的工作比冒泡排序少。
  2. 答案声称 10000 n lg n > 10 n ² 对于“合理的” n。对于大约 14000 个元素，这是正确的。
于 2012-09-27T13:46:27.437 回答
5

我很惊讶没有人提到插入排序对于“几乎”排序的数据要快得多的简单事实。这就是它被使用的原因。

于 2014-04-09T13:47:17.590 回答
4

第一个更容易：为什么插入排序优于选择排序？因为对于最优输入序列，插入排序在O(n)中，即如果序列已经排序。选择排序总是在O(n^2)中。

为什么插入排序优于冒泡排序？对于已经排序的输入序列，两者都只需要一次通过，但插入排序会更好地降级。更具体地说，插入排序在反转次数较少的情况下通常比冒泡排序表现更好。这可以解释，因为冒泡排序总是在第 i 次迭代中迭代 Ni 元素，而插入排序更像“查找”，并且只需要平均迭代 (Ni)/2 个元素（在第 Ni-1 次迭代中）以找到插入位置。因此，平均而言，插入排序预计比插入排序快两倍左右。

于 2012-09-27T14:26:02.707 回答
4

这是一个经验证明，插入排序比冒泡排序更快（对于 30 个元素，在我的机器上，附加实现，使用 java ...）。

我运行了附加的代码，发现冒泡排序平均运行了 6338.515 ns，而插入则需要 3601.0

我使用wilcoxon 签名测试来检查这是一个错误的概率，它们实际上应该是相同的 - 但结果低于数值错误的范围（实际上是 P_VALUE ~= 0）

private static void swap(int[] arr, int i, int j) { 
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

public static void insertionSort(int[] arr) { 
    for (int i = 1; i < arr.length; i++) {
        int j = i;
        while (j > 0 && arr[j-1] > arr[j]) { 
            swap(arr, j, j-1);
            j--;
        }
    }
}
public static void bubbleSort(int[] arr) { 
    for (int i = 0 ; i < arr.length; i++) { 
        boolean bool = false;
        for (int j = 0; j < arr.length - i ; j++) { 
            if (j + 1 < arr.length && arr[j] > arr[j+1]) {
                bool = true;
                swap(arr,j,j+1);
            }
        }
        if (!bool) break;
    }
}

public static void main(String... args) throws Exception {
    Random r = new Random(1);
    int SIZE = 30;
    int N = 1000;
    int[] arr = new int[SIZE];
    int[] millisBubble = new int[N];
    int[] millisInsertion = new int[N];
    System.out.println("start");
    //warm up:
    for (int t = 0; t < 100; t++) { 
        insertionSort(arr);
    }
    for (int t = 0; t < N; t++) { 
        arr = generateRandom(r, SIZE);
        int[] tempArr = Arrays.copyOf(arr, arr.length);

        long start = System.nanoTime();
        insertionSort(tempArr);
        millisInsertion[t] = (int)(System.nanoTime()-start);

        tempArr = Arrays.copyOf(arr, arr.length);

        start = System.nanoTime();
        bubbleSort(tempArr);
        millisBubble[t] = (int)(System.nanoTime()-start);
    }
    int sum1 = 0;
    for (int x : millisBubble) {
        System.out.println(x);
        sum1 += x;
    }
    System.out.println("end of bubble. AVG = " + ((double)sum1)/millisBubble.length);
    int sum2 = 0;
    for (int x : millisInsertion) {
        System.out.println(x);
        sum2 += x;
    }
    System.out.println("end of insertion. AVG = " + ((double)sum2)/millisInsertion.length);
    System.out.println("bubble took " + ((double)sum1)/millisBubble.length + " while insertion took " + ((double)sum2)/millisBubble.length);
}

private static int[] generateRandom(Random r, int size) {
    int[] arr = new int[size];
    for (int i = 0 ; i < size; i++) 
        arr[i] = r.nextInt(size);
    return arr;
}

编辑：
（1）优化冒泡排序（上面更新）将冒泡排序的总时间减少到：6043.806 不足以做出重大改变。Wilcoxon 检验仍然是结论性的：插入排序更快。

(2) 我还添加了一个选择排序测试（附加代码）并将其与插入进行比较。结果是：选择花费了 4748.35，而插入花费了 3540.114。
wilcoxon 的 P_VALUE 仍低于数值误差范围（实际上 ~=0）

使用的选择排序代码：

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length ; i++) { 
        int min = arr[i];
        int minElm = i;
        for (int j = i+1; j < arr.length ; j++) { 
            if (arr[j] < min) { 
                min = arr[j];
                minElm = j;
            }
        }
        swap(arr,i,minElm);
    }
}
于 2012-09-27T14:13:54.857 回答
2

编辑：正如 IVlad 在评论中指出的那样，选择排序对任何数据集只进行 n 次交换（因此只有 3n 次写入），因此插入排序不太可能因为交换次数较少而击败它——但它可能会大幅比较少。下面的推理更适合与冒泡排序的比较，冒泡排序将进行相似数量的比较，但平均会有更多的交换（因此更多的写入）。

插入排序往往比冒泡排序和选择排序等其他 O(n^2) 算法更快的一个原因是，在后一种算法中，每一个数据移动都需要一个 swap，它可能是内存的 3 倍如果交换的另一端需要稍后再次交换，则根据需要进行复制。

使用插入排序OTOH，如果要插入的下一个元素还不是最大元素，则可以将其保存到一个临时位置，并通过从右侧开始并使用单个数据副本（即没有交换）将所有较低的元素向前分流. 这为放置原始元素打开了一个空白。

不使用交换的插入排序整数的 C 代码：

void insertion_sort(int *v, int n) {
    int i = 1;
    while (i < n) {
        int temp = v[i];         // Save the current element here
        int j = i;

        // Shunt everything forwards
        while (j > 0 && v[j - 1] > temp) {
            v[j] = v[j - 1];     // Look ma, no swaps!  :)
            --j;
        }

        v[j] = temp;
        ++i;
    }
}
于 2012-09-27T14:00:20.343 回答