插入排序

核心:

• 累计元素出现的次数
• for example:

i(1 6 3)
6>3
1<3
1 3 6
o

时间复杂度:

• 平均:$O(n^2)$
• 最优:$O(n)$
• 最坏:$O(n^2)$

空间复杂度：

• $?(1)$ //忘了用啥字母了

稳定性:

• 稳定

参考代码:

• 注：代码代表输入n个数，进行插入排序

#include<iostream>
using namespace std;
int a[1005];
int main(){
	
	int n;
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	
	for(int i=2;i<=n;++i){
		int t=a[i];
		int j=i-1;
		while(a[j]>t && j>=1){
			a[j+1]=a[j];
			--j;
		}
		a[j+1]=t;
	}
	
	for(int i=1;i<=n;++i)cout<<a[i]<<' ';
	
 return 0;
}