数据结构与算法——字符串排序
对于许多排序应用，决定顺序的键都是字符串。下面将学习专门针对字符串类型的排序方法，这些方法比之前学习的通用排序方法（如冒泡、插入、归并等）更高效。
第一类方法是低位优先（Least-Signifcant-Digit First，LSD）的字符串排序方法。这个算法要求被排序的每个字符串长度都相等。它会把字符串当成数字，从字符串的右边开始向左检查字符（相当于从数字的最低位到高位）。
第二类方法是高位优先（MSD）的字符串排序。它不要求被排序的字符串等长，而且不一定需要检查所有的输入就能完成排序。该算法将从左开始向右检查字符（就像通常我们比较字符串那样），使用和快速排序类似的方法将字符串排序。
在学习低位优先的字符串排序时，最好先了解下计数排序和基数排序。上一篇文章中已经有详细介绍了，这里不再赘述。
低位优先的字符串排序LSD首先待排序的字符串长度均相同，设为W，从右向左以每个字符作为关键字，用计数排序法将字符串排序W次。由于计数排序法是稳定的，所以低位优先的字符串排序能够稳定地将字符串排序。
假设你对计数排序和基数排序都有一定的了解了，这里直接给出代码。
package Chap5; import java.util.Arrays; public class LSD { public static void sort(String[] a, int W) { // 每位数字范围0~9，基为10 int R = 256; int N = a.length; String[] aux = new String[N]; int[] count = new int[R+1]; // 共需要d轮计数排序, 从最后一位开始，符合从右到左的顺序 for (int d = W - 1; d >= 0; d--) { // 1. 计算频率，在需要的数组长度上额外加1 for (int i = 0; i < N; i++) { // 使用加1后的索引，有重复的该位置就自增 count[a[i].charAt(d) + 1]++; } // 2. 频率 -> 元素的开始索引 for (int r = 0; r < R; r++) { count[r + 1] += count[r]; } // 3. 元素按照开始索引分类，用到一个和待排数组一样大临时数组存放数据 for (int i = 0; i < N; i++) { // 填充一个数据后，自增，以便相同的数据可以填到下一个空位 aux[count[a[i].charAt(d)]++] = a[i]; } // 4. 数据回写 for (int i = 0; i < N; i++) { a[i] = aux[i]; } // 重置count[]，以便下一轮统计使用 for (int i = 0; i < count.length; i++) { count[i] = 0; } } } public static void main(String[] args) { String[] a = {"4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720", "1OHV845", "1OHV845","2RLA629", "2RLA629", "3ATW723"}; LSD.sort(a, 7); System.out.println(Arrays.toString(a)); } }