首页 > 试题广场 >

线性表的长度为10，在最坏情况下，冒泡排序需要比较次数为（）

[单选题]
线性表的长度为10，在最坏情况下，冒泡排序需要比较次数为（）。 
  • 40
  • 42
  • 44
  • 45
查看答案及解析
添加回答
zt_xcyk头像 zt_xcyk
n(n+1)/2=10*9/2=45
发表于 2015-09-03 19:32:07 回复(0)
tianyunzqs头像 tianyunzqs
冒泡的算法就是
for(int i=0; i<n; ++i)
{
    for(int j=1; j<n-i; ++j)
    {
        if(a[j-1]>a[j])
        {交换。。。}
    }
}

当i=0时，进行比较n-1次；
当i=1时，进行比较n-2次；
。。。
当i=n-1时，进行比较0次；
所以总的比较次数就是(n-1) + (n-2) + ... + 1 + 0 = n*(n-1)/2
发表于 2015-09-02 10:06:41 回复(7)
河湖之恋头像 河湖之恋
最坏的情况即是每个元素两两都要相比较。故用排列组合的思想即为C(10,9)=45
发表于 2015-09-01 20:34:05 回复(4)
karaysn头像 karaysn
冒泡最好的情况，比较次数是 n-1
最坏情况下，比较次数是n*(n-1)/2
发表于 2017-11-09 08:51:25 回复(0)
何同学~头像 何同学~
我们一般说的n2，其实就是 n*(n-1)/2  
所以这道题就是10*9/2 = 45
发表于 2015-09-02 01:05:55 回复(0)
lujo头像 lujo
🤣
发表于 2019-08-12 22:11:43 回复(0)
侯卿头像 侯卿
想多了，然后多减了一个1。。。是从9到0一共10次，而不是9到2。。
编辑于 2018-01-26 19:43:37 回复(0)
梦境迷离头像 梦境迷离
数据结构与算法分析机械工业专门讲了一般算法的下界上限
发表于 2017-12-12 17:17:28 回复(0)
shiyan娃娃头像 shiyan娃娃
冒泡排序在最坏的情况下，需要进行n/2遍的从前往后扫描和n/2遍的从后往前扫描，因此需要进行n(n-1)/2次比较.10（10-1）/2=45.
编辑于 2017-08-27 15:09:11 回复(0)
wanlanwalan头像 wanlanwalan

冒泡排序算法： 
for(int i=0; i<n; ++i)
{
    for(int j=1; j<n-i; ++j)
    {
        if(a[j-1]>a[j])
        {交换。。。}
    }
}
当i=0时，进行比较n-1次；
当i=1时，进行比较n-2次；
。。。
当i=n-1时，进行比较0次；
所以总的比较次数就是(n-1) + (n-2) + ... + 1 + 0 = n*(n-1)/2
发表于 2017-04-27 10:54:59 回复(0)
被支配的恐惧头像 被支配的恐惧
冒泡的算法就是
for(int i=0; i<n; ++i)
{
    for(int j=1; j<n-i; ++j)
    {
        if(a[j-1]>a[j])
        {交换。。。}
    }
}

当i=0时，进行比较n-1次；
当i=1时，进行比较n-2次；
。。。
当i=n-1时，进行比较0次；
所以总的比较次数就是(n-1) + (n-2) + ... + 1 + 0 = n*(n-1)/2
发表于 2017-04-09 17:36:39 回复(0)
牛客265482号头像 牛客265482号 
//冒泡排序的时间复杂度为n*(n-1)/2=O(n^2),则比较语句执行n*(n-1)/2 = 45次。

发表于 2016-04-01 10:22:23 回复(0)
codersong头像 codersong
最晚的情况是序列是逆序的，需比较(n-1)+(n-2)+......+1=n*(n+1)/2
发表于 2015-10-09 21:50:59 回复(0)
普米斯头像 普米斯
D
发表于 2015-09-10 13:48:43 回复(0)
郑元元头像 郑元元
如果题目要求是升序排列，而给出的数组恰好是降序，则此为最差情况，如：10,9,8,7,6,5,4,3,2,1 10要比较9次才可以正确放入 9要比较8次才可以正确放入 8要比较7次才可以正确放入 …… 结果为：9+8+7+……+2+1=45
发表于 2015-09-05 20:03:09 回复(0)
熊猫的斑竹先森头像 熊猫的斑竹先森
1+2+3+4+....+9=45
发表于 2015-09-05 14:33:03 回复(0)
媛头像 媛
考查时间复杂度
发表于 2015-09-05 14:32:52 回复(0)
丕子李头像 丕子李
我感觉是36次。9*（9-1）/2
发表于 2015-09-04 23:26:20 回复(0)
停停走走_123头像 停停走走_123
最坏的情况是反序吧比如，要求从小到大，但是序列是从大到小，10.9.8.7.6.5.4.3.2.1.
第一次冒泡 排序9次
第二次冒泡 排序8次
依次类推结果为(9+8+...+1)=(9+1)*9/2=45
发表于 2015-09-04 20:24:28 回复(0)
dkplatform头像 dkplatform
n*(n-1)/2
发表于 2015-09-04 19:42:22 回复(0)
提交观点

问题信息

排序
来自：腾讯2016研发工程师...
难度：
29条回答 15561浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号