键索引排序法

键索引排序法主要用来解决分组排序的问题。
例如：
一个班级有分为三个组，每个组编号1~3。

姓名	组别
Harry	1
Hermione	2
Draco	1
Diamond	3
Steve	3

需要对以上学生按照分组来排序，预期结果如下。

Harry Draco Hermione Diamond Steve

这种场景之下可以使用键索引排序法来实现。

int N = a.length
String[] aux = new String[N];
int[] count = new int[R+1];

//对数据做频率统计,a[i].key()为组数，count是频率统计的容器
for(int  i=0;i<N;i++)
  count[a[i].key()+1]++;
//频率转换为索引
for(int r = 0;r<R;r++)
count[r+1] += count[r]
//元素分类即排序
for(int i=0;i<N;i++)
aux[count[a[i].key]++] = a[i];

该算法的时间复杂度是O(N+R)，一般情况下N>>R，可以看做是O(N)的复杂度。频率转换为索引是理解该算法的关键之处，我们可以这样来看待这个问题，假设有一个hashmap对于碰撞的处理是简单插入到散列后的队列之后，key为组别而value是姓名，那么我们读取原始数据并根据组别插入hashmap，发生碰撞之后连接到尾部。最后从hashmap中按照组别顺序将数据取出来，这就是一个索引排序。现在我们统计每一个组别中数据的数量，并为此划分了空间大小（其实这变相的指定了每个组别的存放位置），将同组别的直接插入到相应位置，使用数组下标作为一个“哈希散列值”，更方便并且更有效率，这其实是整个算法的核心：频率转换为索引。

低位优先的字符串排序

索引排序的一个应用是低位优先的字符串排序。低位优先字符串排序针对的是等长的字符串数据的排序，该算法的思路是将ASCII码中一共256个值作为分组的依据，字符串从后向前对每一位做键索引排序。

public class TangLSD {
    public static void sort(String[] a, int W){
        int N = a.length;
        int R = 256;
        String[] aux = new String[N];
       //以下为对字符串从后向前每一个字符做索引排序
       for(int i=W-1;i>=0;i--){
           int[] count = new int[R+1];
           for(int j=0;j<N;j++){
               count[a[j].charAt(i)+1] ++;
           }
           //频率转换为索引
           for(int j=0;j<R;j++){
               count[j+1] += count[j];
           }
          //索引处填入字符串
           for(int j=0;j<N;j++){
               aux[count[a[j].charAt(i)]++]=a[j];
           }
          //没做一次索引我们会重新赋值一次
           for(int j=0;j<N;j++){
               a[j] = aux[j];
           }
       }
    }

    public static void main(String[] args){
        String[] strs = new String[]{"aadf","dvcd","wdsf","sacd","hgin"};
        sort(strs,1);
        for (String str:strs) {
            System.out.println(str);
        }
    }
}

结果如下

aadf dvcd hgin sacd wdsf

理解了键索引排序，低位优先的字符串排序理解起来就自然而然了。粗略的看时间复杂度是O(WR)+O(WN)，空间复杂度为R+N。

高位优先字符串排序

高位优先的排序方法其实可以看做“分治法”的一种具体实现，首先用键索引排序法对首字母做排序，按照首字母做划分，对于首字母相同的字符串做递归排序。