多关键字排序
很多时候，一个对象可以用多个特征值来刻画它，可以把每个特征值看做一个关键字，比如扑克牌有花色和点数这两个特征，如果所要求的顺序由多个关键字联合决定，我们就可以利用这种特征来使用多关键字排序方法，多关键字地位不是平等的，有优先级大小。
如扑克牌排序，我们就可以规定花色比点数优先，也就是说无论点数多少，只要花色大的就认为它是大牌，比如规定黑桃大于红心，红心大于梅花，梅花大于方块。
多关键字排序有两种思路：
高优先级：MSD(先用高优先级的关键字进行分组)
低优先级：LSD(先用低优先级的关键字进行分组)
高优先级排序MSD
下边我们先看高优先级排序方式MSD，
比如有如下扑克牌，我们规定花色优先，花色从小到大关系如下图：方块，梅花，红心，黑桃
第一步：我们先用高优先级的关键字(花色)进行分组，如下图
我们可以想象成四个盒子，把扑克牌按照花色扔进4个盒子中。
全部分进四个盒子之后，在每个组内进行排序（每个盒子内的排序算法随意），每个盒子里边元素排好序之后入下图：
这里每个组内（盒子）的排序也可以继续采用分组的方式，在每个盒子按低优先级分组收集
保证每个组内元素排好序，再把这些排好序的各组的元素收集起来就可以了。如下图
收集好之后，如下图，就是已经排好序的游戏序列。
低优先级排序LSD
我们分析一下低优先级，还以扑克牌为例
第一步：我们先用最低优先级的关键字进行分组
第二步：分组分好之后进行收集
第三步：收集好的数据再按花色进行重新分组
第四步：把分组后数据再重新收集，就可以得到一个有序数组。
总结：
通过上边例子我们会发现，整个过程我们并没有进行排序工作，仅仅是进行了分组和收集
这个排序的创新点是它好像并没有进行任何排序，而是通过不断的分组收集，再分组再收集就完成了整个排序工作。
我们这里只有两个关键字，如果有三个四个或者更多关键字，我们依然可以采用这种方式按照优先级的高低来进行分组收集，把所有的分组工作做完之后，我们的排序工作就完成了。
注意点：关键字的空间不能太大，否则我们分组太多，效率会很低，这种排序适合哪种很多种关键字，但是每个关键字又不是很大的情况
Java代码来模拟扑克牌排序
先做一个扑克牌类，和花色的枚举类
/**
* 扑克牌类
* @author Administrator
*
*/
public class Card {
private CardType type;
private int point;
public Card(CardType type, int point) {
this.type = type;
this.point = point;
}
public String toString() {
return "(" + type.getName() + " " + point + ")";
}
public CardType getType() {return type;}
public int getPoint() {return point;}
}
花色枚举类
/**
* 黑桃（Spade） > 红桃（Heart） > 梅花（Club） > 方块（Diamond）
*/
public enum CardType {
SPADE {// 黑桃
@Override
public int code() {
return 3;
}
@Override
public String getName() {return "黑桃";}
},HEART { // 红桃
@Override
public int code() {
return 2;
}
@Override
public String getName() {return "红桃";}
},CLUB { // 梅花
@Override
public int code() {
return 1;
}
@Override
public String getName() {return "梅花";}
},DIAMOND { // 方块
@Override
public int code() {
return 0;
}
@Override
public String getName() {return "方块";}
};
public abstract int code();
public abstract String getName();
}
低优先级排序类
import java.util.Arrays;
public class RadixSortCard {
//低优先级排序
public static void lsdSort(Card[] arr) {
int len = arr.length;
// -------------------第一步 分组-------------------------
// 按点数存入桶
// 创建点数的桶,不算大小王{A(1),2,3,4,5,6,7,8,9,10,J(11),Q(12),K(13)}同需13个桶
Card[][] t1 = new Card[14][len+1];// 因为点数从1开始，这里数组做成14个。
int[] num1 = new int[14];//每个桶中元素的下标
for (Card c : arr) {//存入桶中
int point = c.getPoint();
t1[point][num1[point]] = c;
num1[point]++;
}
// -------------------第二步 收集-------------------------
// 按顺序取出各桶中的元素
int index1 = 0;
for (int i = 0; i < 14; i++) {
if (num1[i] > 0) {// 桶中有元素
for (int j = 0; j < num1[i]; j++) {
if (t1[i][j] != null) {
arr[index1++] = t1[i][j];
}
}
}
}
// -------------------第三步 再分组-------------------------
//再先按花色存入桶
Card[][] t2 = new Card[4][len];// 创建花色的桶
int[] num2 = new int[4];//每个桶中元素的下标
for (Card c : arr) {
int typeCode = c.getType().code();
t2[typeCode][num2[typeCode]] = c;
num2[typeCode]++;
}
// -------------------第四步 再收集-------------------------
int index2 = 0;
for (int i = 0; i < 4; i++) {
if (num2[i] > 0) { // 桶中有元素
for (int j = 0; j < num2[i]; j++) {
if (t2[i][j] != null) {
arr[index2++] = t2[i][j];
}
}
}
}
}
public static void main(String[] args) {
Card[] arr = new Card[11];
Card c0 = new Card(CardType.HEART, 1);//红桃1
Card c1 = new Card(CardType.SPADE, 9);//黑桃9
Card c2 = new Card(CardType.SPADE, 2);//黑桃2
Card c3 = new Card(CardType.CLUB, 5);//梅花5
Card c4 = new Card(CardType.SPADE, 8);//黑桃8
Card c5 = new Card(CardType.DIAMOND, 12);//方块12
Card c6 = new Card(CardType.CLUB, 13);//梅花13
Card c7 = new Card(CardType.DIAMOND, 3);//方块3
Card c8 = new Card(CardType.HEART, 11);//红桃11
Card c9 = new Card(CardType.DIAMOND, 8);//方块8
Card c10 = new Card(CardType.HEART, 9);//红桃9
arr[0] = c0;
arr[1] = c1;
arr[2] = c2;
arr[3] = c3;
arr[4] = c4;
arr[5] = c5;
arr[6] = c6;
arr[7] = c7;
arr[8] = c8;
arr[9] = c9;
arr[10] = c10;
lsdSort(arr);
System.out.println(Arrays.toString(arr));
}
}
关键字拆分
有时候如果关键字空间太大，我们可以把一个关键字拆分为多个关键字，比如整数如果作为一个关键字，他的空间就太大了。如果问题中整数只是在一千以内，那我分成1000组显然是不合适的，我们可以按十进制的位作为关键字，可以把个位，十位，百位看做三个关键字（优先级 个位 < 十位 < 百位）。
下边分析一下数值排序（高优先级和低优先级排序）
原文： https://blog.csdn.net/u011948899/article/details/78027838
最低位优先法：先从最低位开始排序，再对次低位排序，直到对最高位排序后得到一个有序序列；具体过程如下图所示：
初始数组序列为：15,25,105,78,34,21,32,41，按照个位数大小依次入桶；
将桶中数依次倒出，对于同一个桶中的数按先进先出顺序倒出，结果为：21,41,32,34,15,25,105,78，再按十位数大小依次入桶；
将桶中数依次倒出，结果为：105,15,21,25,32,34,41,78，再按百位上数大小依次入桶，没有百位的数则按百位为0入桶；
将桶中数倒出，结果为：15,21,25,32,34,41,78,105
最高位优先法：先从最高位开始排序，再逐个对各分组按次高位进行子排序，循环直到最低位。
仍以序列：15,25,105,78,34,21,32,41为例，从最高位百位依次入桶，只有105有百位，其他百位按0算；检测每个桶中的数据。当桶中的元素个数多于1个的时候，要对这个桶递归进行下一位的分组。
Java实现整数排序代码(LSD MSD)：
import java.util.Arrays;
/**
* 基数排序，低优先级（LSD）和高优先级（MSD）
* @author Administrator
*
*/
public class RadixSort {
// 对数组arr进行低优先级排序
public static void lsdSort(int[] arr) {
int len = arr.length;
// 先找出数组最大的数
int max = arr[0];
for (int i=1; i<len; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
// 求最大数的位数
double d = Math.pow(10, String.valueOf(max).length());
int[][] t = new int[10][len];//准备10个用于存放0-9的桶，每个桶最多存放数组长度len个元素
int[] num = new int[len];//记录每个桶中存入元素个数.
int bit = 1; // 个位1，十位10，百位100
while (bit < d) {
// 从个位开始，将元素装入桶中
for (int a : arr) {
int m = (a / bit) % 10;//确定该数应该存入几号桶（0,1,2,3,4,5,6,7,8,9）
t[m][num[m]] = a;
num[m]++;
}
// 按顺序从桶中（0-9）依次取出所有元素，放入arr中继续下一位循环
int index = 0;
for (int i = 0; i < len; i++) {
if (num[i] != 0) {// 桶中有元素，则取出
for (int j = 0; j < num[i]; j++) {
arr[index++] = t[i][j];// 将i桶中元素取出，存入到arr中
}
}
num[i] = 0;
}
bit = bit * 10;
}
}
public static void msdSort(int[] arr) {
int len = arr.length;
// 取数组中最大值
int max = arr[0];
for (int i = 1; i < len; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
int maxL = String.valueOf(max).length();//获取素组中最长元素的长度
int bit = new Double(Math.pow(10, maxL - 1)).intValue();
int[][] t = new int[10][len]; //准备10个用于存放0-9的桶，每个桶最多存放数组长度len个元素
int[] num = new int[len]; // 记录每个桶中存入元素的个数
for (int a : arr) { //按最高位入桶
int m = (a / bit) % 10;
t[m][num[m]] = a;
num[m]++;
}
int index = 0;
for (int i = 0; i < len; i++) {
if (num[i] == 1) { // 如果桶中只有一个数则直接取出
arr[index++] = t[i][0];
} else if (num[i] > i) { //如果桶中不止一个数，则另存入数组arr2，递归
int[] arr2 = new int[num[i]];
for (int j = 0; j < num[i]; j++) {
arr2[j] = t[i][j];
msdSort(arr2); // 递归方法
}
}
}
}
public static void main(String[] args) {
int[] arr = {12,1,20,59,123,321,652};
lsdSort(arr);
System.out.println(Arrays.toString(arr));
int[] arr2 = {12,1,20,56,123,321,652};
lsdSort(arr2);
System.out.println(Arrays.toString(arr2));
}
}
