搜索
bottom↓
回复: 15

c语言,如何优化程序运行时间

[复制链接]

出0入0汤圆

发表于 2020-10-27 20:49:42 | 显示全部楼层 |阅读模式
开课吧学习平台做闯关题,这个闯不过去了,有大神给优化一下吗,总是提醒运行超出限制时间, 在其他平台这个可以没问题。

这是题干:给予 10 个乱序输入的整数。你需要(任选一种排序方法)将它们从大到小进行排序后输出;
#include <stdio.h>
void swap(int *a,int *b)
{
    int k;
    k = *a;
    *a = *b;
    *b = k;
}
int main() {
    int n = 10;
    int numbers[10];
    int i;
    int j;
    // 读入给定的数字
    for (i = 0; i < n ;i++)
    {
        scanf("%d", &numbers[i]);
    }
    for(i = 0;i < n; i++)
     {  
        for(j = 0;j < n-i;j++)
        {
            if(numbers[j] < numbers[j+1])
            {
                swap(&numbers[j],&numbers[j+1]);
            }
        }
    }
    for(i = 0;i < n;i++)
    {
        printf("%d",numbers[i]);  
        if(i != (n-1))
        {
            printf(" "); //最后一个整数后面不能有空格
        }
    }
    return 0;
}

出0入90汤圆

发表于 2020-10-27 20:58:43 来自手机 | 显示全部楼层
你这个排序算法不行,优化也没多大意义,改算法吧

出0入984汤圆

发表于 2020-10-27 21:02:53 | 显示全部楼层
直接用qsort库函数多省心

出0入442汤圆

发表于 2020-10-27 22:21:13 来自手机 | 显示全部楼层
aammoo 发表于 2020-10-27 20:58
你这个排序算法不行,优化也没多大意义,改算法吧

这只有10个数,根据经验,小于100个数我都通通冒泡,效率最高。lz这估计是平台bug,编译出来死循环了。

出0入0汤圆

发表于 2020-10-28 08:18:03 | 显示全部楼层
本帖最后由 剑舞 于 2020-10-28 08:19 编辑

出0入0汤圆

 楼主| 发表于 2020-10-28 10:16:16 | 显示全部楼层
aammoo 发表于 2020-10-27 20:58
你这个排序算法不行,优化也没多大意义,改算法吧

对,改变算法,今天尝试一下,不用冒泡法

出0入0汤圆

发表于 2020-10-28 11:50:28 来自手机 | 显示全部楼层
冒泡的最差情况是n!
不考虑开销,试一试用链表插值排,
初始化链表o1,
排序,最差情况,n*n,n个数据,循环n遍
输出o1

出0入0汤圆

 楼主| 发表于 2020-10-29 18:11:33 | 显示全部楼层
改变了算法就行了
下面代码替代冒泡法
for(i = 0;i < n; i++)
    {   
        max = numbers[i];
        for(j = i;j < n;j++)
        {
            if(max < numbers[j])
            {
                max = numbers[j];
                index = j;
            }
            if(j == n-1 && max == numbers[index] )
                {
                    swap(&numbers[i],&numbers[index]);

                }        
        }
    }

出0入0汤圆

 楼主| 发表于 2020-10-29 18:12:38 | 显示全部楼层
zyqcome 发表于 2020-10-28 11:50
冒泡的最差情况是n!
不考虑开销,试一试用链表插值排,
初始化链表o1,

小白还写不出来链表 ,请朋友不吝赐教

出0入0汤圆

 楼主| 发表于 2020-10-29 18:50:06 | 显示全部楼层
Himem 发表于 2020-10-27 21:02
直接用qsort库函数多省心

厉害,函数后面在研究研究你说的这个函数

出0入0汤圆

发表于 2020-10-30 08:54:17 | 显示全部楼层
圈养的野马 发表于 2020-10-29 18:12
小白还写不出来链表 ,请朋友不吝赐教

你把它想复杂了,就是串在一起的 struct 用指针连起来

这样用的的好处是不会像数组排,需要移动数组

麻烦的是,可能需要一个指针来记录最小的一个,

不记录的话,最后需要一个递归调用的输出

出0入0汤圆

发表于 2020-10-30 10:23:23 | 显示全部楼层
本帖最后由 csq463276932 于 2020-10-30 10:35 编辑

楼主位的程序应该有问题。
   for(i = 0;i < n; i++)
     {  
        for(j = 0;j < n-i;j++)
        {
            if(numbers[j] < numbers[j+1])
            {
                swap(&numbers[j],&numbers[j+1]);
            }
        }
    }
__________________________________________
要改成下面这样才能正确输出数据。
   for(i = 0;i < n; i++)
     {  
        for(j = 0;j < n-1-i;j++)
        {
            if(numbers[j] < numbers[j+1])
            {
                swap(&numbers[j],&numbers[j+1]);
            }
        }
    }

出0入0汤圆

发表于 2020-10-30 17:13:44 | 显示全部楼层
    for(i = 0; i < n; i++)
    {
        for(j =i+1; j < n; j++)
        {
            if(numbers[i] <numbers[j])     
            {
                swap(&numbers[i], &numbers[j]);
            }
        }
    }

出0入0汤圆

 楼主| 发表于 2020-11-2 11:23:02 | 显示全部楼层
csq463276932 发表于 2020-10-30 10:23
楼主位的程序应该有问题。
   for(i = 0;i < n; i++)
     {  

对,用你写的这两个确实能行,看来不是算法的问题呢,这个先把小的往后挪

出0入0汤圆

 楼主| 发表于 2020-11-2 11:27:16 | 显示全部楼层
csq463276932 发表于 2020-10-30 17:13
for(i = 0; i < n; i++)
    {
        for(j =i+1; j < n; j++)

这个是先把大的往前面挪

出0入0汤圆

 楼主| 发表于 2020-11-2 11:28:35 | 显示全部楼层
zyqcome 发表于 2020-10-30 08:54
你把它想复杂了,就是串在一起的 struct 用指针连起来

这样用的的好处是不会像数组排,需要移动数组

哦   那我后面把指针链表再学习一下回来在研究研究
回帖提示: 反政府言论将被立即封锁ID 在按“提交”前,请自问一下:我这样表达会给举报吗,会给自己惹麻烦吗? 另外:尽量不要使用Mark、顶等没有意义的回复。不得大量使用大字体和彩色字。【本论坛不允许直接上传手机拍摄图片,浪费大家下载带宽和论坛服务器空间,请压缩后(图片小于1兆)才上传。压缩方法可以在微信里面发给自己(不要勾选“原图),然后下载,就能得到压缩后的图片】。另外,手机版只能上传图片,要上传附件需要切换到电脑版(不需要使用电脑,手机上切换到电脑版就行,页面底部)。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

手机版|Archiver|amobbs.com 阿莫电子技术论坛 ( 粤ICP备2022115958号, 版权所有:东莞阿莫电子贸易商行 创办于2004年 (公安交互式论坛备案:44190002001997 ) )

GMT+8, 2024-5-8 20:08

© Since 2004 www.amobbs.com, 原www.ourdev.cn, 原www.ouravr.com

快速回复 返回顶部 返回列表