程序员人生网站导航

算法#12--详解各种字符串排序算法和代码实现

栏目：php教程时间：2016-09-28 10:15:32

1.算法汇总

首先，来看1张各种字符串排序算法的汇总。前面的文章已介绍过插入排序、快速排序、归并排序和3向快速排序。这里不再介绍。

我们将重点详解：低位优先的字符串排序、高位优先的字符串排序和3向字符串快速排序。

2.低位优先的字符串排序

这类方法会从右向左检查键中的字符。如果将1个字符串看做1个256进制的数字，那末从右向左检查字符串就等价于先检查数字的最低位。

这类方法最合适用于键的长度都相同的字符串排序援用。

实现代码：


//低位优先的字符串排序
public class LSD 
{
    public static void sort(String[] a, int W)
    {//通过前W个字符将a[]排序
        int N = a.length;
        int R = 256;
        String[] aux = new String[N];

        for(int d = W - 1; d >= 0; d--)
        {//根据第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];
            }
        }
    }

    public static void main(String[] args) 
     {
        String[] a= {"4PGC938", "2IYE230", "3CI0720", "1ICK750", "1OHV845", "4JZY524", "1ICK750",
                "3CI0720", "1OHV845", "1OHV845", "2RLA629", "2RLA629", "3ATW723"};

        LSD.sort(a, 7);
        for(int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);
        } 
     }
}

运行轨迹：

3.高位优先的字符串排序

这类方法会从左到右检查键中的字符，首先查看的是最高位的字符。高位优先的字符串排序的吸引人的地方在于，它们不1定需要检查所有的输入就可以够完成排序。

高位优先的字符串排序和快速排序类似，由于它们都会将需要排序的数组切分为独立的部份并递归地用相同的方法处理子数组来完成排序。

它们的区分的地方在于高位优先的字符串排序算法在切分时仅使用键的第1个字符，而快速排序的比较则会触及键的全部。

接下来要学习的方法会将相同字符的键划入同1个切分。

实现代码：


//高位优先的字符串排序
public class MSD {
    private static int R = 256;     //基数
    private static final int M = 3;//小数组的切换阈值
    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)
    {//以第d个字符为键将a[lo]至a[hi]排序
        if(hi <= lo + M)
        {//快速排序
            InsertionSort(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);
        }
    }

    //快速排序
    private static void InsertionSort(String[] a, int lo, int hi, int d) 
    {   
        for( int i = lo; i < hi; i++) 
        { 
            for( int j=i+1; j>lo; j--) 
            {               
                if( a[j-1].compareTo(a[j]) <= 0)
                {
                    break;
                }
                String temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;              
            }
        }  
    }

    public static void main(String[] args) 
     {
        String[] a= {"she", "sells", "seashells", "by", "the", "sea", "shore", "the", "shells", "she",
            "sells", "are", "surely", "seashells"};

        MSD.sort(a);
        for(int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);
        } 
     }

}

运行轨迹：

这里用到了小型子数组。当要排序的数量，低于阈值，我们就将快速排序转换为插入排序。对高位优先的字符串排序算法它节俭的时间是非常可观的。

4.3向字符串快速排序

再要学习的方法会产生3个切分，分别对应被搜索的第1个字符小于、等于或大于切分键的第1个字符的情况。

高位优先的字符串排序可能会创建大量（空）子数组，而3向切分总是只有3个。因此3向字符串快速排序能够很好处理等值键、有较长公共前缀的键、取值范围较小的键和小数组–所有高位优先的字符串排序算法不善于的各种情况。

实际上，3向字符串快速排序是普通的快速排序和高位优先的字符串排序算法的结合。

实现代码：


//3向字符串快速排序
public class Quick3string {
    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)
            {
                swap(a, lt, i);
                lt++;
                i++;
            }
            else if(t > v) 
            {
                swap(a, gt, 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);
    }

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

    private static void swap(String[] a, int i, int j) 
    {
        String temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    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);
        for (int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);
        }
    }
}

运行轨迹：

------分隔线----------------------------

上一篇 Hadoop生态圈介绍

下一篇 win10 uwp 异步进度条

------分隔线----------------------------