$时间复杂度$

$最好：O(n)$

$最差：O(n^2)$

$平均：O(n^2)$

$空间复杂度$

$原地排序：O(1)$

$算法稳定性：稳定$

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
constexpr int N=1e4+7;
int a[N],n;
void sort(int a[],int n){
	for(int i=2;i<=n;i++){
		int key=a[i];
		int j=i-1;
		while(j>=1&&a[j]>key){
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=key;
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a,n);
	for(int i=1;i<=n;i++) cout<<a[i]<<" ";
	return 0;
}