[数据结构拾遗]字符串排序算法总结

Bertha 。 2022-02-23 06:48 237阅读 0赞

![1240][]

# 前言 #

**本专题旨在快速了解常见的数据结构和算法。**

**在需要使用到相应算法时，能够帮助你回忆出常用的实现方案并且知晓其优缺点和适用环境。并不涉及十分具体的实现细节考究。**

# 字符串排序算法简介 #

对于许多排序应用，决定顺序的键都是字符串。

其主要思想是利用比较，根据字符的有限性通过计数的方式来划分字符串的排名位置。

主要介绍以下几种方式：

*  预备知识：键索引计数法
 *  低位优先的字符串排序 LSD string sort
 *  高位优先的字符串排序 MSD string Sort
 *  三向字符串快速排序 Three-way string quicksort

**字符串排序算法要求大家先理解：基数排序和计数排序**

[排序算法最强总结及其代码实现][Link 1]

# 常用方法 #

## 预备知识：键索引计数法 ##

首先我们需要了解一个预备知识：键索引计数法

**键索引计数法作为三种字符串排序算法中两种的基础，本身也很适用于小整数键的简单排序。**

键索引计数法主要分为四步：统计频率，将频率转换为索引，数据分类，回写。

**原理图：**

![1240 1][]

**举例说明：**

比如数组`a={1,2,3,4,2,3,4,2,1,3,4,2,3,4}`，它里面重复的数字比较多，不重复的只有1，2，3，4，这时就可以用此方法。

（例子来源：[https://www.jianshu.com/p/be5b67139396）][https_www.jianshu.com_p_be5b67139396]

1.  频率统计

统计各个数字出现的次数，

1出现了2次
    2出现了4次
    3出现了4次
    4出现了4次

需要**用一个5位的数组记录**（比所需数字多一位），原因留给各位看官思考。

1.  将频率转化为索引

前面我们记录了各自数字的次数，并用数组保存

a[0]=0，
    a[1]=2,
    a[2]=4，
    a[3]=4，
    a[4]=4

> 这里从1开始计数，而不是从0，并不是为了与排序的数字对应，而是为了计算索引的方便，任意键的起始索引均为所有较小键的频率之和，我们就可以a\[i+1\]+=a\[i\]递推得到，这样a\[0\]=0，a\[1\]=2，a\[2\]=6，a\[3\]=10，a\[4\]=14，这样第一个数字（即1）的起始位置为 0，第2个数字（即 2）的起始位置为2…

**多一个位置的原因：好处已经体现出来了，第一个就是用来标记最开始的起始位置的**

1.  数据分类

得到各个数字的起始索引，接下来就是将原数组进行归类，将相同的数字放在一起，这里我们用一个临时的数组进行记录

1.  回写回原数组

最后将临时数组中的值写会原数组

**代码实现：**

public class countSort {
        public static void  main(String[] args){
            int[] nums={2,3,4,1,2,4,3,1,2,2,1};
            countSort sort=new countSort();
            sort.indecCountIndex(nums);
        }
    
        public void indecCountIndex(int[] nums){
            int[] count=new int[6];
             //计算频率
            for(int i=0;i<nums.length;i++){
                count[nums[i]+1]++;
            }
           //将频率转化为索引
            for(int i=1;i<count.length;i++){
                count[i]=count[i]+count[i-1];
            }
          //数据分类
            int[] aux=new int[nums.length];
            for(int i=0;i<nums.length;i++){
                aux[count[nums[i]]++]=nums[i];
            }
          //回写数据（我这里是打印）
            for(int i=0;i<nums.length;i++){
                System.out.print(aux[i]+" ");
            }
        }
    }

## 低位优先的字符串排序 LSD string sort ##

**定义：**

*  待排序的字符串长度：W

**适用范围：**

低位优先排序在我们的生活中经常见到，比如银行卡号的排序、车牌的排序以及电话号码的排序等

**原理：**

从右向左以每个字符作为关键字，用键索引计数法将字符串排序W次。由于计数排序法是稳定的，所以低位优先的字符串排序能够稳定地将字符串排序。

**轨迹图：**

![1240 2][]

![1240 3][]

**代码实现：JAVA**

摘自：[https://www.cnblogs.com/sun-haiyu/p/7877651.html][https_www.cnblogs.com_sun-haiyu_p_7877651.html]

算法（第四版）也有实现

import java.util.Arrays;
    
    public class LSD {
        public static void sort(String[] a, int W) {
            // 每位数字范围0~9，基为10
            int R = 256;
            int N = a.length;
            String[] aux = new String[N];
            int[] count = new int[R+1];
    
            // 共需要d轮计数排序, 从最后一位开始，符合从右到左的顺序
            for (int d = W - 1; d >= 0; d--) {
                // 1. 计算频率，在需要的数组长度上额外加1
                for (int i = 0; i < N; i++) {
                    // 使用加1后的索引，有重复的该位置就自增
                    count[a[i].charAt(d) + 1]++;
                }
                // 2. 频率 -> 元素的开始索引
                for (int r = 0; r < R; r++) {
                    count[r + 1] += count[r];
                }
    
                // 3. 元素按照开始索引分类，用到一个和待排数组一样大临时数组存放数据
                for (int i = 0; i < N; i++) {
                    // 填充一个数据后，自增，以便相同的数据可以填到下一个空位
                    aux[count[a[i].charAt(d)]++] = a[i];
                }
                // 4. 数据回写
                for (int i = 0; i < N; i++) {
                    a[i] = aux[i];
                }
                // 重置count[]，以便下一轮统计使用
                for (int i = 0; i < count.length; i++) {
                    count[i] = 0;
                }
    
            }
        }
    
        public static void main(String[] args) {
            String[] a = {"4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720",
            "1OHV845", "1OHV845","2RLA629", "2RLA629", "3ATW723"};
            LSD.sort(a, 7);
            System.out.println(Arrays.toString(a));
        }
    }

上面程序将打印如下内容

[1ICK750, 1ICK750, 1OHV845, 1OHV845, 1OHV845, 2IYE230, 2RLA629, 2RLA629, 3ATW723, 3CIO720, 3CIO720, 4JZY524, 4PGC938]

## 高位优先的字符串排序 MSD string Sort ##

**参考：**

[https://blog.csdn.net/weixin\_41427400/article/details/79851043][https_blog.csdn.net_weixin_41427400_article_details_79851043]

**适用范围：**

**MSD与LSD比较起来，拥有更强的普适性，它不需要字符串的长度相同即可对字符串数组进行排序；**

在生活中的使用也比LSD更多一些，比如字典里的排序就是MSD的情况，当然还有很多，这里就不再举例了。

**原理：**

MSD的核心思想是分治算法，即将大问题分为小问题来解决，其思想与快速排序类似。

先对最高位的字符进行排序，将排序后的字符串进行分组——最高位相同的在一组；在对同一组的进行MSD排序，不过此时以第二位字符进行排序，直到排完最低位，算法结束。(如图3所示)

![image.png][]

> 思想讲起来总是很简单，不过当中的一些细节确实我们需要注意的。一个显而易见的问题是怎么处理结尾字符的问题，因为MSD运行字符的长度不同，那么总会有字符串先结束，这是我们就需要对这些字符串进行处理。如果我们每个字符都去判断显然会很麻烦，因此我们选择一种巧妙的方式使用一个CharAt(string, int)函数来返回字符串对应下标的字符，当对应下标不存在的时候我们返回-1；

/* 转换函数:返回字符串中对于索引的字符
     * 参数:s:想要进行转换的字符串，i:字符索引
     * 返回值:对应索引的字符，若超出字符串长度返回-1
     */
    char CharAt(string s, int i) {
    	if (i < s.length())
    		return s[i];
    	else
    		return -1;
    	}

这样我们就可以把字符串结尾的情况同其余情况一起处理，同时保证了已结尾的字符串会在未结尾的字符串之前！

**代码实现：**

详见算法（第四版）第五章或者如下网址C++实现：

[https://blog.csdn.net/weixin\_41427400/article/details/79851043][https_blog.csdn.net_weixin_41427400_article_details_79851043]

**提升性能：**

在数值排序中提到过一次优化排序效率的方法：当待排序数组的长度较小时，使用插入排序。同样的，该方法也适应与高位优先字符串排序，而且这种优化一般情况下也是必须的，有专家做过实验，在数据量巨大时，将长度小于10的子数组排序切换到插入排序，可以将排序的效率提升十倍左右。

## 三向字符串快速排序 Three-way string quicksort ##

MSD对包含大量重复键的字符串进行排序时，效率十分低下。三向字符串快速排序可以很好的解决这个问题，其是MSD和快速排序的结合版。

**适用范围：**

**非常适用于有共同前缀的字符串**

### 预备知识：三向切分的快速排序（数字快速排序的改进算法） ###

**参考：**

[https://www.jianshu.com/p/0966f989974d][https_www.jianshu.com_p_0966f989974d]

要理解三向字符串快速排序，需要先理解好三向切分的快速排序。

传统快速排序中，可能出现大量重复元素，最特殊的情况：一个数组中所有元素都相同，此时无需继续排序了，但是普通的快速排序算法还是会对数组进行切分。基于此可以将数组切分成三部分，分别对应小于、等于、大于切分元素的数组元素。

> 我们来看这种被称为三向切分的快速排序。它从左到右遍历数组一次，维护一个指针lt使得a\[low…lt-1\]中的元素都小于v，一个指针gt使得a\[gt + 1…high\]中的元素都大于v，一个指针i使得a\[lt…i-1\]中的元素都等于v，a\[i…gt\]中的元素暂定。一开始i和low相等。随着循环，a\[i…gt\]越来越小，即gt-i不断减小，当i > gt时循环结束。循环中进行下面的操作：

*  如果a\[i\]小于v，将a\[i\]和a\[lt\]交换，lt和i都加1；
 *  如果a\[i\]大于v，将a\[i\]和a\[gt\]交换，gt减1；
 *  如果a\[i\]等于v，将i加1

上面的这些操作保证了最后i > gt可以推出循环。

![1240 4][]

下面是三向切分快速排序的实现代码：

public class Quick3way {
    
        public static void sort(Comparable[] a) {
            shuffle(a);
            sort(a, 0, a.length - 1);
        }
    
        private static void sort(Comparable[] a, int low, int high) {
            if (high <= low) {
                return;
            }
    
            int lt = low;
            int gt = high;
            int i = low + 1;
            // 切分元素
            Comparable v = a[low];
            while (i <= gt) {
                int cmp = a[i].compareTo(v);
                if (cmp < 0) {
                    swap(a, lt++, i++);
                } else if (cmp > 0) {
                    swap(a, i, gt--);
                } else {
                    i++;
                }
            }
            // 现在a[lo..lt-1] < v=a[lt..gt] < a[gt+1..high]成立
            // 切分元素相同的数组不会被递归算法访问到，对其左右的子数组递归排序
            sort(a, low, lt - 1);
            sort(a, gt + 1, high);
        }
    }

对于存在大量重复元素的数组，这种方法比标准的快速排序要快。三向切分的最坏情况是所有元素各不相同，这时会比标准的快速排序要慢，因为比起标准的快速排序使用了更多的比较。

对于包含大量重复元素的数组，三向切分的快速排序算法将排序时间从线性对数级降低到线性级别，因此时间复杂度介于O(N)和O(Nlg N)之间，这依赖于输入数组中重复元素的数量。

### 三向字符串快速排序 ###

我们可以利用上面学习的三向切分的数字快速排序思想，将**字符串**数组切分成三个子数组：

*  一个含有所有首字母小于切分字符的子数组
 *  一个含有所有首字母等于切分字符的子数组
 *  一个含有所有首字母大于切分字符的子数组。

然后递归地对这三个数组排序，要注意对于所有首字母等于切分字符的子数组，在递归排序时应该忽略首字母（就像MSD中那样）。

**递归调用轨迹:**

![image.png][image.png 1]

**代码实现：**

在三向切分的数字快速排序的基础上稍加修改

import java.util.Arrays;
    
    public class Quick3String {
        // 切换为插入排序的阈值
        private static int M = 15;
    
        public static void sort(String[] a) {
            sort(a, 0, a.length - 1, 0);
        }
    
        private static void sort(String[] a, int low, int high, int d) {
            if (high <= low + M) {
                insertSort(a, low, high, d);
                return;
            }
    
            int lt = low;
            int gt = high;
            int i = low + 1;
            // 切分字符v是a[low]的第d个字符
            int v = charAt(a[low], d);
            while (i <= gt) {
                int t = charAt(a[i], d);
                if (t < v) {
                    swap(a, lt++, i++);
                } else if (t > v) {
                    swap(a, i, gt--);
                } else {
                    i++;
                }
            }
            // 现在a[lo..lt-1] < v=a[lt..gt] < a[gt+1..high]成立
            // 切分元素相同的数组不会被递归算法访问到，对其左右的子数组递归排序
            sort(a, low, lt - 1, d);
            // 所有首字母与切分字符相等的子数组，递归排序，像MSD那样要忽略都相同的首字母
            if (v >= 0) {
                sort(a, lt, gt, d+ 1);
            }
            sort(a, gt + 1, high, d);
        }
    
        private static void swap(String[] a, int p, int q) {
            String temp = a[p];
            a[p] = a[q];
            a[q] = temp;
        }
    
        private static int charAt(String s, int d) {
            if (d < s.length()) {
                return s.charAt(d);
            } else {
                return -1;
            }
        }
    
        private static void insertSort(String[] a, int low, int high, int d) {
            for (int i = low + 1; i <= high; i++) {
                // 当前索引如果比它前一个元素要大，不用插入;否则需要插入
                if (less(a[i], a[i - 1], d)) {
                    // 待插入的元素先保存
                    String temp = a[i];
                    // 元素右移
                    int j;
                    for (j = i; j > low && less(temp, a[j - 1], d); j--) {
                        a[j] = a[j - 1];
                    }
                    // 插入
                    a[j] = temp;
                }
            }
        }
    
        private static boolean less(String v, String w, int d) {
            return v.substring(d).compareTo(w.substring(d)) < 0;
        }
    
        public static void main(String[] args) {
            String[] a = {"she", "sells", "seashells", "by", "the", "sea", "shore", "the",
                    "shells", "she", "sells", "are", "surely", "seashells"};
            Quick3String.sort(a);
            System.out.println(Arrays.toString(a));
        }
    }

三向切分的快速排序使用子数组的第一个元素作为切分点，三向切分的字符串快速排序使用子数组的第一个字符串的第d个字符作为切分字符。

在递归对子数组排序时，相比三向切分的快速排序，三向切分的字符串快速排序多了这么一个判断，这句的意思是只要还没到字符串的末尾（v = -1说明到达，其余均未到达），所有首字母与切分字符相等的子数组也需要递归排序，不过要像MSD那样，忽略掉相同的首字母，处理下一个字符。

# 总结 #

字符串排序算法选择：

![1240 5][]

# 参考 #

*  算法（第四版）:第五章第一节
 *  [https://www.cnblogs.com/sun-haiyu/p/7877651.html][https_www.cnblogs.com_sun-haiyu_p_7877651.html]
 *  [http://lixinzhang.github.io/string-sorts-zi-fu-chuan-pai-xu.html][http_lixinzhang.github.io_string-sorts-zi-fu-chuan-pai-xu.html]
 *  [https://www.jianshu.com/p/be5b67139396][https_www.jianshu.com_p_be5b67139396 1]
 *  [https://blog.csdn.net/weixin\_41427400/article/details/79851043][https_blog.csdn.net_weixin_41427400_article_details_79851043]
 *  [https://blog.csdn.net/acmdream/article/details/74687035][https_blog.csdn.net_acmdream_article_details_74687035]
 *  [https://www.jianshu.com/p/0966f989974d][https_www.jianshu.com_p_0966f989974d]
 *  [https://www.jianshu.com/p/5beb3e73361d][https_www.jianshu.com_p_5beb3e73361d]

# 关注我 #

我是蛮三刀把刀，后端开发。主要关注后端开发，数据安全，爬虫等方向。微信：yangzd1102

Github：[@qqxx6661][qqxx6661]

个人博客：

*  CSDN：[@qqxx6661][qqxx6661 1]
 *  知乎：[@Zhendong][Zhendong]
 *  简书：[@蛮三刀把刀][Link 2]
 *  掘金：[@蛮三刀把刀][Link 3]

### 原创博客主要内容 ###

*  Java知识点复习全手册
 *  Leetcode算法题解析
 *  剑指offer算法题解析
 *  SpringCloud菜鸟入门实战系列
 *  SpringBoot菜鸟入门实战系列
 *  Python爬虫相关技术文章
 *  后端开发相关技术文章

### 个人公众号：Rude3Knife ###

![个人公众号：Rude3Knife][Rude3Knife]

**如果文章对你有帮助，不妨收藏起来并转发给您的朋友们~**

[1240]: /images/20220223/4296b12e74b14591af7d9d33eabcf5ff.png
[Link 1]: https://blog.csdn.net/qqxx6661/article/details/79568935
[1240 1]: /images/20220223/ede0acb283b04d5190ef51db459af608.png
[https_www.jianshu.com_p_be5b67139396]: https://www.jianshu.com/p/be5b67139396%EF%BC%89
[1240 2]: /images/20220223/a5ab3808b35c4c598651f709f3e0292a.png
[1240 3]: /images/20220223/92fd1a44f08742f5bcb9425e7cc6cf16.png
[https_www.cnblogs.com_sun-haiyu_p_7877651.html]: https://www.cnblogs.com/sun-haiyu/p/7877651.html
[https_blog.csdn.net_weixin_41427400_article_details_79851043]: https://blog.csdn.net/weixin_41427400/article/details/79851043
[image.png]: /images/20220223/c755ec4288834f2ab13aad59e6aac6b3.png
[https_www.jianshu.com_p_0966f989974d]: https://www.jianshu.com/p/0966f989974d
[1240 4]: /images/20220223/bc4d850b4aa742e99fcde87d0f41ad7c.png
[image.png 1]: /images/20220223/e49c605a08554841945987bfc3d87c36.png
[1240 5]: /images/20220223/f78773234bf3469e84216fbf2b48b197.png
[http_lixinzhang.github.io_string-sorts-zi-fu-chuan-pai-xu.html]: http://lixinzhang.github.io/string-sorts-zi-fu-chuan-pai-xu.html
[https_www.jianshu.com_p_be5b67139396 1]: https://www.jianshu.com/p/be5b67139396
[https_blog.csdn.net_acmdream_article_details_74687035]: https://blog.csdn.net/acmdream/article/details/74687035
[https_www.jianshu.com_p_5beb3e73361d]: https://www.jianshu.com/p/5beb3e73361d
[qqxx6661]: https://github.com/qqxx6661
[qqxx6661 1]: http://blog.csdn.net/qqxx6661
[Zhendong]: https://www.zhihu.com/people/yang-zhen-dong-1/
[Link 2]: https://www.jianshu.com/u/b5f225ca2376
[Link 3]: https://juejin.im/user/5b48015ce51d45191462ba55
[Rude3Knife]: /images/20220223/81ad8130e13d4a5daed6b47f87dc46e5.png