我刚刚完成了旧的“排序侦探”作业（给你一些黑盒排序算法，并且必须根据结果确定每个是什么例子），我注意到插入排序总是在排序后进行 N-1 比较列表。由于在每个人都上交作业之前我将无法查看老师的代码，也不允许我在课堂上提问可能会提示其他学生如何继续解决问题的问题，这让我离开了有一个问题，我至少一周都无法得到这个问题的答案。
在现实世界中，插入排序的教科书示例是否总是会在排序列表上进行 N-1 比较，还是我的教师/教科书版本的插入排序的怪癖？
在搜索了谷歌和维基百科之后，我找不到这个问题的答案，这意味着要么我问错了问题，要么他们没有。有任何想法吗？
是的，如果输入已经排序，“教科书”插入排序将执行 N-1 次比较。例如，参见 Knuth 的计算机编程艺术，第 3 卷，第 5.2.1 节，算法 S（直接插入排序）。对于每个记录 R i (i > 1)，该算法将其与元素 R i-1进行比较，以该顺序向下到 R 1，直到找到小于 R i的元素。如果输入已经排序，则 R i-1始终小于 R i，因此该算法仅对每条记录执行一次比较（并且不对记录 1 进行比较）。
当然，您可以编写插入排序来按从 R 1到 R i-1的顺序执行比较，但如果输入列表已经排序，则将执行 N*(N-1)/2 比较。所以不要那样做。:)
您还可以使用二进制搜索来查找插入每条记录的位置。这称为二元插入，Knuth 也在 §5.2.1 中讨论了它。同样，它将对已经排序的输入执行比教科书直接插入更多的比较（但对随机输入执行的比较更少）。