String sort的几种方法

简介

　　在之前的一些排序算法中，主要是对一些数值的类型比较的比较多一点。而对于字符串类型来说，它有一些特殊的性质。如果按照传统的排序方法，对于字符串的比较性能其实还取决于字符串的长度以及相似程度。实际上，对于一些字符集的取值在一个比较小的范围内的情况，我们可以有一些比较高效率的算法。这里针对这些特殊的情况进行讨论。

　　假设给定的排序集合里元素，也就是每个字符都是在一个比较有限的范围里，比如说256个字符范围内。那么，我们可以利用这个特性做一些高效的处理。联想到之前讨论过的counting sort和radix sort方法。这里就是利用了这个特性。

 

Key-Indexed counting

　　在之前讨论couting sort 的文章里，曾经针对需要排序的元素为数字的情况进行过讨论。counting sort成立的一个前提是它里面所有的元素取值是在一个固定的范围内。假设这个数组里元素能取的最大值是k，那么每次我们要排序的时候只需要声明一个长度为k的数组a。每次碰到一个元素i就将a[i]对应的值加1。这样就统计出来了所有从小到大的元素的值的分布。剩下的就只是从小到达把这些值重新排列输出就可以了。

　　当然，在一些数字有一定长度而且它们的长度都一样的情况下。我们可以利用从高到低或者从低到高位逐位排序的方式来对数组进行排序。这就是radix sort的基本思路。它本质上就是在每一位的排序上都使用了couting sort。

　　借鉴前面对于数字的排序，我们对于字符串数组的排序也可以采用类似的方式：

 

            int[] count = new int[R + 1];
            //计算每个字符出现的频率
            for(int i = 0; i < n; i++)
                count[a[i].charAt(d) + 1]++;
            //将每个字符出现的频率转换为所在的索引
            for(int r = 0; r < R; r++)
                count[r + 1] += count[r];
            //将字符分布到具体的数组位置
            for(int i = 0; i < n; i++)
                aux[count[a[i].charAt(d)]++] = a[i];
            //将结果拷贝回数组
            for(int i = 0; i < n; i++)
                a[i] = aux[i];

 　　上述代码里的R表示当前字符的取值范围。在R值不大的时候它的效率还是相当可观的。在这个计数排序的基础上，我们可以得到一些不同的排序算法。

 

LSD sort

　　一种最典型的方法就是从最低位向最高位的方式依次排序，这种和前面的radix sort的思路基本上完全一样。不过在前面的基础上针对字符的情况稍微做一点修改。详细的代码实现如下：

 

public class LSD {
    public static void sort(String[] a, int w) {
        int n = a.length;
        int R = 256;
        String[] aux = new String[n];
        for(int d = w - 1; d >= 0; d--) {
            int[] count = new int[R + 1];
            for(int i = 0; i < n; i++)
                count[a[i].charAt(d) + 1]++;

            for(int r = 0; r < R; r++)
                count[r + 1] += count[r];

            for(int i = 0; i < n; i++)
                aux[count[a[i].charAt(d)]++] = a[i];

            for(int i = 0; i < n; i++)
                a[i] = aux[i];
        }
    }
}

　　对于等长的字符串，而且里面字符的取值在一个比较小范围内时，这种LSD排序的方式比较理想。那么，如果我们把条件稍微放宽一点，如果字符串的长度其实不是等长的呢？有没有办法利用前面的计数排序呢？

 

MSD

　　和前面LSD不一样的就是，我们可以采用从最高位到最低位排序的方式来排序，同时，它可以处理数组长度不一致的情况。一般来说，当数组长度一致的时候，我们定义一个对应的数组来映射它所在的索引，如果不一致的时候就会出现当访问到某个位置的时候，其中某个字符串已经超出访问范围了。这时候该怎么办呢？

　　对于超出字符串访问范围的，我们可以定义一个charAt(i)的方法，超过范围的元素返回索引值-1。这样所有超出原来范围的数组都可以集中统计在-1的这个位置上。在详细映射实现的时候，我们可以将数组的长度加长一位。所有映射到索引位置的元素加一，这样-1位置的元素就相当于新数组里索引为0的位置。这样可以得到一个实现：

 

public class MSD {
    private static int R = 256;
    private static final int M = 15;
    private static String[] aux;

    private static int charAt(String s, int d) {
        if(d < s.length()) return s.charAt(d);
        else return -1;
    }

    public static void sort(String[] a) {
        int n = a.length;
        aux = new String[n];
        sort(a, 0, n - 1, 0);
    }

    private static void sort(String[] a, int lo, int hi, int d) {
        if(hi <= lo + M) {
            Insertion.sort(a, lo, hi, d);
            return;
        }
        int[] count = new int[R + 2];
        for(int i = lo; i <= hi; i++)
            count[charAt(a[i], d) + 2]++;

        for(int r = 0; r < R + 1; r++)
            count[r + 1] += count[r];

        for(int i = lo; i <= hi; i++)
            aux[count[charAt(a[i], d) + 1]++] = a[i];

        for(int i = lo; i <= hi; i++)
            a[i] = aux[i - lo];

        for(int r = 0; r < R; r++)
            sort(a, lo + count[r], lo + count[r + 1] - 1, d + 1);
    }
}

　　这种实现显得稍微复杂一点，不过在一定程度上当超出长度的元素比较少的时候，应该可以有更进一步的优化空间。 

 

Three-way string quicksort

　除了上述两种排序的方式，还有一种比较有意思的排序方法。它借鉴了快速排序的思路。就是每次取一个字符串中某个位置的字符作为节点，将字符串数组按照这个节点划分成小于等于以及大于它的三个部分。然后类似于快速排序的方法，对于大于以及小于它的部分递归的进行排序。而对于等于这个节点的部分，如果有多个的话则进一步按照下一个位置的字符进行递归排序。

　　在排序的过程里，考虑到有相同元素的情况，它的实现和单纯的快速排序划分还稍微有点不一样。详细的实现代码如下：

 

public class Quick3string {
    private static int charAt(String s, int d) {
        if(d < s.length())
            return s.charAt(d);
        else return -1;
    }

    public static void sort(String[] a) {
        sort(a, 0, a.length - 1, 0);
    }

    private static void sort(String[] a, int lo, int hi, int d) {
        if(hi <= lo) return;
        int lt = lo, gt = hi;
        int v = charAt(a[lo], d);
        int i = lo + 1;
        while(i <= gt) {
            int t = charAt(a[i], d);
            if(t < v) exch(a, lt++, i++);
            else if(t > v) exch(a, i, gt--);
            else i++;
        }

        sort(a, lo, lt - 1, d);
        if(v >= 0) sort(a, lt, gt, d + 1);
        sort(a, gt + 1, hi, d);
    }
}

 　　由于exch方法仅仅是交换两个元素的位置，实现比较简单，这里就忽略了。这种方法对于有大量重复元素的字符串数组有比较好的排序效果。 

 

总结

　　虽说是对字符串数组进行排序。在传统的排序比较方法里，我们需要针对数组里每个元素比较的时候要从头到位的比对。有时候对于元素取值范围比较固定的情况可以有一定的优化空间。这里就利用了couting sort和radix sort的思路。而在有大量相同前缀部分的字符串数组排序方法里，我们可以考虑使用类似于快速排序的方法，每次取一个位对数组进行划分，这样逐步递归的实现排序。这里面的详细实现细节值得反复推敲。 

 

参考材料

algorithms