我想获得 {1, ..., n} 的排列数，插入排序正好进行 n(n-1)/2 次比较。 例如，对于 {1, 2, 3, 4} 我们得到 (4, 3, 2, 1), (3, 4, 2, 1), (4, 2, 3, 1) 等 - 对于所有他们 InsertionSort 进行 4*3/2 = 6 次比较。 有人知道一些确切的公式吗？ 我正在考虑类似 (n-1) + 1 = n 的问题，其中 1 代表逆序，然后我们可以逆序交换所有 (n-1) 对。
最佳答案
这是一个提示。 (1, 2, 3, 4) 的完整列表是:
(4, 3, 2, 1)
(3, 4, 2, 1)
(4, 2, 3, 1)
(2, 4, 3, 1)
(4, 3, 1, 2)
(3, 4, 1, 2)
(4, 1, 3, 2)
(1, 4, 3, 2)
从最后一列到第一列看。
逐步了解插入排序。查看它们合并的位置。你看到那里的模式了吗？
反过来，你能猜出我是如何生成这个列表的吗？你能证明这个列表是完整的吗？
为什么在这里很重要。就说2<sup>n-1</sup>没用。
关于algorithm - 插入排序中比较的确切数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42230741/