lsd 特征点匹配代码_2018-09-24 多关键字排序（基数排序LSD + MSD）「建议收藏」

多关键字排序

很多时候，一个对象可以用多个特征值来刻画它，可以把每个特征值看做一个关键字，比如扑克牌有花色和点数这两个特征，如果所要求的顺序由多个关键字联合决定，我们就可以利用这种特征来使用多关键字排序方法，多关键字地位不是平等的，有优先级大小。

如扑克牌排序，我们就可以规定花色比点数优先，也就是说无论点数多少，只要花色大的就认为它是大牌，比如规定黑桃大于红心，红心大于梅花，梅花大于方块。

多关键字排序有两种思路：

高优先级：MSD(先用高优先级的关键字进行分组)

低优先级：LSD(先用低优先级的关键字进行分组)

高优先级排序MSD

下边我们先看高优先级排序方式MSD，

比如有如下扑克牌，我们规定花色优先，花色从小到大关系如下图：方块，梅花，红心，黑桃

0.png

第一步：我们先用高优先级的关键字(花色)进行分组，如下图

我们可以想象成四个盒子，把扑克牌按照花色扔进4个盒子中。

1.png

全部分进四个盒子之后，在每个组内进行排序(每个盒子内的排序算法随意)，每个盒子里边元素排好序之后入下图：

2.png

这里每个组内(盒子)的排序也可以继续采用分组的方式，在每个盒子按低优先级分组收集

保证每个组内元素排好序，再把这些排好序的各组的元素收集起来就可以了。如下图

3.png

收集好之后，如下图，就是已经排好序的游戏序列。

4.png

低优先级排序LSD

我们分析一下低优先级，还以扑克牌为例

第一步：我们先用最低优先级的关键字进行分组

5.png

第二步：分组分好之后进行收集

image.png

第三步：收集好的数据再按花色进行重新分组

image.png

第四步：把分组后数据再重新收集，就可以得到一个有序数组。

image.png

image.png

总结：

通过上边例子我们会发现，整个过程我们并没有进行排序工作，仅仅是进行了分组和收集

这个排序的创新点是它好像并没有进行任何排序，而是通过不断的分组收集，再分组再收集就完成了整个排序工作。

我们这里只有两个关键字，如果有三个四个或者更多关键字，我们依然可以采用这种方式按照优先级的高低来进行分组收集，把所有的分组工作做完之后，我们的排序工作就完成了。

注意点：关键字的空间不能太大，否则我们分组太多，效率会很低，这种排序适合哪种很多种关键字，但是每个关键字又不是很大的情况

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，按照个位数大小依次入桶；

11.png

将桶中数依次倒出，对于同一个桶中的数按先进先出顺序倒出，结果为：21,41,32,34,15,25,105,78，再按十位数大小依次入桶；

22.png

将桶中数依次倒出，结果为：105,15,21,25,32,34,41,78，再按百位上数大小依次入桶，没有百位的数则按百位为0入桶；

33.png

将桶中数倒出，结果为：15,21,25,32,34,41,78,105

最高位优先法：先从最高位开始排序，再逐个对各分组按次高位进行子排序，循环直到最低位。

仍以序列：15,25,105,78,34,21,32,41为例，从最高位百位依次入桶，只有105有百位，其他百位按0算；检测每个桶中的数据。当桶中的元素个数多于1个的时候，要对这个桶递归进行下一位的分组。

高优先级.png

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

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));

}

}