[已解决]这个题目在PTA上面超时了，请问要怎么改进

默默地

题目

5个数排序
这是一个签到题。要求你对五个数排序并且输出。例如：本题目要求读入一行五个数字，然后排序并输出排序后的五个数字。
输入格式:请在这里写输入格式。例如：输入在一行中并且给出5个数字
输出格式:请在这里描述输出格式。例如：对每一组输入，在一行中输出排序完的数字。（末尾无空格o(￣▽￣)ブ）
输入样例:在这里给出一组输入。例如：
3 2 1 4 5
输出样例:在这里给出相应的输出。例如：
1 2 3 4 5

我的代码

#include <stdio.h>

int main()
{
    int num[4];
    int i,j,temp;
    for(i=0;i<=4;i++)
    {
        scanf("%d",&num[i]);
    }
    for(i=0;i<4;i++)
    {
        for(j=i+1;j<=4;j++)
        {
            if(num[i]>num[j])
            {
                temp=num[i];
                num[i]=num[j];
                num[j]=temp;
            }
        }
    }
    for(i=0;i<=4;i++)
    {
        printf("%d ",num[i]);
    }
    printf("\b");
    return 0;
}

但结果是

                               
登录/注册后可看大图

而在codeblock里面是可以运行的，所以想问怎么改进，缩短代码运行时间。

最佳答案

月排行榜 / 总排行榜

jackz007

2021-10-19 11:07:04

        试试这个代码呢

#include <stdio.h>

int main(void)
{
        int d[5] , i , j , k                           ;
        for(i = 0 ; i < 5 ; i ++) scanf("%d" , & d[i]) ;
        for(i = 0 ; i < 4 ; i ++) {
                for(j = i + 1 ; j && d[j] < d[j - 1] ; j --) {
                        k = d[j - 1]                   ;
                        d[j - 1] = d[j]                ;
                        d[j] = k                       ;
                }
        }
        for(i = 0 ; i < 5 ; i ++) {
                if(i) printf(" ")                      ;
                printf("%d" , d[i])                    ;
        }
        printf("\n")                                   ;
}

跳转到最佳答案楼层

傻眼貓咪

只有 5 个数字，为什么会超时？

傻眼貓咪

你用的是插入排序法 Insertion Sort，时间复杂度：O(n^2)

jackz007

        试试这个代码呢

#include <stdio.h>

int main(void)
{
        int d[5] , i , j , k                           ;
        for(i = 0 ; i < 5 ; i ++) scanf("%d" , & d[i]) ;
        for(i = 0 ; i < 4 ; i ++) {
                for(j = i + 1 ; j && d[j] < d[j - 1] ; j --) {
                        k = d[j - 1]                   ;
                        d[j - 1] = d[j]                ;
                        d[j] = k                       ;
                }
        }
        for(i = 0 ; i < 5 ; i ++) {
                if(i) printf(" ")                      ;
                printf("%d" , d[i])                    ;
        }
        printf("\n")                                   ;
}

人造人

    int num[4];
    int i,j,temp;
    for(i=0;i<=4;i++)

人造人

傻眼貓咪 发表于 2021-10-19 10:53
只有 5 个数字，为什么会超时？

stack-buffer-overflow

傻眼貓咪

人造人 发表于 2021-10-19 12:25
stack-buffer-overflow

感恩，受教了，原来是栈缓冲区溢出啊

人造人

傻眼貓咪 发表于 2021-10-19 12:29
感恩，受教了，原来是栈缓冲区溢出啊

我一开始也觉得奇怪
只有 5 个数字，为什么会超时？

于是我先是百度找速度快的排序算法，然后又想到了内联函数内联汇编这些
我写完了归并排序，然后发现已经有别人回复了，我的代码就不贴了
那就看一看别人写的代码吧，然后发现两个算法差不多
然后发现了  stack-buffer-overflow
^_^

默默地

人造人 发表于 2021-10-19 12:38
我一开始也觉得奇怪
只有 5 个数字，为什么会超时？

谢谢，受教了