冒泡排序复杂度问题

来源：百度知道 编辑：UC知道 时间：2024/05/22 19:34:56
最坏情况复杂度的时候需要比较n(n-1)/2次，这个是怎么得到的
比如说3，2，1这个数列，如果使用冒泡排序，那么最坏情况应该比较3次，顺便解释一下这个3次是怎么得到的

这个式子类似于梯形面积公式。
(上底+下底)*高/2 即 { 1+(n-1)}*(n-1)/2

下面详细说明：
一个长度n的数组，用冒泡法;
将第一个最大/小数冒泡到顶需要 需要比较 n-1 次
第二个 ： n-2次
第三个 ： n-3次
。
。
第k个 : n-k次
。
。
第n-1个：n-(n-1)=1 次
第n个不需要比，所以
总次数 = { 1+(n-1)}*(n-1)/2
想象成一个梯形就容易理解了

2,3,1 2,1,3, 1,2,3
所谓最坏情况既是与你的预期排序完全相反,你想得到递增序列,
数据却是递减的..