子类继承父类的题,希望能帮助解决一下(๑• . •๑),第一次学
都没看懂你写的是什么?
n:123 ?
你要实现是什么效果呢?
比如说是给num赋值?
public zi(){
}
public zi(int n){
this.num=n;
}
....
java不支持命名参数吧,你去掉 n: m: 看看
不知道你这个问题是否已经解决, 如果还没有解决的话:1)原理
以LSD实现为例:(从最低位开始进桶的基数排序)
如下图,最低位数相同的都进入相应下标的桶,如第一次,最低位是3的全进了3号桶,最低位是9的全进了9号桶。因为正整数的最低位只能是0~9,所以我们使用数组bask的长度为10,相应的下标为对应的位数的值,全部数组都进桶了完成一次对当前最低位的遍历,然后将桶按照编号合并(跟桶排序的最后一步相同),我们开始进行下一个位的进桶,比如十位是1的全进1号桶,我们这个时候不去理个位了。重复直到遍历完最大的数的最高位。最后得到的数组就排好序了。这就是10进制的LSD基数排序原理
实际例子:
假设原来有一串数值如下所示:
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
1)首先根据个位数的数值
,在走访数值时将它们分配至编号0到9的桶子中:
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
2)接下来将这些桶子中的数值重新串接起来
,成为以下的数列:
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配,这次是根据十位数来分配
:
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
3)接下来将这些桶子中的数值重新串接起来,成为以下的数列:
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为止。
LSD的基数排序适用于位数小的数列,如果位数多的话,使用MSD的效率会比较好。MSD的方式与LSD相反,是由高位数为基底开始进行分配,但在分配之后并不马上合并回一个数组中,而是在每个“桶子”中建立“子桶”,将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
2)代码实现
这里演示全是正整数的排序:
public static void radixSort(int[]array){
int n=1;//表示从个位开始
int max=array[0];//最大的数默认a【0】
int [][]baske=new int[10][array.length];//因为位数只能是0~9,所以我们建立了10个桶,每个桶最多容纳array.length个数
//我们又是用二维数组表示桶,则一样需要一个数组来记录该桶里面存了多少个数
int []len_bask = new int[array.length];
for(int i=0;i<array.length;i++){
len_bask[i]=0;//初始化为0
if(max<array[i])
max = array[i];
}
int k=0;//用来控制array数组赋值下标
//找到该数组里最大是数有几位
while(max!=0){
for (int value : array) {
//取最低位的数值出来
int lsd = (value / n) % 10;
baske[lsd][len_bask[lsd]] = value;//位数相同的进同一个桶,
len_bask[lsd]++; // 同时桶内数的个数加1
}
//现在将桶内的数取出来合并
for(int i=0;i<10;i++){//外围控制桶的下标
if(len_bask[i]!=0)//桶不空
{
for(int j=0;j<len_bask[i];j++){//控制桶内
array[k]=baske[i][j];
k++;
}
len_bask[i]=0;//遍历完该桶内的数,桶内的数就没有了。
}
}
//继续进行下一个位
k=0;
n *=10;
max/=10;//,同时我们让最大值位数降1,假设刚才是max=9,我们就只需要比较一个位数了。
}
}
3)Demo
还是上次的那个数组:
4)评价
标准的基数排序每次从小到大排序十进制下的一个位,并且只关心这一个位,也可以进行设计二进制的基数排序。
不知道细心的伙伴发现没有,上面的算法我们只能进行正整数的排序。那假设有负整数和正整数呢?我们可以加桶的个数,比如0~9的桶装正整数,10到19的桶装负整数
;那如果不是整数呢?感谢IEEE 754的标准
,它制定的浮点标准还带有一个特性:如果不考虑符号位(浮点数是按照类似于原码使用一个bit表示符号位s,s = 1表示负数),那么同符号浮点数的比较可以等价于无符号整数的比较,方法就是先做一次基数排序,然后再调整正负数部分顺序即可。所以现在已经可以实现浮点数的基数排序了!!!
最佳情况:T(n) = O(n * k) 最差情况:T(n) = O(n * k) 平均情况:T(n) = O(n * k)
基数排序有两种方法:
5)基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异: