algorithm - 数字已经成对的插入排序

Question

我目前正在尝试计算当元素已经排好序对时通过插入排序完成的比较次数，例如

4,5,22,23,1,2,19,20...

目前正在努力解决使用哨兵时完成的最坏情况和平均情况下的比较次数。

对于每对乱序的最坏情况，我得出的比较模式是 1 + 3 + 3 + 5 + 5 ... + n + n , 导致求和

\sum_{n=2}^{n/2}(2n-1)(2)  

然后我将其求解为 (n^2+4/2) - 3 - (n-2)

这看起来对吗？我现在在尝试解决一般情况时遇到麻烦。知道如何去做吗？感谢您的帮助

Answer 1

你可以一次比较/交换一对相邻的数字，所以这个问题和一个半长数组的普通插入排序是一样的。每次比较需要比较两个数，所以平均情况是O((n/2)^2*2)=O(n^2/2)。