排序(二)桶排序,基数排序

一、桶排序

1.1 描述

如果我们有N个整数，范围从min到max（min 必须为正数），我们可以利用这个信息得到一种快速的排序，叫做桶式排序（bucket sort）。我们留置一个数组，称之为Count，大小为M (max - min +1)，并初始化为零。于是，Count有M个单元（或桶），开始时他们都是空的。当Ai被读入时，Count[Ai - len]增1。在所有的输入被读进以后，按顺序扫描数组Count，打印count[i] 次 的 i + len。输出的i+len 值就是排序完成的数据。该算法花费O（M+N）

1.2代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 桶式排序
 * @param data
 * @param min 最小值
 * @param max 最大值
 */
public  void bucketSort(int[] data, int min, int max) {
    //桶数组
    int[] bucket = new int[max - min + 1 ];
    // 读取源数据 ， 并将出现次数记录 ， 源数据 = 桶数组的下标值（需要加个 min ）
    for (int d : data) {
        bucket[d - min] ++;
    }
    //顺序读取桶数组 ， 打印桶数据不为0 的下标
    for (int i = 0 , k = 0; i < bucket.length; i++) {
        for (int j = 0; j < bucket[i]; j++) {
            data[k++] = i + min ;
        }
    }
}

二、基数排序

2.1 多关键字排序

很多时候，一个对象可以用多个特征值来刻画它，可以把每个特征值看做一个关键字，比如扑克牌有花色和点数这两个特征，如果所要求的顺序由多个关键字联合决定，我们就可以利用这种特征来使用多关键字排序方法，多关键字地位不是平等的，有优先级大小。
如扑克牌排序，我们就可以规定花色比点数优先，也就是说无论点数多少，只要花色大的就认为它是大牌，比如规定黑桃大于红心，红心大于梅花，梅花大于方块。多关键字排序有两种思路：
高优先级：MSD(先用高优先级的关键字进行分组)
低优先级：LSD(先用低优先级的关键字进行分组)

这里只进行简单描述，详细了解请看博客 https://www.jianshu.com/p/21c48bb32cff

2.2 基数排序描述

与桶排序的思想类似，如果桶排序的n很大，再建立一个m容量的数组就不合适了。

所以可以用多趟桶排序，桶的大小是m（一般取10），然后对每个数字的每一位（从低位到高位）进行桶排序，最后就达到了结果。

时间复杂度为：O(K*(n+m))（K表示需要循环的次数，就是序列中最大数字的位数）。

原理：每次将排序得到每一位的序列，下一次排序又在上一次排序的基础上进行，所以序列就变得有序了，即部分有序–>整体有序。

采用的是多关键字排序的 低优先级排序 ， 先将个位按桶排序排好序，在将百位进行桶排序 直到最高位排序完成。

2.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 基数排序
 * @param a
 */
public void  radixSort(int[] a){
    //最大值
    int max = Arrays.stream(a).max().orElseThrow(RuntimeException::new);
    int[]bucket = new int[10];
    //存储源数据 (暂时没想到好的方法)
    int[][] data = new int[10][10];
    //最大位数
    int maxIndex = String.valueOf(max).length();
    for (int i = 1; i <= maxIndex; i++) {
        for (int d : a) {
            // 【里面求位数】
            int t = d / (int) Math.pow(10, i - 1) % 10;
            bucket[ t] ++;
            data[t][bucket[ t]] = d;
        }
        //顺序读取桶数组 ， 打印桶数据不为0 的下标
        for (int b = 0 , k = 0; b < bucket.length; b++) {
            for (int j = 0; j < bucket[b]; j++) {
                // 从 data 中取出数据
                a[k++] = data[b][j+1];
            }
        }
        bucket = new int[10];
        data = new int[10][10] ;
    }
}