低位字符优先算法 Java的实现及原理

低位字符优先算法的基础就是键索引计数法，他的思想是从后往前对每一个字符为键都进行键索引计数排序，直到当前所选择的键为第一个字符，这样就要求全部字符串的比较部分一定是连续且相等长度的。

思路：
1.在外部定义一系列变量，一个字符串数组AUX用于缓存和 回写。一个R作为count数组的键位。一个index作为当前key在string中的索引位置。
2.循环递增index，进入循环进行一次键索引计数排序
3.在index=string的最开头一个char时做最后一次循环出来后结束循环。

这样看起来似乎没有什么道理，但是在每一次循环时都根据当前的键进行了排序也就是在当前所在的键这一列是有序的，之后在对下一个键进行排序也就是在前一列有序的基础上对下一列有序，这样就变成了以开头为大的排序。当前一个相同时就时按照后一个排序。

代码：

/**
 * 低位优先字符串排序
 */
public class suanfa12 {
    public static void main(String[] args) {
        String[] strings = {
                "abc",
                "abd",
                "cbd",
                "cba",
                "bac",
                "bbd",
                "dea",
                "dac",
        };

        lfs(strings,3);

        for (String string : strings) {
            System.out.println(string);
        }
    }

    public static void lfs(String[] a,int w){
        int length = a.length;
        String[] aux = new String[length];
        for (int i =w-1;i>=0;i--){
            int[] count = new int[257];
            //统计频率
            for (String s : a) {
                count[s.charAt(i)+1]++;
            }
            //转换频率为索引位
            for (int i1 = 0; i1 < 256; i1++) {
                count[i1+1] += count[i1];
            }

            //将排好序的string存入aux数组
            for (int i1 = 0; i1 < length; i1++) {
                aux[count[a[i1].charAt(i)]++] = a[i1];
            }
            //回存
            for (int i1 = 0; i1 < length; i1++) {
                a[i] = aux[i];
            }
        }
    }
}