sorting - 冒泡排序交换次数

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