冒泡排序交换次数

Question

要使用冒泡排序算法对 6 个元素 {11,5,7,3,2,1} 的列表进行排序，您可以手动找到它有 14 次交换。我知道下面的公式可以进行比较

n(n-1)/2

6(6-1)/2 = 15。为什么是 15 而不是 14？

另外，快速排序和插入排序是否有类似的公式？

提前致谢！

Answer 1

按升序排列：

在冒泡排序中，最大的元素向右移动。因此，当在右侧找到较小的元素时，交换就完成了。

因此，要计算某个元素的交换次数，只需计算右侧小于该元素的元素数量即可。

数组{11,5,7,3,2,1}

对于 11，右侧较小的元素数量：5(5,7,3,2,1)

5: 3(3,2,1)

对于 7：3(3,2,1)

对于 3：2(2,1)

对于 2：1(1)

为 1:0

总交换次数：5+3+3+2+1 = 14