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

2022-02-15 00:00:00 排序 基数 计数

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个临时空间。

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

    原文作者:LTELTY
    原文地址: https://blog.csdn.net/qq_25026989/article/details/89367954
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。

相关文章