排序
快排，归并排序之前已经熟悉不再赘述
计数排序 复杂度O(n+m)
计数排序适于值域范围较小的数字排序，核心思想：
- 每个数字出现几次
- 统计完每个元素出现次数后，求一边前缀和，就知道了每个数字排完序后的序列中出席拿的为止的范围(第几小到第几小都是这个数字)
- 把数字填入相应为止
保证稳定性：
- 相同数字，越后出现拍后面
- 倒着确定每个位置数字最后排在第几位即可
流程：
代码:
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <array>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5+10;
int m = 1e5;
int n,a[N],c[N],r[N]; //n是共有多少个数，m为最大值
//c[N]存每个数出现次数，r为排序后每个数的位置下标对应原数组的下标
inline void countingsort()
{
memset(c, 0, sizeof(c));
for(int i = 1; i <= n; i++) ++c[a[i]];//统计每个数出现多少次
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= c[i]; j++)
{
cout<<i<<" ";
}
}
cout<<endl;
for(int i = 2; i<=m;i++) c[i] += c[i-1];
for(int i = n; i; i--) r[i] = c[a[i]]--;
for(int i = 1; i<=n; i++) cout<<r[i]<<" ";
cout<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for (int i = 1; i <= n ;i++) cin>>a[i];
countingsort();
return 0;
}
基数排序 复杂度O(nm)
将每个待排序元素拆成m个关键字，然后从前往后对m个关键字一次排序，每次排序使用上一次的排序结果
基数排序一般会用计数排序来完成关键字的排序
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <array>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
//基数排序基于计数排序
int n, m = 10, a[100001], sa[100001],v[100001], r[100001], c[10]; //sa[i]为当前第i个数在原序列为第几位，v[i]为第i个数的关键字的值
inline void countingsort()
{
memset(c, 0, sizeof(c));
for(int i=1;i<=n;i++) ++c[v[i]];
for(int i=1;i<10;i++) c[i] += c[i-1];
for(int i=n;i;i--) r[sa[i]]=c[v[sa[i]]]--; //r[sa[i]]为原来序列中sa[i]个数的rank值
for(int i=1;i<=n;i++) sa[r[i]]=i; //sa[r[i]]当前为第i个数的rank值在原序列的下标为i
}
inline void radixsort()
{
for(int i=1;i<=n;i++) sa[i]=i;//一开始当前第i个数在原序列第i位
int x=1;
for(int i=1; i<= m; i++, x*=10)
{
for(int j=1;j<=n;j++)
v[j] = a[j]/x%10;
countingsort();
}
for(int i=1;i<=n;i++) printf("%d ", a[sa[i]]);
printf("\n");
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
scanf("%d", &n);
for(int i=1; i<=n ;i++) scanf("%d",&a[i]);
radixsort();
return 0;
}