排序(七) 基数排序的一些思路

╰半橙微兮° 2022-12-11 13:33 122阅读 0赞

基数排序也叫桶排序 他是根据位数来排序的

循环的次数只跟位数有关 所以在时间效率上会很高

相反的 空间的开辟会更大些 不过这好解决 时间才是第一位的

不足之处的话 不好处理小数 负数

![c8b96c93d3fa6137272b4734f3bddbee.png][]

说下思路

将所有元素取个位数 依次放入 0~9的桶中

之后依次从桶中取出数据 放回原数组

再按十位数取 依次放入0~9的桶中

反复多次

最后的数组就有序了

非常适合大数据量的排序

--------------------

所以我们首先要确定数组中最大元素的长度 或者说是几位数 来确定大的循环

int max = arr[0];
            for (int i = 1; i < arr.length; i++) { 
                if (arr[i] > max) { 
                    max = arr[i];
                }
            }
            //找到最大位数
            int len = (max + "").length();

然后定义一个二维数组 new int\[10\]\[arr.length\] 相当于10个一维数组

当然也可以定义10个一维数组、、、、、、

int[][] barrels = new int[10][arr.length];

然后根据个位数 来确定放在哪个桶里面 如4 放在4桶 0放在0桶酱紫

但是我们放元素过程中 还需要一个指针来知道每个桶到底放了多少元素 这样方便之后取数据

所以还需要一个数组来确定每个桶的元素个数

//存放各桶元素的指针数组
    int[] point = new int[10];

当每次放数据时 数组对应的坐标也要++ 如放入了0桶 point\[0\]+1

//外层循环的次数由位数决定
    for (int i = 0; i < len; i++) { 
    
    			//遍历待排序的数组
                for (int j = 0; j < arr.length; j++) { 
                	//digit第一次循环表示个位数 
                    int digit = (int) (arr[j] / (Math.pow(10, i)) % 10);
                    //每次放入时 指针数组的元素要++
                    barrels[digit][point[digit]++] = arr[j];
                }
         
    
    }

最后要将排序完毕后的桶的数据进行遍历

这也是个双层循环 外层循环的大小就是桶的个数 10

内层循环要做一个判断 当某个桶里没有数据 则不需要对这个桶进行操作

之后将元素数据一次放入

第一轮遍历就完毕了

int index = 0;
                //取数据的时候 要知道哪个桶不为空才取
                for (int k = 0; k < barrels.length; k++) { 
                    //当这个指针的某个元素为0 则不添加
                    if (point[k] != 0) { 
                        //barrels[k].length 表示某个桶里的元素个数
                        for (int l = 0; l < point[k]; l++) { 
                        	//依次放入数组中
                            arr[index++] = barrels[k][l];
                        }
                    }
                    
                }

但要注意 为了第二次遍历 桶中的数据要清空 否则第二次的排序就乱了

//在k循环内清空桶
      point[k] = 0;

--------------------

**贴上完整代码**

public static void sort(int[] arr) { 
            int max = arr[0];
            for (int i = 1; i < arr.length; i++) { 
                if (arr[i] > max) { 
                    max = arr[i];
                }
            }
            //找到最大位数
            int len = (max + "").length();
    		//存放各桶的二维数组
            int[][] barrels = new int[10][arr.length];
            //存放各桶元素
            int[] point = new int[10];
            //循环最大位数的次数
            for (int i = 0; i < len; i++) { 
                for (int j = 0; j < arr.length; j++) { 
                    //digit第一次循环表示个位数 
                    int digit = (int) (arr[j] / (Math.pow(10, i)) % 10);
                    //每次放入时 指针数组的元素要++
                    barrels[digit][point[digit]++] = arr[j];
                }
                int index = 0;
                //取数据的时候 要知道哪个桶不为空才取
                for (int k = 0; k < barrels.length; k++) { 
                    //当这个指针的某个元素为0 则不添加
                    if (point[k] != 0) { 
                        //barrels[k].length 表示某个桶里的元素个数
                        for (int l = 0; l < point[k]; l++) { 
                        	//依次放入数组中
                            arr[index++] = barrels[k][l];
                        }
                    }
                    //清空桶
                    point[k] = 0;
                }
    
            }
    
        }

ps：**你现在的每一份努力 都有未来的影子**

[c8b96c93d3fa6137272b4734f3bddbee.png]: /images/20221123/a42a28fcf40b48a5816034078dc66cb2.png