冒泡排序在最坏的情况下的比较次数为什么是n(n-1)⼀2?

2024-11-20 15:38:16
推荐回答(4个)
回答1:

冒泡排序如1,2,3,4最好的情况是按完全升级排列,最坏就是数字完全按降序排列:

第一次是1:然后1和2,3,4;

第2次是2:比较谁比它小交换,于是2和34交换,答案是3421;

第3次为3:3和4;

最后是4321;这就是最坏情况下的次数3+2+1=6=4*3/2;

其实对于n个的话,你要求降低排列,但是偏偏都是升序的数字;最坏的情况就是如此:次数为:n-1+n-2......+1=n*(n-1)/2。

C语言冒泡排序法详解

1、要想编出程序来,首先我们必须了解冒泡排序法的意思:比较相邻的元素,如果第一个比第二个大,就交换他们两个。对每一对相邻元素进行同样的操作,这样,最后的元素应该会是最大的数。排除最后一个数,针对所有的元素重复以上的步骤。持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

2、了解之后就是代码了。

3、有些朋友可能看不太懂,我来解释下。我们定义了i,j,a[10],进入i的循环,把值存入a[i]里。


                                   

4、存好数据后,进入下一个循环,判断a[j-1]和a[j]的大小,因为i=0,所以这里就是从a[0]开始判断的,如果更大就交换位置。


                                   

5、最后就是输出结果了,上一步已经排好位置了,我们只需要把排好的数打印出来就是了。

      

回答2:

冒泡排序如1,2,3,4最好的情况是按完全升级排列,最坏就是数字完全按降序排列:
第一次是1:然后1和2,3,4
第2次:2:比较谁比它小交换,于是2.和34交换,答案是3421
第3次为3:3和4
交换机最后是4321;这就是最坏情况下的次数3+2+1=6=4*3/2;
其实对于n个的话,你要求降低
排列,但是偏偏都是升序的数字;最坏的情况就是如此:次数为:n-1+n-2
.........+1=n*(n-1)/2;好累哇哇

回答3:

因为冒泡排序时两个一组进行比较,需要经过n/2遍的从前向后比较及n/2遍的从后向前比较,所以为n(n-1)/2

回答4:

请先弄清楚什么情况是最坏情况