基数排序、桶排序和计数排序的区别

1.桶排序(Bucket Sort)

基本思路是：
将待排序元素划分到不同的痛。先扫描一遍序列求出最大值 maxV 和最小值 minV ，
设桶的个数为 k ，则把区间 [minV, maxV] 均匀划分成 k 个区间，每个区间就是一个桶。将序列中的元素分配到各自的桶。
对每个桶内的元素进行排序。可以选择任意一种排序算法。
 将各个桶中的元素合并成一个大的有序序列。
假设数据是均匀分布的，则每个桶的元素平均个数为 n/k 。假设选择用快速排序对每个桶内的元素进行排序，
那么每次排序的时间复杂度为 O(n/klog(n/k)) 。
总的时间复杂度为 O(n)+O(m)O(n/klog(n/k)) = O(n+nlog(n/k)) = O(n+nlogn-nlogk 。
当 k 接近于 n 时，桶排序的时间复杂度就可以金斯认为是 O(n) 的。即桶越多，时间效率就越高，而桶越多，空间就越大。

2.计数排序(Counting Sort)

是一种O(n)的排序算法，其思路是开一个长度为 maxValue-minValue+1 的数组，然后
分配。扫描一遍原始数组，以当前值- minValue 作为下标，将该下标的计数器增1。
收集。扫描一遍计数器数组，按顺序把值收集起来。
举个例子， nums=[2, 1, 3, 1, 5] , 首先扫描一遍获取最小值和最大值，
 maxValue=5 , minValue=1 ，于是开一个长度为5的计数器数组 counter ，
1. 分配。统计每个元素出现的频率，得到 counter=[2, 1, 1, 0, 1] ，例如 counter[0] 表示值 0+minValue=1 出现了2次。
2. 收集。 counter[0]=2 表示 1 出现了两次，那就向原始数组写入两个1， 
3. counter[1]=1 表示 2 出现了1次，那就向原始数组写入一个2，依次类推，最终原始数组变为 [1,1,2,3,5] ，排序好了。
  计数排序本质上是一种特殊的桶排序，当桶的个数最大的时候，就是计数排序。

3.基数排序

是一种非比较排序算法，时间复杂度是 O(n) 。它的主要思路是，
1. 将所有待排序整数（注意，必须是非负整数）统一为位数相同的整数，位数较少的前面补零。一般用10进制，
2. 也可以用16进制甚至2进制。所以前提是能够找到最大值，得到最长的位数，设 k 进制下最长为位数为 d 。
3. 从最低位开始，依次进行一次稳定排序。这样从最低位一直到最高位排序完成以后，整个序列就变成了一个有序序列。
举个例子，有一个整数序列，0, 123, 45, 386, 106，下面是排序过程：
第一次排序，个位，000 123 045 386 106，无任何变化
第二次排序，十位，000 106 123 045 386
第三次排序，百位，000 045 106 123 386
最终结果，0, 45, 106, 123, 386, 排序完成。
为什么同一数位的排序子程序要用稳定排序？因为稳定排序能将上一次排序的成果保留下来。
例如十位数的排序过程能保留个位数的排序成果，百位数的排序过程能保留十位数的排序成果。
能不能用2进制？能，可以把待排序序列中的每个整数都看成是01组成的二进制数值。
那这样的话，岂不是任意一个非负整数序列都可以用基数排序算法？
理论上是的，假设待排序序列中最大整数为2 4 . 1，则最大位数 d=64 ，时间复杂度为 O(64n) 。
可见任意一个非负整数序列都可以在线性时间内完成排序。
既然任意一个非负整数序列都可以在线性时间内完成排序，那么基于比较排序的算法有什么意义呢？
基于比较的排序算法，时间复杂度是 O(nlogn) ，看起来比 O(64n) 慢，仔细一想，其实不是， O(nlogn) 只有当序列非常长，
达到2^64 个元素的时候，才会与 O(64n) 相等，因此，64这个常数系数太大了，
大部分时候， n 远远小于2^64，基于比较的排序算法还是比 O(64n) 快的。
当使用2进制时， k=2 最小，位数 d 最大，时间复杂度 O(nd) 会变大，空间复杂度 O(n+k) 会变小。
当用最大值作为基数时， k=maxV 最大， d=1 最小，此时时间复杂度 O(nd) 变小，
但是空间复杂度 O(n+k) 会急剧增大，此时基数排序退化成了计数排序。

比较时间复杂度和空间复杂度。

其中, d 表示位数， k 在基数排序中表示 k 进制，在桶排序中表示桶的个数， maxV 和 minV 表示元
素最大值和最小值。

• 首先，基数排序和计数排序都可以看作是桶排序。
• 计数排序本质上是一种特殊的桶排序，当桶的个数取最大( maxV-minV+1 )的时候，就变成了计数排序。
• 基数排序也是一种桶排序。桶排序是按值区间划分桶，基数排序是按数位来划分；基数排序可以看做是多轮桶排序，每个数位上都进行一轮桶排序。
• 当用最大值作为基数时，基数排序就退化成了计数排序。 当使用2进制时， k=2 最小，位数 d 最大，时间复杂度 O(nd)
  会变大，空间复杂度 O(n+k) 会变小。
• 当用最大值作为基数时， k=maxV 最大， d=1 最小，此时时间复杂度 O(nd) 变小，但是空间复杂度 O(n+k)
  会急剧增大，此时基数排序退化成了计数排序。

桶排序和基数排序比较 2.0

1、算法思路

桶排序

桶排序(Bucket Sort)假设输入数据服从均匀分布，然后将输入数据均匀地分配到有限数量的桶中，然后对每个桶再分别排序，对每个桶再使用插入排序算法，最后将每个桶中的数据有序的组合起来。假设输入是由一个随机过程生成，该过程将元素均匀的分布在一个区间[a,b]上，在[a,b]之间放置一定数量的桶，由于桶排序和计数排序一样均对输入的数据进行了某些假设限制，因此比一般的基于比较的排序算法复杂度低。

基数排序

基数排序假设输入数据属于一个小区间内的整数，对每一位上进行进桶，出桶；根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。

2、实现过程

桶排序过程

1.初始化装入连续区间元素的n个桶，每个桶用来装一段区间中的元素。

2.遍历待排序的数据，将其映射到对应的桶中，保证每个桶中的元素都在同一个区间范围中。

3.对每个桶进行排序，最终将所有桶中排好序的元素连起来。

图来自https://blog.csdn.net/cauchyweierstrass/article/details/49919559

桶排序其中也蕴含着分治的策略，联想之前的计数排序，基数排序就像是桶排序的一个特例，一个数据一个桶。并且和散列(哈希，hash)似乎也有千丝万缕的关系。

基数排序实现过程

是根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。

设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。

我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以0~9来表示的。

所以我们不妨把0~9视为10个桶。

我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是0，将这个数存入编号为0的桶中。

分类后，我们在从各个桶中，将这些数按照从编号0到编号9的顺序依次将所有数取出来。

这时，得到的序列就是个位数上呈递增趋势的序列。

按照个位数排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。

在算法的原理中，我们是以一张二维数组的表来存储这些无序的元素。使用二维数组有一个很明显的不足就是二维数组太过稀疏。数组的利用率为 10%。

在寻求优化的路上，我们想到一种可以压缩空间的方法，且时间复杂度并没有偏离得太厉害。那就是设计了两个辅助数组，一个是 count[]，一个是 bucket[]。count 用于记录在某个桶中的最后一个元素的下标，然后再把原数组中的元素计算一下它应该属于哪个“桶”，并修改相应位置的 count 值。直到最大数的最高位也被添加到桶中，或者说，当所有的元素都被被在第 0 个桶中，基数排序就结束了。
优化后的原理图如下

3、程序实现

//桶排序的实现
public int[] buketSort(int[] array, int backetSize) {  
    int[] result = new int[array.length];  
    Node[] bucket = new Node[backetSize];  
    for (int i = 0; i < bucket.length; i++) {  
        bucket[i] = new Node(); // 带头结点  
    }  
    for (int i = 0; i < array.length; i++) {  
        int bucketIndex = hash(array[i]);  
        Node node = new Node(array[i]);  
        Node p = bucket[bucketIndex];  
        if (p.next == null) {// 没有元素  
            p.next = node;  
        } else {// 已经有一个元素  
            while (p.next != null && p.next.data <= node.data) {  
                p = p.next;  
            } // 跳出循环时候 该值小于下一个元  
            node.next = p.next;  
            p.next = node;  
        }  
    }  
    int j = 0;  
    for (int i = 0; i < bucket.length; i++) // 确定次数  
        for (Node p = bucket[i].next; p != null; p = p.next) // n/m  
            result[j++] = p.data;  
    return result;  
}  
  
private int hash(int value) {  
    return value / 10;  
}  

//基数排序实现
public class RadixSort {  
    public int getDigit(int x, int d) {  
        int a[] = {  
                1, 1, 10, 100  
        }; //第一个没有用到，给多少都可以，保险给1， 本实例中的最大数是百位数，所以只要到100就可以了  
        return ((x / a[d]) % 10);  
        //187/10取得的值是18，所以再对10取余就可以获得其十位上的值  
    }  
   
    public void radixSort(int[] list, int begin, int end, int digit) {  
        final int radix = 10; // 基数，定义为常量  
        int i = 0, j = 0;  
        int[] count = new int[radix]; // 存放各个桶的数据统计个数，10个桶  
        int[] bucket = new int[end - begin + 1];//list中的数量  
   
        // 按照从低位到高位的顺序执行排序过程  
        for (int d = 1; d <= digit; d++) {  
   
            // 置空各个桶的数据统计  
            for (i = 0; i < radix; i++) {  
                count[i] = 0;  
            }  
   
            // 统计各个桶将要装入的数据个数  
            for (i = begin; i <= end; i++) {  
                j = getDigit(list[i], d);  
                count[j]++;  
            }//对应的桶计数++，这里只是得到了每个桶会放的个数  
   
            // count[i]表示第i个桶的右边界索引  
            for (i = 1; i < radix; i++) {  
                count[i] = count[i] + count[i - 1];  
            }  
   
            // 将数据依次装入桶中  
            // 这里要从右向左扫描，保证排序稳定性  
            for (i = end; i >= begin; i--) {  
                j = getDigit(list[i], d); // 求出关键码的第k位的数字， 例如：576的第3位是5  
                bucket[count[j] - 1] = list[i]; // 放入对应的桶中，count[j]-1是第j个桶的右边界索引  
                count[j]--; // 对应桶的装入数据索引减一  
            }  
   
            // 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表  
            for (i = begin, j = 0; i <= end; i++, j++) {  
                list[i] = bucket[j];  
            }  
        }  
    }  
   
    public int[] sort(int[] list) {  
        radixSort(list, 0, list.length - 1, 3);  
        return list;  
    }  
   
    // 打印完整序列  
    public void printAll(int[] list) {  
        for (int value : list) {  
            System.out.print(value + "\t");  
        }  
        System.out.println();  
    }  
   
    public static void main(String[] args) {  
        int[] array = {  
                5, 23, 534, 187, 49, 30, 0, 21, 1, 100  
        };  
         
        RadixSort radix = new RadixSort();  
        System.out.print("排序前:\t\t");  
        radix.printAll(array);  
        radix.sort(array);  
        System.out.print("排序后:\t\t");  
        radix.printAll(array);  
     
    }  
}  

4、算法分析

桶排序

时间消耗包括两部分一部分为初始化桶，连接排好序的桶，其时间复杂度为O(n) 一般有m<n (m个桶)

另一部分为对桶中的元素进行排序：每个桶里面有ni个元素，对ni个元素进行插入排序的耗时为O(ni^2)。
于是T(n)=O(n)+∑O(ni^2)，平均意义下认为ni=n/m，于是有T(n)=O(n)+n*O((n/m)^2)=O(n^2/m)+O(n)

当n=m时，T(n)=O(n)+O(n)=O(n)

对于每个桶采用其他的排序算法：m个桶，每个桶中的元素平均假设有n/m个，平均意义下每个桶中的

元素有n/m个，O(m * n/m *lg(n/m) = O(n*lg(n/m))，所以总的时间复杂度为T(n)=O(n+n*lg(n/m))

当m=n时时间复杂度为O(n)，桶数量越多，时间效率越高，然而桶数量越多占用空间也就越大。
如上面后插链表，容易得到桶排序是稳定。

基数排序

基数排序中，r为基数，d为位数。则基数排序的时间复杂度为O(d(n+r))。在基数排序过程中，

对于任何位数上的基数进行“装桶”操作时，都需要n+r个临时空间。

基数排序的效率和初始序列是否有序没有关联，基数排序也是稳定的。