铺垫

简单语法基础

CPP

memset(x,0,sizeof(int) * M);
memcpy(x,y,sizeof(int) * M);

理解为

x=0

或者

x=y

。

计数排序（Counting Sort）

非比较型，有稳定性。给出一种较短的实现（

x[]

排序到

y[]

）。

CPP

mx=*max_element(x+1,x+1+n);
for(int i=1;i<=n;i++)cnt[x[i]]++;
for(int v=1;v<=mx;v++)cnt[v]+=cnt[v-1];
for(int i=n;i>=1;i--)y[cnt[x[i]]--]=x[i];

cnt[v]

表示：来一个数值

v

，该放在哪里。时间复杂度为

O(n+V)

，其中

V

为值域大小。

优点： 线性，稳定。
缺点： 时空复杂度依赖值域，无法解决大值域问题。

提炼：

计数器数组（桶）
计数器前缀和
倒序定排名

计数排序是特殊的桶排序，其每个桶只存一种元素。

桶排序（Bucket Sort）

先把值域分块为若干桶，每个桶再排序。

基数排序（Radix Sort）

核心：选基数。

基数排序解决了计数排序大值域无法开数组的问题。
具有稳定性。

基数排序逐位使用计数排序。

CPP

for(i = 0,1,2,3 ... ) 对数组以第 i 位数组做稳定的计数排序;

基为

2

：计数排序会被简化。
基为

10^6

：此时

[1,10^{18}]

内整数都是广义三位数，可以排的快。

id rk

id[i]

表示排序后第

i

，原来是第几个。

rk[i]

代表原来第

i

个，排序后是第几个。

例：比赛排名表就是

id

表。

id[rk[i]]=rk[id[i]]=i

id

存的是编号。

rk

存的是排名。

后缀数组（Suffix Array, SA）

记忆：“撒”数组。

对字符串所有后缀排序。（字典序）

sa \approx id

但不完全相等。

例：aabaaaab

sa = \{4,5,6,1,7,2,8,3\}

rk[i]

表示

i

开头的后缀串的排名。

sa[r]

表示后缀串排序后第

r

小的后缀串开头位置。

同理

rk[sa[x]]=sa[rk[x]]=x

。

怎么求 SA？

显然存前后缀空间复杂度为

O(n^2)

。

基数排序+广义字串长度倍增

不断对长度为

2^k

的字串进行基数排序。

理解为比赛。
abba____
先排序 abba 四字符。

选手：a,b,b,a
得到

sa=\{1,4,2,3\}

每轮会把开头取不到前缀的淘汰，加入后面带 _ 的。

id[i]

表示当前长度

2^k

，只后最后

2^{k-1}

，排名第

i

小的字串开头位置。
且具体实现的时候可以根据上一轮次获得第一轮的排名，故基数排序只要一轮。

怎么想到倍增

答：排序对象特殊，有重复信息可以利用。

字符串基础 II

文章操作

铺垫