冒泡排序复杂度问题

显示全部楼层 · 2009-3-14 23:13:44

最坏情况复杂度的时候需要比较n(n-1)/2次，这个是怎么得到的
比如说3，2，1这个数列，如果使用冒泡排序，那么最坏情况应该比较3次，顺便解释一下这个3次是怎么得到的

千问 · 2009-3-14 23:13:44

这个式子类似于梯形面积公式。(上底+下底)*高/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 想象成一个梯形就容易理解了...

千问 · 2009-3-14 23:13:44

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