插入排序与二进制搜索

本文介绍了插入排序与二进制搜索的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

实现插入排序时，可以使用二进制搜索来定位数组i的前i-1个元素中应该插入元素i的位置.

When implementing Insertion Sort, a binary search could be used to locate the position within the first i - 1 elements of the array into which element i should be inserted.

这将如何影响所需的比较次数?使用这样的二进制搜索将如何影响插入排序的渐近运行时间?

How would this affect the number of comparisons required? How would using such a binary search affect the asymptotic running time for Insertion Sort?

我很确定这会减少比较的次数，但是我不确定为什么.

I'm pretty sure this would decrease the number of comparisons, but I'm not exactly sure why.

推荐答案

直接来自维基百科:

如果比较的成本超过掉期的成本，通常是这样例如使用通过引用或人工存储的字符串键互动(例如，从并排显示的一对中选择一个)，那么使用二进制插入排序可能会产生更好的性能.二进制插入排序采用二进制搜索来确定正确的插入新元素的位置，因此执行⌈log2(n)⌉最坏情况下的比较，即O(n log n).该算法作为由于每次插入都需要进行一系列交换.

If the cost of comparisons exceeds the cost of swaps, as is the case for example with string keys stored by reference or with human interaction (such as choosing one of a pair displayed side-by-side), then using binary insertion sort may yield better performance. Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs ⌈log2(n)⌉ comparisons in the worst case, which is O(n log n). The algorithm as a whole still has a running time of O(n2) on average because of the series of swaps required for each insertion.

来源:

en.wikipedia/wiki/Insertion_sort#Variants

这里是一个例子:

jeffreystedfast.blogspot/2007/02/binary-insertion-sort.html

我很确定这会减少比较的次数，但是我不确定原因.

好吧，如果您已经知道插入排序和二进制搜索，那么它非常简单.当您以插入方式插入作品时，您必须与之前的所有作品进行比较.假设您要将[2]移到正确的位置，则必须先比较7个，然后再找到正确的位置.

Well, if you know insertion sort and binary search already, then its pretty straight forward. When you insert a piece in insertion sort, you must compare to all previous pieces. Say you want to move this [2] to the correct place, you would have to compare to 7 pieces before you find the right place.

[1] [3] [3] [3] [4] [4] [5] -> [2] <-[11] [0] [50] [47]

[1][3][3][3][4][4][5] ->[2]<- [11][0][50][47]

但是，如果您从中点开始比较(如二进制搜索)，则只能比较4个！您可以执行此操作，因为您知道剩余的片段已按顺序排列(如果片段按顺序排列，则只能执行二进制搜索！).

However, if you start the comparison at the half way point (like a binary search), then you'll only compare to 4 pieces! You can do this because you know the left pieces are already in order (you can only do binary search if pieces are in order!).

现在想象一下，如果您有成千上万件(甚至数百万件)，这将为您节省大量时间.我希望这有帮助.| = ^)

Now imagine if you had thousands of pieces (or even millions), this would save you a lot of time. I hope this helps. |=^)