时间复杂度均为O(n)O(n)O(n)，但插入明显更快

#include <bits/stdc++.h> using namespace std; int n,x; int a[1005]; void work() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; cin>>x; if(x<a[1]) { cout<<x<<" "; for(int i=1;i<=n;i++) cout<<a[i]<<" "; return; } if(x>a[n]) { for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<x; return; } int low=lower_bound(a+1,a+1+n,x)-a; for(int i=1;i<low;i++) cout<<a[i]<<" "; cout<<x<<" "; for(int i=low;i<=n;i++) cout<<a[i]<<" "; } int main() { work(); return 0; }

#include <iostream> using namespace std; int main() { int n, x; cin >> n; int a[n+1]; for (int i = 0; i < n; i++) { cin >> a[i]; } cin >> x; int i = n-1; while (i >= 0 && a[i] > x) { a[i+1] = a[i]; i--; } a[i+1] = x; for (int i = 0; i <= n; i++) { cout << a[i] << " "; } return 0; }

插入后sort就行了

#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int num[n+1]; for(int i=0;i<n;i++){ cin>>num[i]; } cin>>num[n]; sort(num,num+n+1); for(int i=0;i<n+1;i++){ cout<<num[i]<<" "; } return 0; }

#include<bits/stdc++.h> using namespace std; int a[1005]; int main(){ int n; cin >> n; for(int i = 1;i <= n;i++) cin >> a[i]; int x; cin >> x; a[n+1] = x; sort(a+1,a+n+2); for(int i = 1;i <= n+1;i++) cout << a[i] << ' '; return 0; }

数据范围最大1e3，所以用快排sort不会超时，更方便 下面是我的代码：