上节我们学习了归并排序,我们知道了归并采用的是分治的策略,在分的过程中采用的是递归来处理,而治的过程才是我们算法的核心,更多详解看算法入门教程-归并排序,这节我们学习另外一种算法:基数排序,首先我们简单的介绍下什么是基数排序?
基数排序
官方介绍:基数排序称为"分配式排序",有称"桶子法"通过键值的各个位的值,将要排序的元素分配到某些"桶"中来达到排序的作用.
基数排序属于稳定性排序,同样也是桶排序的扩展
基数排序的思想:将所有待比较数值统一为同样的数位长度,数位较短的前面补零,然后从最低位开始,依次进行一次排序,这样从最低位一直到最高位排序完成后,数列就会变成一个有序的数列.
接下来我们通过图解的方式来理解上述所描述的过程:
假设我待排序的数列为{53,3,542,748,14,214},我们来看具体过程:
- 第一轮的图解过程:
第一轮排序过程.png
-
第二轮的图解过程
第二轮排序过程.png
-
第三轮图解过程
第三轮排序结果图.png
通过三轮的排序我们最终完成了排序过程,图中有具体的详细,这里我简单的补充说明下为啥什么这样存放
- 首先图中0-9代表10个一位数组(也就是我们的桶)
- 其中我们元素取到的个位和十位以及百位等值,对应的就是我们下标为0-9的一维数组
这样大家可能明白许多了,我们接着通过代码的方式来实现
代码实现过程
假设我待排序的列表为:{53,3,542,748,14,214}
- 公用代码
//基数排序方法
public static void radixSort(int[] arr){
//首先我们来定义一个二维数组来表示10个桶,其中每个桶就是一个一维数组
//为了防止放入元素的时候溢出,这里将每个桶的大小定为arr.length
//基数排序是经典的空间换取时间的算法
int [][] bucket = new int[10][arr.length];
//为了统计每个桶中实际的元素的个数,这里定义一个一维数组来记录每次放入元素的个数
//如:bucketEleCounts[0]表示记录的是bucket[0]桶的放入元素的个数
int [] bucketEleCounts = new int[10];
- 第一轮排序代码实现
//第一轮:针对每一个元素的个位进行排序处理
for (int j = 0; j <arr.length ; j++) {
//取出每个元素的个位数
int digitOfElement = arr[j] %10;
//放入到对应的桶中
//说明:
// bucket[digitOfElement]表示第几个桶;因为我们计算出来的个位数也代表它是第几个桶
//[bucketEleCounts[digitOfElement]]表示对应桶的元素
bucket[digitOfElement][bucketEleCounts[digitOfElement]] = arr[j];
// ++ 操作表示如果后面计算得到个位数相同的话,我们需要将它放入已有元素的后面
bucketEleCounts[digitOfElement] ++;
}
//2.按照上述桶的顺序,我们将一维数组的下标依次取出该元素放入到原数组(arr)
//首先定义一个临时索引index
int index = 0;
//遍历操作
for (int k = 0; k <bucket.length ; k++) {
//如果我们的桶中有数据,才放入到原数组中
if (bucketEleCounts[k] !=0){
//循环该桶,也就是第K个桶
for (int l = 0; l <bucketEleCounts[k] ; l++) {
//将第k个桶的第l个元素放入到原数组中
arr[index] = bucket[k][l];
index ++;
}
}
//注意:
//第一轮处理完过后,我们需要将每一个(bucketEleCounts[k]清零,为了后面步骤的需要
bucketEleCounts[k] = 0;
}
System.out.println("第一轮对个位的排序处理结果");
System.out.println(Arrays.toString(arr));
- 来看测试代码
/**
* 算法学习-基数排序
*/
public class RadixSort {
public static void main(String[] args) {
int [] arr = {53,3,542,748,14,214};
radixSort(arr);
-
测试结果如图:
第一轮测试结果.png
-
第二轮排序代码实现
//第二轮:针对每一个元素的个位进行排序处理
for (int j = 0; j <arr.length ; j++) {
//取出每个元素的十位数
int digitOfElement = arr[j] /10 %10;
//放入到对应的桶中
//说明:
// bucket[digitOfElement]表示第几个桶;因为我们计算出来的个位数也代表它是第几个桶
//[bucketEleCounts[digitOfElement]]表示对应桶的元素
bucket[digitOfElement][bucketEleCounts[digitOfElement]] = arr[j];
// ++ 操作表示如果后面计算得到个位数相同的话,我们需要将它放入已有元素的后面
bucketEleCounts[digitOfElement] ++;
}
//2.按照上述桶的顺序,我们将一维数组的下标依次取出该元素放入到原数组(arr)
//首先定义一个临时索引index
index = 0;
//遍历操作
for (int k = 0; k <bucket.length ; k++) {
//如果我们的桶中有数据,才放入到原数组中
if (bucketEleCounts[k] !=0){
//循环该桶,也就是第K个桶
for (int l = 0; l <bucketEleCounts[k] ; l++) {
//将第k个桶的第l个元素放入到原数组中
arr[index] = bucket[k][l];
index ++;
}
}
//注意:
//第二轮处理完过后,我们需要将每一个(bucketEleCounts[k]清零,为了后面步骤的需要
bucketEleCounts[k] = 0;
}
System.out.println("第二轮对个位的排序处理结果");
System.out.println(Arrays.toString(arr));
-
直接看测试结果如图所示:
第二轮测试结果图.png
-
第三轮排序代码实现
//第三轮:针对每一个元素的个位进行排序处理
for (int j = 0; j <arr.length ; j++) {
//取出每个元素的十位数
int digitOfElement = arr[j] /100 %10;
//放入到对应的桶中
//说明:
// bucket[digitOfElement]表示第几个桶;因为我们计算出来的个位数也代表它是第几个桶
//[bucketEleCounts[digitOfElement]]表示对应桶的元素
bucket[digitOfElement][bucketEleCounts[digitOfElement]] = arr[j];
// ++ 操作表示如果后面计算得到个位数相同的话,我们需要将它放入已有元素的后面
bucketEleCounts[digitOfElement] ++;
}
//2.按照上述桶的顺序,我们将一维数组的下标依次取出该元素放入到原数组(arr)
//首先定义一个临时索引index
index = 0;
//遍历操作
for (int k = 0; k <bucket.length ; k++) {
//如果我们的桶中有数据,才放入到原数组中
if (bucketEleCounts[k] !=0){
//循环该桶,也就是第K个桶
for (int l = 0; l <bucketEleCounts[k] ; l++) {
//将第k个桶的第l个元素放入到原数组中
arr[index] = bucket[k][l];
index ++;
}
}
//注意:
//第二轮处理完过后,我们需要将每一个(bucketEleCounts[k]清零,为了后面步骤的需要
bucketEleCounts[k] = 0;
}
System.out.println("第三轮对个位的排序处理结果");
System.out.println(Arrays.toString(arr));
}
-
测试结果如下图所示:
第三轮测试结果图.png
通过三轮的处理我们最终完成了排序,我们来整合下代码
//基数排序方法
public static void radixSort(int[] arr){
//得到数组中最大数的位数
//定义一个临时变量来存储我们的最大数先假设定义的就是最大的
int max = arr[0]; //假设第一个就是最大的
for (int i = 1; i < arr.length ; i++) {
if (arr[i] > max){
max = arr[i];
}
}
//得到最大数的位数是多少
int maxLength = (max +"").length();
//首先我们来定义一个二维数组来表示10个桶,其中每个桶就是一个一维数组
//为了防止放入元素的时候溢出,这里将每个桶的大小定为arr.length
//基数排序是经典的空间换取时间的算法
int [][] bucket = new int[10][arr.length];
//为了统计每个桶中实际的元素的个数,这里定义一个一维数组来记录每次放入元素的个数
//如:bucketEleCounts[0]表示记录的是bucket[0]桶的放入元素的个数
int [] bucketEleCounts = 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]表示第几个桶;因为我们计算出来的个位数也代表它是第几个桶
//[bucketEleCounts[digitOfElement]]表示对应桶的元素
bucket[digitOfElement][bucketEleCounts[digitOfElement]] = arr[j];
// ++ 操作表示如果后面计算得到个位数相同的话,我们需要将它放入已有元素的后面
bucketEleCounts[digitOfElement] ++;
}
//2.按照上述桶的顺序,我们将一维数组的下标依次取出该元素放入到原数组(arr)
//首先定义一个临时索引index
int index = 0;
//遍历操作
for (int k = 0; k <bucket.length ; k++) {
//如果我们的桶中有数据,才放入到原数组中
if (bucketEleCounts[k] !=0){
//循环该桶,也就是第K个桶
for (int l = 0; l <bucketEleCounts[k] ; l++) {
//将第k个桶的第l个元素放入到原数组中
arr[index] = bucket[k][l];
index ++;
}
}
//注意:
//第i+1轮处理完过后,我们需要将每一个(bucketEleCounts[k]清零,为了后面步骤的需要
bucketEleCounts[k] = 0;
}
System.out.println("第"+(i+1)+"轮对个位的排序处理结果");
System.out.println(Arrays.toString(arr));
}
- 测试一把结果如图所示:
整合后的测试结果图.png
最后一点我们来测试下基数排序的执行时间效率:
int [] arr = new int[10000000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random() * 10000000); //随机生成[0,100000)的数
}
Date date1 = new Date();
SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String format = dateFormat.format(date1);
System.out.println("排序前的时间为:"+format);
//进行排序
int [] temp = new int[arr.length];
radixSort(arr);
Date date2 = new Date();
SimpleDateFormat dateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String format2 = dateFormat.format(date2);
System.out.println("排序后的时间为:"+format2);
- 来看测试结果如图所示:
时间测试.png
可以看出10W条数据排序是没有任何压力的,那么关于基数排序的学习就到这了...
网友评论