字符串算法—字符串排序（下篇）
本⽂将介绍3区基数快速排序、后缀排序法。
1. 前⽂回顾
在中，我们介绍了键索引计数法、LSD基数排序、MSD基数排序。
但LSD基数排序要求需排序字符串的长度⼀致；MSD基数排序虽然对字符串的长度没要求，但其递归循环⾥的每次循环都需要进⾏很多操作，且需要额外的空间。 本⽂将介绍⼀种更⾼效的字符串排序⽅法：结合MSD基数排序和。如果对这两种算法不熟悉的，建议先去了解⼀下。
2. 3区基数快速排序（3-way radix quicksort）
从例⼦⼊⼿：与MSD基数排序⼀样，我们设定每个字符串的最后⼀位字符的下⼀个位置的空字符的键索为-1。a[]是拥有⼀堆字符串的字符串数组。
与MSD基数排序⼀样，每个字符配⼀个正数键索，⽤于⽐较字符间的⼤⼩。
⾸先，对a[0]（she）的第⼀个字符(s)进⾏3区快速排序：
3区快速排序会把整个数组分为3个区：
第⼀个区⾥的所有字符串的第⼀个字符都⽐（she）的第⼀个字符(s)⼩，它含有a[0]、a[1];
第⼆个区⾥的所有字符串的第⼀个字符都与（she）的第⼀个字符(s)相同，它含有a[2]~a[11];
字符串长度排序 第三个区⾥的所有字符串的第⼀个字符都⽐（she）的第⼀个字符(s)⼤，它含有a[12]、a[13]。
然后从上往下的，先看第⼀个区，此区含有多个字符串，对此区的第⼀个字符串(by)的第⼀个字符(b)进⾏3区快速排序：（为了⽅便观察，待排序的字符串⽤⿊⾊表
⽰）
3区快速排序会把整个区分为3个区：
第⼀个区⾥的所有字符串的第⼀个字符都⽐（by）的第⼀个字符(b)⼩，它含有a[0];
第⼆个区⾥的所有字符串的第⼀个字符都与（by）的第⼀个字符(b)相同，它含有a[1];
第三个区⾥的所有字符串的第⼀个字符都⽐（by）的第⼀个字符(b)⼤，它没有元素;
看第⼆个区，它只有⼀个字符串，此区排序完毕；
看第三个区，它没有字符串，此区排序完毕；
（为了⽅便观察，已排序完毕的字符串⽤绿⾊表⽰）
然后看下⼀个区，此区含有多个字符串，对此区的第⼀个字符串(seashells)的第⼆个字符(e)进⾏3区快速排序：
3区快速排序会把整个区分为3个区：
第⼀个区⾥的所有字符串的第⼆个字符都⽐（seashells）的第⼆个字符(e)⼩，它没有元素;
第⼆个区⾥的所有字符串的第⼆个字符都与（seashells）的第⼆个字符(e)相同，它含有a[2]~a[6];
第三个区⾥的所有字符串的第⼆个字符都⽐（seashells）的第⼆个字符(e)⼤，它含有a[7]~a[11];
看第⼆个区，它有多个字符串，对此区的第⼀个字符串(seashells)的第三个字符(a)进⾏3区快速排序：
3区快速排序会把整个区分为3个区：
第⼀个区⾥的所有字符串的第三个字符都⽐（seashells）的第三个字符(a)⼩，它没有元素;
第⼆个区⾥的所有字符串的第三个字符都与（seashells）的第三个字符(a)相同，它含有a[2]~a[4];
第三个区⾥的所有字符串的第三个字符都⽐（seashells）的第三个字符(a)⼤，它含有a[5]~a[6];
然后从上往下的，先看第⼀个区，它没有字符串，此区排序完毕；
看第⼆个区，它有多个字符串，对此区的第⼀个字符串(seashells)的第四个字符(s)进⾏3区快速排序：
3区快速排序会把整个区分为3个区：
第⼀个区⾥的所有字符串的第四个字符都⽐（seashells）的第四个字符(s)⼩，它含有a[2];
第⼆个区⾥的所有字符串的第四个字符都与（seashells）的第四个字符(s)相同，它含有a[3]~a[4];
第三个区⾥的所有字符串的第四个字符都⽐（seashells）的第四个字符(s)⼤，它没有元素;
然后从上往下的，先看第⼀个区，它只有⼀个字符串，此区排序完毕；
看第⼆个区，它有多个字符串，对此区的第⼀个字符串(seashells)的第五个字符(h)进⾏3区快速排序：
3区快速排序会把整个区分为3个区：
第⼀个区⾥的所有字符串的第五个字符都⽐（seashells）的第五个字符(h)⼩，它没有元素;
第⼆个区⾥的所有字符串的第五个字符都与（seashells）的第五个字符(h)相同，它含有a[3]~a[4];
第三个区⾥的所有字符串的第五个字符都⽐（seashells）的第五个字符(h)⼤，它没有元素;
然后从上往下的，先看第⼀个区，它没有字符串，此区排序完毕；
看第⼆个区，它有多个字符串，对此区的第⼀个字符串(seashells)的第六、七、⼋、九、⼗个字符(h)进⾏3区快速排序：（由于这两个字符串是⼀样的，排序结果不变，这⾥省略中间过程，直接到第⼗个字符的排序）
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论