在实现插入排序时，可以使用二进制搜索来定位要插入元素i的数组的第一个i-1元素内的位置 .
这将如何影响所需的比较次数？如何使用这样的二进制搜索影响Insertion Sort的渐近运行时间？
我很确定这会减少比较次数，但我不确定为什么 .
直接来自维基百科：
如果比较的成本超过交换的成本，例如通过引用或人工交互存储的字符串键（例如选择并排显示的一对中的一个）的情况，则使用二进制插入排序可以产生更好的表现 . 二进制插入排序采用二进制搜索来确定插入新元素的正确位置，因此在最坏的情况下执行⌈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）任意插入 .
假设数组已排序（用于执行二进制搜索），它不会减少任何比较，因为内部循环在1次比较后立即结束（因为前一个元素较小） . 通常，插入排序中的比较数最多为反转数加上数组大小-1 .
由于排序数组中的反转次数为0，因此已排序数组中的最大比较数为N-1 .
3 回答
直接来自维基百科：
资源：
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）任意插入 .
假设数组已排序（用于执行二进制搜索），它不会减少任何比较，因为内部循环在1次比较后立即结束（因为前一个元素较小） . 通常，插入排序中的比较数最多为反转数加上数组大小-1 .
由于排序数组中的反转次数为0，因此已排序数组中的最大比较数为N-1 .