插入排序

核心:

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

i(1 6 6 3)
ct[1]=1
ct[6]=2
ct[3]=1
o(1 3 6 6)

时间复杂度:

• 平均:$O(n+k)$
• 最优:$O(n+k)$
• 最坏:$O(n+k)$

空间复杂度：

• $?(n+k)$ //忘了用啥字母了

稳定性:

• 稳定(?

参考代码:

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

#include<iostream>
#define N 1000005
using namespace std;
int ct[N];
int main(){
	
	int n,t;
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>t;
		ct[t]++;
	}
	for(int i=0;i<=N;++i)
		if(ct[i]>0)
			cout<<i<<' ';
	
	
 return 0;
}