Der*_*tle 14 sorting algorithm binary-search insertion-sort
在实现插入排序时,可以使用二进制搜索来定位要插入元素i的数组的第一个i-1元素内的位置.
这将如何影响所需的比较次数？如何使用这样的二进制搜索影响Insertion Sort的渐近运行时间？
我很确定这会减少比较次数,但我不确定为什么.
But*_*ass 19
直接来自维基百科:
如果比较的成本超过交换的成本,例如通过引用或人工交互存储的字符串键(例如选择并排显示的一对中的一个)的情况,则使用二进制插入排序可能会产生更好的性能.二进制插入排序采用二进制搜索来确定插入新元素的正确位置,因此在最坏的情况下执行⌈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件!你可以这样做,因为你知道左边的部分已经按顺序排列了(如果部分是有序的话,你只能进行二进制搜索!).
现在想象一下,如果你有成千上万件(甚至数百件),这将为你节省大量时间.我希望这有帮助.| = ^)
如果您有一个良好的数据结构来进行有效的二进制搜索,则不太可能有O(log n)插入时间.相反,在任意位置快速插入的良好数据结构不太可能支持二进制搜索.
要实现具有插入排序的最佳比较搜索的O(n log n)性能,需要O(log n)二进制搜索和O(log n)任意插入.
小智 5
二分插入排序 - 取这个数组 => {4, 5 , 3 , 2, 1}
现在在主循环中，假设我们处于第三个元素。现在使用二分查找，我们将知道在哪里插入 3，即 4 之前。
二分查找使用 O(Logn) 比较，这是一种改进，但我们仍然需要在正确的位置插入 3。为此，我们需要将 3 与 5 交换，然后与 4 交换。
由于插入所需的时间与没有二分查找时的时间相同，最坏情况下的复杂度仍然是 O(n^2)。我希望这有帮助。