基数排序法与元素个数有关吗为什么不一样（基数排序法）

基数排序

基数排序(桶排序)介绍:

基数排序（radix sort）属于“分配式排序  
  
  
  
  
  
 ”（distribution sort）  
  
  
  
  
  
 ，又称“桶子法 
  
  
  
  
  
 ”（bucket sort）或 bin sort 
  
  
  
  
  
 ，顾 名思义


 


 


 


 


 


 
，它是通过键值的各个位的值 
 
 
 
 
 
，将要排序的元素分配至某些“桶


 


 


 


 


 


 
”中  
   
   
   
   
   
  ，达到排序的作用 基数排序法是属于稳定性的排序

 

 

 

 

 

 
，基数排序法的是效率高的稳定性排序法 基数排序(Radix Sort)是桶排序的扩展 基数排序是 1887 年赫尔曼·何乐礼发明的            。它是这样实现的：将整数按位数切割成不同的数字
 

 

 

 

 

 
，然后按每个 位数分别比较

基数排序基本思想

将所有待比较数值统一为同样的数位长度             ，数位较短的数前面补零 
 
  
 
  
 
  
 
  
 
  
 
  。然后
 

 
 

 
 

 
 

 
 

 
 

 
，从最低位开始











，依次进行一次排序











。 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
  
  
  
  
  
  
。

基数排序图文说明

将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序

基数排序代码实现

要求：将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序

分析看上面的图片

package DataStructures.com.atguigu.sort; import java.util.Arrays; public class RadixSort { public static void main(String[] args) { int arr[] = {53, 3, 542, 748, 14, 214}; radixSort(arr); } //基数排序方法 public static void radixSort(int[] arr){ //定义一个二维数组                   ，表示10个桶, 每个桶就是一个一维数组 //说明 //1. 二维数组包含10个一维数组 //2. 为了防止在放入数的时候
 
 
 
 
 
 
 
 
 
 
 
 
，数据溢出

















，则每个一维数组(桶)             ，大小定为arr.length //3. 名明确
 
  
 
  
 
  
 
  
 
  
 
  
，基数排序是使用空间换时间的经典算法 int[][] bucket = new int[10][arr.length]; //为了记录每个桶中











，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数 //可以这里理解 //比如：bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数 int[] bucketElementCounts = new int[10]; //第一轮(针对每个元素的个位进行排序处理) for(int j = 0;j < arr.length;j++){ //取出每个元素的个位的值 int digitOfElement = arr[j] / 1 % 10; //放入到对应的桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } //按照这个桶的顺序（一维数组的下标依次取出数据  
  
  
  
  
  
 ，放入原来数组） int index = 0; //遍历每一桶 
  
  
  
  
  
 ，并将桶中的数据


 


 


 


 


 


 
，放入原来数组 for(int k = 0;k <bucketElementCounts.length;k ++){ //如果桶中有数据 
 
 
 
 
 
，我们才放入到原数组 if(bucketElementCounts[k] != 0){ //循环该桶即第K个桶（即第k个一维数组）,放入 for(int l = 0;l < bucketElementCounts[k];l++){ //取出元素放入到arr arr[index++] = bucket[k][l]; } } //第l轮处理后  
   
   
   
   
   
  ，需要将每个bucketElementCounts[k] = 0!!! bucketElementCounts[k] = 0; } System.out.println("第1轮

 

 

 

 

 

 
，对个位的排序处理arr=" + Arrays.toString(arr)); //========================================== //第2轮(针对每个元素的十位进行排序处理) for (int j = 0; j < arr.length; j++) { // 取出每个元素的十位的值 int digitOfElement = arr[j] / 10 % 10; //748 / 10 => 74 % 10 => 4 // 放入到对应的桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } // 按照这个桶的顺序(一维数组的下标依次取出数据
 

 

 

 

 

 
，放入原来数组) index = 0; // 遍历每一桶             ，并将桶中是数据
 

 
 

 
 

 
 

 
 

 
 

 
，放入到原数组 for (int k = 0; k < bucketElementCounts.length; k++) { // 如果桶中











，有数据                   ，我们才放入到原数组 if (bucketElementCounts[k] != 0) { // 循环该桶即第k个桶(即第k个一维数组), 放入 for (int l = 0; l < bucketElementCounts[k]; l++) { // 取出元素放入到arr arr[index++] = bucket[k][l]; } } //第2轮处理后
 
 
 
 
 
 
 
 
 
 
 
 
，需要将每个 bucketElementCounts[k] = 0 ！！！！ bucketElementCounts[k] = 0; } System.out.println("第2轮

















，对十位的排序处理 arr =" + Arrays.toString(arr)); //第3轮(针对每个元素的百位进行排序处理) for (int j = 0; j < arr.length; j++) { // 取出每个元素的百位的值 int digitOfElement = arr[j] / 100 % 10; // 748 / 100 => 7 % 10 = 7 // 放入到对应的桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } // 按照这个桶的顺序(一维数组的下标依次取出数据             ，放入原来数组) index = 0; // 遍历每一桶
 
  
 
  
 
  
 
  
 
  
 
  
，并将桶中是数据











，放入到原数组 for (int k = 0; k < bucketElementCounts.length; k++) { // 如果桶中  
  
  
  
  
  
 ，有数据 
  
  
  
  
  
 ，我们才放入到原数组 if (bucketElementCounts[k] != 0) { // 循环该桶即第k个桶(即第k个一维数组), 放入 for (int l = 0; l < bucketElementCounts[k]; l++) { // 取出元素放入到arr arr[index++] = bucket[k][l]; } } //第3轮处理后


 


 


 


 


 


 
，需要将每个 bucketElementCounts[k] = 0 ！！！！ bucketElementCounts[k] = 0; } System.out.println("第3轮 
 
 
 
 
 
，对百位的排序处理 arr =" + Arrays.toString(arr)); } }

运行结果：

推广到一般情况：

代码如下：

package DataStructures.com.atguigu.sort; import java.util.Arrays; public class RadixSort { public static void main(String[] args) { int arr[] = {53, 3, 542, 748, 14, 214}; radixSort(arr); } //基数排序方法 public static void radixSort(int[] arr){ //根据前面的推导过程  
   
   
   
   
   
  ，我们可以得到最终的基数排序代码 //1. 得到数组中最大的数的位数 int max = arr[0];//假设第一数就是最大数 for(int i = 1;i < arr.length;i++){ if(arr[i] > max){ max = arr[i]; } } //得到最大数是几位数 int maxLength = (max + "").length(); //定义一个二维数组

 

 

 

 

 

 
，表示10个桶, 每个桶就是一个一维数组 //说明 //1. 二维数组包含10个一维数组 //2. 为了防止在放入数的时候
 

 

 

 

 

 
，数据溢出             ，则每个一维数组(桶)
 

 
 

 
 

 
 

 
 

 
 

 
，大小定为arr.length //3. 名明确











，基数排序是使用空间换时间的经典算法 int[][] bucket = new int[10][arr.length]; //为了记录每个桶中                   ，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数 //可以这里理解 //比如：bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数 int[] bucketElementCounts = new int[10]; //这里我们使用循环将代码处理 for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) { //(针对每个元素的对应位进行排序处理)
 
 
 
 
 
 
 
 
 
 
 
 
， 第一次是个位

















，第二次是十位             ，第三次是百位.. for(int j = 0; j < arr.length; j++) { //取出每个元素的对应位的值 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) { //循环该桶即第k个桶(即第k个一维数组), 放入 for(int l = 0; l < bucketElementCounts[k]; l++) { //取出元素放入到arr arr[index++] = bucket[k][l]; } } //第i+1轮处理后 
 
 
 
 
 
，需要将每个 bucketElementCounts[k] = 0 ！！！！ bucketElementCounts[k] = 0; } System.out.println("第"+(i+1)+"轮  
   
   
   
   
   
  ，排序处理 arr =" + Arrays.toString(arr)); } } }

运行结果：

结果跟之前一样

基数排序的说明

1.基数排序是对传统桶排序的扩展

 

 

 

 

 

 
，速度很快.

2.基数排序是经典的空间换时间的方式
 

 

 

 

 

 
，占用内存很大, 当对海量数据排序时             ，容易造成 OutOfMemoryError  
  
  
  
  
  
 。

基数排序时稳定的 


 


 


 


 


 


 。[注:假定在待排序的记录序列中
 

 
 

 
 

 
 

 
 

 
 

 
，存在多个具有相同的关键字的记录











，若经过排序                   ，这些 记录的相对次序保持不变
 
 
 
 
 
 
 
 
 
 
 
 
，即在原序列中

















，r[i]=r[j]             ，且 r[i]在 r[j]之前
 
  
 
  
 
  
 
  
 
  
 
  
，而在排序后的序列中











，r[i]仍在 r[j]之前  
  
  
  
  
  
 ， 则称这种排序算法是稳定的；否则称为不稳定的]

这篇博客是我在B站看韩顺平老师数据结构和算法的课时的笔记 
  
  
  
  
  
 ，记录一下


 


 


 


 


 


 
，防止忘记 
 
 
 
 
 
，也希望能帮助各位朋友
 
 
 
 
 
 
。