多關鍵字排序
很多時候，一個對象可以用多個特征值來刻畫它，可以把每個特征值看做一個關鍵字，比如撲克牌有花色和點數(shù)這兩個特征，如果所要求的順序由多個關鍵字聯(lián)合決定，我們就可以利用這種特征來使用多關鍵字排序方法，多關鍵字地位不是平等的，有優(yōu)先級大小。
如撲克牌排序，我們就可以規(guī)定花色比點數(shù)優(yōu)先，也就是說無論點數(shù)多少，只要花色大的就認為它是大牌，比如規(guī)定黑桃大于紅心，紅心大于梅花，梅花大于方塊。
多關鍵字排序有兩種思路：
高優(yōu)先級：MSD(先用高優(yōu)先級的關鍵字進行分組)
低優(yōu)先級：LSD(先用低優(yōu)先級的關鍵字進行分組)
高優(yōu)先級排序MSD
下邊我們先看高優(yōu)先級排序方式MSD，
比如有如下?lián)淇伺?，我們?guī)定花色優(yōu)先，花色從小到大關系如下圖：方塊，梅花，紅心，黑桃
第一步：我們先用高優(yōu)先級的關鍵字(花色)進行分組，如下圖
我們可以想象成四個盒子，把撲克牌按照花色扔進4個盒子中。
全部分進四個盒子之后，在每個組內進行排序（每個盒子內的排序算法隨意），每個盒子里邊元素排好序之后入下圖：
這里每個組內（盒子）的排序也可以繼續(xù)采用分組的方式，在每個盒子按低優(yōu)先級分組收集
保證每個組內元素排好序，再把這些排好序的各組的元素收集起來就可以了。如下圖
收集好之后，如下圖，就是已經(jīng)排好序的游戲序列。
低優(yōu)先級排序LSD
我們分析一下低優(yōu)先級，還以撲克牌為例
第一步：我們先用最低優(yōu)先級的關鍵字進行分組
第二步：分組分好之后進行收集
第三步：收集好的數(shù)據(jù)再按花色進行重新分組
第四步：把分組后數(shù)據(jù)再重新收集，就可以得到一個有序數(shù)組。
總結：
通過上邊例子我們會發(fā)現(xiàn)，整個過程我們并沒有進行排序工作，僅僅是進行了分組和收集
這個排序的創(chuàng)新點是它好像并沒有進行任何排序，而是通過不斷的分組收集，再分組再收集就完成了整個排序工作。
我們這里只有兩個關鍵字，如果有三個四個或者更多關鍵字，我們依然可以采用這種方式按照優(yōu)先級的高低來進行分組收集，把所有的分組工作做完之后，我們的排序工作就完成了。
注意點：關鍵字的空間不能太大，否則我們分組太多，效率會很低，這種排序適合哪種很多種關鍵字，但是每個關鍵字又不是很大的情況
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();
}
低優(yōu)先級排序類
import java.util.Arrays;
public class RadixSortCard {
//低優(yōu)先級排序
public static void lsdSort(Card[] arr) {
int len = arr.length;
// -------------------第一步 分組-------------------------
// 按點數(shù)存入桶
// 創(chuàng)建點數(shù)的桶,不算大小王{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];// 因為點數(shù)從1開始，這里數(shù)組做成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];// 創(chuàng)建花色的桶
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));
}
}
關鍵字拆分
有時候如果關鍵字空間太大，我們可以把一個關鍵字拆分為多個關鍵字，比如整數(shù)如果作為一個關鍵字，他的空間就太大了。如果問題中整數(shù)只是在一千以內，那我分成1000組顯然是不合適的，我們可以按十進制的位作為關鍵字，可以把個位，十位，百位看做三個關鍵字（優(yōu)先級 個位 < 十位 < 百位）。
下邊分析一下數(shù)值排序（高優(yōu)先級和低優(yōu)先級排序）
原文： https://blog.csdn.net/u011948899/article/details/78027838
最低位優(yōu)先法：先從最低位開始排序，再對次低位排序，直到對最高位排序后得到一個有序序列；具體過程如下圖所示：
初始數(shù)組序列為：15,25,105,78,34,21,32,41，按照個位數(shù)大小依次入桶；
將桶中數(shù)依次倒出，對于同一個桶中的數(shù)按先進先出順序倒出，結果為：21,41,32,34,15,25,105,78，再按十位數(shù)大小依次入桶；
將桶中數(shù)依次倒出，結果為：105,15,21,25,32,34,41,78，再按百位上數(shù)大小依次入桶，沒有百位的數(shù)則按百位為0入桶；
將桶中數(shù)倒出，結果為：15,21,25,32,34,41,78,105
最高位優(yōu)先法：先從最高位開始排序，再逐個對各分組按次高位進行子排序，循環(huán)直到最低位。
仍以序列：15,25,105,78,34,21,32,41為例，從最高位百位依次入桶，只有105有百位，其他百位按0算；檢測每個桶中的數(shù)據(jù)。當桶中的元素個數(shù)多于1個的時候，要對這個桶遞歸進行下一位的分組。
Java實現(xiàn)整數(shù)排序代碼(LSD MSD)：
import java.util.Arrays;
/**
* 基數(shù)排序，低優(yōu)先級（LSD）和高優(yōu)先級（MSD）
* @author Administrator
*
*/
public class RadixSort {
// 對數(shù)組arr進行低優(yōu)先級排序
public static void lsdSort(int[] arr) {
int len = arr.length;
// 先找出數(shù)組最大的數(shù)
int max = arr[0];
for (int i=1; i<len; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
// 求最大數(shù)的位數(shù)
double d = Math.pow(10, String.valueOf(max).length());
int[][] t = new int[10][len];//準備10個用于存放0-9的桶，每個桶最多存放數(shù)組長度len個元素
int[] num = new int[len];//記錄每個桶中存入元素個數(shù).
int bit = 1; // 個位1，十位10，百位100
while (bit < d) {
// 從個位開始，將元素裝入桶中
for (int a : arr) {
int m = (a / bit) % 10;//確定該數(shù)應該存入幾號桶（0,1,2,3,4,5,6,7,8,9）
t[m][num[m]] = a;
num[m]++;
}
// 按順序從桶中（0-9）依次取出所有元素，放入arr中繼續(xù)下一位循環(huán)
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;
// 取數(shù)組中最大值
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的桶，每個桶最多存放數(shù)組長度len個元素
int[] num = new int[len]; // 記錄每個桶中存入元素的個數(shù)
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) { // 如果桶中只有一個數(shù)則直接取出
arr[index++] = t[i][0];
} else if (num[i] > i) { //如果桶中不止一個數(shù)，則另存入數(shù)組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));
}
}
