在实现插入排序时，可以使用二分查找来定位数组的前 i - 1 个元素中应该插入元素 i 的位置。
这将如何影响所需的比较次数？使用这样的二分搜索将如何影响插入排序的渐近运行时间？
我很确定这会减少比较次数，但我不确定为什么。
最佳答案
直接来自维基百科:
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.
来源:
http://en.wikipedia.org/wiki/Insertion_sort#Variants
这是一个例子:
http://jeffreystedfast.blogspot.com/2007/02/binary-insertion-sort.html
I'm pretty sure this would decrease the number of comparisons, but I'm not exactly sure why.
好吧，如果您已经了解插入排序和二分查找，那么它就非常简单了。当您在插入排序中插入一个片段时，您必须与之前的所有片段进行比较。假设您想将此 [2] 移动到正确的位置，您必须先与 7 件进行比较，然后才能找到正确的位置。
[1][3][3][3][4][4][5] ->[2]<- [11][0 ][50][47]
但是，如果您在中间点开始比较(如二分查找)，那么您只会比较 4 件!您可以这样做，因为您知道左边的部分已经按顺序排列(如果部分按顺序排列，您只能进行二分查找!)。
现在想象一下，如果您有数千件(甚至数百万件)，这将为您节省大量时间。我希望这有帮助。 |=^)
关于algorithm - 二分查找插入排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18022192/