神马品牌网酒店前台投诉案例处理:冒泡排序
来源：百度文库 编辑：神马品牌网 时间：2024/04/29 19:58:24
在最坏情况下，冒泡排序所需要的比较次数为n(n-1)/2，我是这样举例子（原序列6 5 4 3 2 1）算出来的：
5 6 3 4 1 2 ……3次
5 3 6 1 4 2 ……2次
3 5 1 6 2 4 ……3次
3 1 5 2 6 4 ……2次
1 3 2 5 4 6 ……3次
1 2 3 4 5 6 ……2次
共15次
请问严格的证明应该是怎样的呢？谢谢！
5 6 3 4 1 2 ……3次
5 3 6 1 4 2 ……2次
3 5 1 6 2 4 ……3次
3 1 5 2 6 4 ……2次
1 3 2 5 4 6 ……3次
1 2 3 4 5 6 ……2次
共15次
请问严格的证明应该是怎样的呢？谢谢！
假设共n个数据，第一趟最坏会交换n-1次，第二趟n-2次，。。。最后一趟1次，(n-1)+(n-2)+....1=(n-1+1)(n-1)/2=n(n-1)/2
第一个数据从第一位移到最后一位需要5次(第一个数据依次比较到最后一位),当第二次移动时,第一个数据只要移动到倒数第二位就可以了就是4次(已经和6比过了),这样的话一工就会5+4+3+2+1
可以用数学归纳法证明