基数排序（桶排序）思路整理

た入场券 2023-02-18 03:16 25阅读 0赞

首先了解一下什么是基数排序：  
基数排序是桶排序的扩展，不了解桶排序也没有关系。它是通过待排序列中每个值的各个位，将每个值按照一定规则放置“桶”中，达到排序的效果。（刚刚接触这段介绍肯定是不太懂的，定义的作用就是可是帮助我们学完基数排序回过头思考，所以不理解没关系）  
基数排序的基本思想：  
将所有待排列的数统一为相等长度的数位，数位短的在前面补0。例如：统一35，246这两个数。按照最长位统一，数位短的补0也就是035，结果就和246数位一样长了。然后再将每个数依次从最低位开始比较，比较的过程中按照一定规则放入“桶中”，然后再依次取出，取出的值就是有序的了。（还是那句话不理解没关系，等到回过头来看就慢慢理解了）  
接下来给出基数排序的示意图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 2]  
最后给出完整代码：

public static void radixSort02(int[] arr){
        
            //定义一个二维数组
            int[][] bucket = new int[10][arr.length];
            //定义一个一维数组，用来存放每个桶内当前元素的下标，也可以推断出当前桶内存放的元素个数
            int[] bucketElementCounts = new int[10];
            //从分析图可以看到，桶内的存取操作次数取决于待排序列最大值的位数
            //所以需要找出待排序序列中最大的值，求出它的位数
            int max = arr[0];
            for (int i = 1;i < arr.length;i++){
        
                if (arr[i] > max){
        
                    max = arr[i];
                }
            }
            int counts = (max +"").length();//转化成字符串直接调用方法
    
            //开始轮流存放
            //n来控制取出的位数
            for (int i = 0,n = 1;i < counts;i++,n *= 10){
        
                for (int j = 0;j < arr.length;j++){
        
                //第一次arr[j] / 1 % 10取出的是个位上的数
                //第二次arr[j] / 10 % 10取出的是十位上的数，之后以此类推
                    int digitOfElement = arr[j] / n % 10;
                    //存放到对应的桶中
                    bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                    bucketElementCounts[digitOfElement] ++;
                }
                int index = 0;//表示原数组的下标
                //依次从桶中取出，放入到原数组
                for (int k = 0;k < bucketElementCounts.length;k++){
        
                    if (bucketElementCounts[k] != 0){
        //等于0代表，下标k对于的桶中没有存放元素则不需要取
                        for (int l = 0;l < bucketElementCounts[k];l++){
        
                            arr[index] = bucket[k][l];
                            index ++;
                        }
                    }
                    bucketElementCounts[k] = 0;//清空，再进行下一轮存取
                }
            }
        }

总结：基数排序的速度是非常快的，甚至比快速排序还要快。但是它也有缺点，根据代码可以分析到。基数排序，在把数据放入桶的过程中，由于事先不知道每个桶内到底要容纳多少个数据，也就无法准确确定大小。所以为了防止数组下标越界，就需要为每个桶开辟能够容纳整个数组的空间。实际上许多空间都是浪费了，这就是典型的利用空间换取时间上的效率。所以如果你的内存不是足够大，是不能排列大量的数据。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/2020061517594359.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200615180007250.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200615180021462.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center