字符串排序

字符串排序

利用字符串的特殊性质将字符串排序,比通用的排序算法效率更高

1.低位优先的字符串排序(LSD)

/**
 * 低位优先的字符串排序(LSD)
 * 概述: 适合相同长度的字符串排序,是稳定排序
 * 思想: 键索引计数法
 * 步骤: 从低位开始每轮取一个字符,使用键索引计数法排序,直到最高位结束
 */
public class LSD {
    public static void sort(String[] a,int w){
        int N = a.length;
        int R = 256;
        String[] aux = new String[N];
        int[] count = new int[R+1];
        for(int d=w-1;d>=0;d--) {//使用键索引计数法进行w轮排序
            //统计频率
            for(int i=0;i<N;++i)
                count[a[i].charAt(d)+1]++;
            //计算索引
            for(int i=0;i<R;++i)
                count[i+1] += count[i];
            //数据分类
            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];
            Arrays.fill(count,0);
        }
    }
}

2.高位优先的字符串排序(MSD)

/**
 * 高位优先的字符串排序(MSD)
 * 概述: 通用的字符串排序算法
 *       缺点: 对于较长相同前缀的字符串进行排序会产生大量小数组
 * 思想: 键索引计数法
 * 步骤: 使用键索引计数法每轮去一个字符从高位开始排序
 */
public class MSD {
    private static int R = 256;
    private static int M = 15;
    private static String[] aux;

    public static void sort(String[] a){
        int N = a.length;
        aux = new String[N];
        int[] count = new int[R+2];
        sort(a,0,N,0);
    }
    private static void sort(String[] a,int lo,int hi,int d){
        //if(lo >= hi-1) return;
        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 i=0;i<R+1;++i)
            count[i+1] += count[i];
        //数据分类
        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 i=0;i<R;i++)
            sort(a,lo+count[i],lo+count[i+1],d+1);
    }
    private static int charAt(String s,int d){
        if(d < s.length()) return s.charAt(d);
        return -1;
    }
}

2.1插入排序

/**
 * 插入排序
 */
public class Insertion {
    public static void sort(String[] a,int lo,int hi,int d){
        for(int i=lo+1;i<hi;++i){
            for(int j=i;j>lo && less(a[j],a[j-1],d);j--)
                exch(a,j,j-1);
        }
    }
    //比较
    private static boolean less(String a,String b,int d){
        int alen = a.length();
        int blen = b.length();
        int min = Math.min(alen,blen);
        while(d < min){
            int c1 = a.charAt(d);
            int c2 = b.charAt(d);
            if(c1 != c2) return c1 - c2 < 0;
            d++;
        }
        return alen - blen < 0;
        //return a.substring(d).compareTo(b.substring(d)) < 0;
    }
    //交换
    private static void exch(String[] a,int i,int j){
        String temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

3.三向字符串快速排序

/**
 * 三向字符串快速排序
 * 概述: 通用字符串排序算法,适合处理含有较长相同前缀的字符串
 * 步骤: 从高位开始对单个字符进行三向切分的快速排序,若按照v切分,则一轮结束后
 *       小于v部分 < 等于v部分 < 大于v部分, 对于等于v部分的下一位字符进行排序
 *       其他部分正常排序
 */
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(lo >= hi) return;    //可以在较短时使用插入排序优化
        int v = charAt(a[lo],d); //取第一个为切分点,v = -1时为没有字符
        int lt = lo,gt = hi;
        int i = lt + 1;
        while(i <= gt){//从切分点下一个开始逐个归位
            int t = charAt(a[i],d);
            if(t < v) exch(a,i++,lt++); //小于v放到v左边
            else if(t > v) exch(a,i,gt--);//大于v放到右边(往末尾放)
            else i++;
        }
        // v == -1 时不会有小于v的部分,等于v的部分无需再排序
        if(v >= 0 ) sort(a,lo,lt-1,d);
        if(v >= 0 ) sort(a,lt,gt,d+1);
        sort(a,gt+1,hi,d);
    }
    //交换
    private static void exch(String[] a,int i, int j){
        String temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    private static int charAt(String s,int d){
        if(d < s.length()) return s.charAt(d);
        return -1;
    }
}