插入排序类似于玩扑克时抓牌的过程，玩家每拿到一张牌都要插入到手中已有的牌里，使之从小到大排好序。 现使用一个排好序的数组模拟插入排序，即输入一数时，要求按原来排序的规律将它插入数组中。

Question

问题遇到的现象和发生背景

如图所示，插入排序类似于玩扑克时抓牌的过程，玩家每拿到一张牌都要插入到手中已有的牌里，使之从小到大排好序。
现使用一个排好序的数组模拟插入排序，即输入一数时，要求按原来排序的规律将它插入数组中。
https://citel.bjtu.edu.cn/moodle/images/insertsort.png
输入：
输入共三行，第一行为数字N（N≤100000），表示原数组元素的个数。第二行为N个数字，即原数组的各元素值。第三行为一个数字，即输入的数。

输出：
输出一行，即排好序的数组，以空格间隔。

示例输入：
10
1 2 3 4 5 6 7 8 9 10

11

示例输出：
1 2 3 4 5 6 7 8 9 10 11

我写的代码时间超出限制，应如何修改

用代码块功能插入代码，请勿粘贴截图

#include<stdio.h>
int main()
{
    int n, m,t;
    long long int a[100009];
    scanf_s("%d", &n);
    for (int i =0; i < n; i++)
    {
        scanf_s("%lld", &a[i]);
    }
    scanf_s("%d", &m);
    a[n] = m;
    for (int i = 0; i < n; i++) 
    { 
        for (int j = 0; j < n - i; j++) 
        { 
            if (a[j]>a[j + 1]) 
            { 
                t = a[j];                
                a[j] = a[j + 1];                
                a[j + 1] = t; 
            } 
        } 
    }
    for (int i = 0; i <= n; i++)
    {
        printf("%lld ", a[i]);
    }
    return 0;
}

运行结果及报错内容

我的解答思路和尝试过的方法

超出时间限制，应如何处理？

Answer 1

这里有两个问题

1. long long int a[100009] 最好不要用long，用int就行了， 这样有两个不好，一个是占用空间多，
   二是运行的时间长需要计算的多了
2. 你这个用的是冒泡排序，不是快速排序，时间复杂度会高很多，因为你输入的数已经是排序好了的，假设插入的数据是 m
   你只要找到第一个 m<a[i]的位置就行了，然后在移动一下数组