在实现插入排序时，可以使用二进制搜索来定位数组的前 i - 1 个元素中应插入元素 i 的位置。
这将如何影响所需的比较次数？使用这种二分搜索如何影响插入排序的渐近运行时间？
我很确定这会减少比较次数，但我不确定为什么。
问问题
56687 次
5 回答
28
直接来自维基百科：
如果比较的成本超过交换的成本，例如通过引用存储的字符串键或人工交互（例如选择并排显示的一对中的一个），那么使用二进制插入排序可能会产生更好的性能。二分插入排序采用二分查找来确定插入新元素的正确位置，因此在最坏的情况下执行 ⌈log2(n)⌉ 比较，即 O(n log n)。由于每次插入需要一系列交换，整个算法的平均运行时间仍然为 O(n2)。
资源：
http://en.wikipedia.org/wiki/Insertion_sort#Variants
这是一个例子：
http://jeffreystedfast.blogspot.com/2007/02/binary-insertion-sort.html
我很确定这会减少比较次数，但我不确定为什么。
好吧，如果您已经知道插入排序和二进制搜索，那么它就非常简单了。当您在插入排序中插入一个片段时，您必须与之前的所有片段进行比较。假设您要将这个 [2] 移动到正确的位置，您必须比较 7 件才能找到正确的位置。
[1][3][3][3][4][4][5] -> [2] <- [11][0][50][47]
但是，如果您在中途点开始比较（如二进制搜索），那么您将只比较 4 件！你可以这样做，因为你知道左边的部分已经是有序的（如果部分是有序的，你只能进行二进制搜索！）。
现在想象一下，如果您有数千件（甚至数百万件），这将为您节省大量时间。我希望这有帮助。|=^)
于 2013-08-02T16:51:18.253 回答
10
如果你有一个很好的数据结构来进行高效的二分搜索，那么插入时间不太可能是 O(log n)。相反，在任意位置快速插入的良好数据结构不太可能支持二进制搜索。
要使用插入排序实现最佳比较搜索的 O(n log n) 性能，需要 O(log n) 二分搜索和 O(log n) 任意插入。
于 2013-08-02T21:23:38.667 回答
4
二进制插入排序 - 取这个数组 => {4, 5 , 3 , 2, 1}
现在在主循环中，想象我们在第三个元素。现在使用二分搜索，我们将知道在哪里插入 3，即在 4 之前。
Binary Search 使用 O(Logn) 比较，这是一个改进，但我们仍然需要在正确的位置插入 3。为此，我们需要将 3 与 5 交换，然后与 4 交换。
由于插入花费的时间与没有二分搜索的情况相同，因此最坏情况下的复杂性仍然是 O(n^2)。我希望这有帮助。
于 2019-04-12T06:59:42.370 回答
2
假设数组已排序（用于执行二进制搜索），它不会减少任何比较，因为内部循环在 1 次比较后立即结束（因为前一个元素更小）。通常，插入排序中的比较次数最多为反转次数加上数组大小 - 1。
由于已排序数组中的反转次数为 0，因此已排序数组中的最大比较次数为 N - 1。
于 2013-08-02T21:48:39.280 回答
0
为了比较，我们有 log n 时间，swap 将是 n 的顺序。对于最坏情况下的 n 个元素：n*(log n + n) 是 n^2 的顺序。
于 2020-07-27T15:53:58.743 回答