插入和冒泡排序的平均情况复杂度分析

Question

这个网站已经有一些关于这个主题的问题，但在看了一些答案后，我感到困惑。

https://cs.stackexchange.com/questions/20/evaluating-the-average-time-complexity-of-a-given-bubblesort-algorithm

在上面的链接中，"Joe“回答说，冒泡排序中的平均交换数量与平均反转数量相同，即(n)(n-1) / 4。

然而，Insertion sort vs Bubble Sort Algorithms说，在冒泡排序中，交换的平均数量是n^2 /2 and，在插入排序中是n^2/4，这就是插入排序优于冒泡排序的原因。

哪一个是正确的？有人能帮帮我吗？

Answer 1

你的第一个链接计算了预期的反转(即掉期)数量，假设是均匀分布的。

您的第二个链接是计算迭代次数，即检查元素。

两者都是正确的。