字符串排序

    对于许多排序应用，决定顺序的键都是字符串。这里将分享两类完全不同的字符串排序方法，三种不同的字符串排序算法。

    第一类是低位优先（LSD）的字符串排序，这个算法是从右到左检查键中的字符，要求字符串大小相同且必须走完全部字符，才能完成排序。

第二类是高位优先（MSD）的字符串排序，和低位相反，高位是从左到右检查键中的字符，不要求字符串大小相同，也不一定要走完所有字符才完成排序。

    在学习这两种排序算法之前，应该先了解一下键索引计数法，这种方法本身就很实用，同时也是本节将要学习的两三中字符串排序算法的基础。键索引计数法在排序归类比较实用，比如将学生按小组排序，下面是键索引计数法的步骤：

    1 频率统计，计数每个键出现的频率

    2, 将频率转化为索引

    3，将数据分类

    4，回写

按照步骤，给出下面的代码：

输出：

    接下来，学习低位优先（LSD）字符串排序算法，下面是代码：

输出：

排序轨迹：

高位优先（MSD）字符串排序算法：

先来看高位优先的字符串排序的示意图：

根据示意图和算法思想，给出如下代码：

输出：

排序轨迹：

三向字符串快速排序

三向字符串快速排序根据高位优先的字符串排序算法改进快速排序，根据键的首字母进行三向切分，仅在中间子数组中的下一个子继续递归排序，示意图如下：

代码如下所示：

输出：

排序轨迹：