冒泡排序程序简单，基本大家都会，今天讲下如何计算其时间复杂度。算法比较简单，简单讲下大家应该就明白了。
最坏情况:
最坏的情况就是所有的元素都要对换，比如希望排出从小到大的顺序，而数组却是从大到小排列：5,4,3,2,1。那么时间复杂度就达到了最大值。
具体计算方法是这样的：一共有5个数字的话，那么冒出的第一个泡需要对换5-1次后放到最后，由于已经找到了最大值放到了最后，冒出的第二个泡就只需要对换5-2次放到倒数第二位了，由于已经找到了最大的两个放到了后面，冒出的第三个泡就只需要对换5-3次了。以此类推，一共需要对换：(5-1) + (5-2) + (5-3) + (5-4)次，相当于一个等差数列求和：1+...+(5-1) ，这里的5可以替换为n，所以最坏情况需要排序(n-1)** n/2，这个就相当于nn，也就是n方了。
简单的想就是冒第i个泡，需要n-i次比较，之所以n-i是因为第一个需要比较n-1次，剩下的不需要和已经冒出的泡比较，所以是n-1-(i-1)，也就是n-i了。所有比较次数相加就是时间复杂度了。
冒泡过程:
排序前：5，4，3，2，1
排序第一次找到最大值：4，3，2，1，5
排序第二次找到次大值：3，2，1，4，5
排序第三次找到第3大值：2，1，3，4，5
排序第四次找到第4大值：1，2，3，4，5
网友评论