这两个排序有什么不同,哪个更快
for(i=0;i<len-1;i++)
{
        for(j=i+1;j<len;j++)
        {
                if(a[i]<a[j])
            {

            }
        }
}
for(i=0;i<len-1;i++)
{
        for(j=0;j<len-i-1;j++)
            {
                    if(a[j]<a[j+1])
        {

        }
            }
}

我用第二个就Time Limit Exceed.用第一个或者sort函数就Accepted.

4个回答

第一个是冒泡排序,第二个排序容易出现死循环

这两个排序算法本质上是没区别的,第一个的思路是把大的值冒泡到数组最前面,第二个的思路是把小的值冒泡到最后面,从算法上时间复杂度一样
出现你这种情况可能是和某一次的数据有关系,你可以看一下是不是你的输入数据比较特殊,导致第一个排序交换的次数比较少

显然,两个代码的循环次数是一样的
所以执行时间取决于你if之间的代码,而这部分代码被你省略了。
非要细究的话,两段代码在cpu中执行,涉及到分支预测的命中率和缓存访问的命中率。
第一个程序的缓存命中率会比较差一些,而分支预测的命中率取决于你的数据是否相对来说是有序的,如果越有序会越好一些。

第一个是选择排序,第二个是冒泡排序。

选择相较于冒泡在比较次数上没有优势,但是在交换次数上会少很多,因为选择在一轮比较下来只用交换一次。

所以选择比冒泡是有时间优势的。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐