后缀数组学习笔记

1. 前置知识：基数排序

1.1. 思想

现有如下序列：3,44,38,5,47,15,36,32,50，现在要用基数排序算法排序，要怎么做？

基数排序的初始状态如下：

1. 按照个位将原序列中的数分组，放入对应的集合

2. 将分好的数按照个位的顺序取出，得到：

3. 将序列中的数重新按照十位分组，放入对应集合：

4. 将每一位上的数按从下到上的顺序依次取出，就是答案

在数更多或位数更多的情况下，重复此过程即可

1.2. 代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[105],cnt[15],b[105];
int main()
{
	scanf("%d",&n);
	int mx=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		mx=max(mx,a[i]);
	}
	int d=0;
	while(mx>0)
	{
		mx/=10;
		d++;
	}
	int tmp=1;
	for(int i=1;i<=d;i++)
	{
		for(int j=0;j<10;j++) cnt[j]=0;
		for(int j=1;j<=n;j++)
		{
			int k=(a[j]/tmp)%10;
			cnt[k]++;
		}
		for(int j=1;j<10;j++)
		{
			cnt[j]+=cnt[j-1];
		}
		for(int j=n;j>0;j--)
		{
			int k=(a[j]/tmp)%10;
			b[cnt[k]]=a[j];
			cnt[k]--;
		}
		for(int j=1;j<=n;j++)
		{
			a[j]=b[j];
		}
		tmp*=10;
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}