algorithm - 冒泡排序的比较次数

Question

我了解到冒泡排序的比较次数是

(n - 1) + (n - 2) + (n - 3) + ... + 2 + 1

怎么会变成这样？

(n - 1) * n/2

你能解释一下吗？

Answer 1

总和

1 + 2 + 3 + 4 + .... + n = n * (n + 1)/2

所以总和

1 + 2 + 3 + .. + (n-1) = (n - 1) * n/2