首页 > 代码库 > 数据结构之排序算法Java实现（4）—— 基数排序法
数据结构之排序算法Java实现（4）—— 基数排序法
基数排序算法是计数排序的延伸，计数排序会造成很大的空间浪费，但基数排序法是对位数进行排序，适合于位数之间相差较大的情况，废话不多说，直接上代码：
升序排序法：
/**
* 基数排序法
* 升序排列
* @param data
*/
public void sortByAsc(int[] data) {
/** step1:确定排序的趟数*/
int max=data[0];
for(int i=1;i<data.length;i++){
if(data[i]>max){
max=data[i];
}
}
/** step2:判断位数*/
int digit = 0;
while(max > 0){
max/=10;
digit++;
}
/**初始化一个二维数组，相当于二维数组，可以把重复的存进去*/
List<ArrayList<Integer>> temp = new ArrayList<>();
for(int i = 0;i < 10;i++){
temp.add(new ArrayList<Integer>());
}
/**开始合并收集*/
for(int i = 0; i < digit; i++){
/** 对每一位进行排序 */
for(int j = 0; j < data.length; j++){
/**求每一个数的第i位的数，然后存到相对应的数组中*/
int digitInx = data[j]%(int)Math.pow(10, i + 1)/(int)Math.pow(10, i);
ArrayList<Integer> tempInside = temp.get(digitInx);
tempInside.add(data[j]);
temp.set(digitInx,tempInside );
}
/**收集数组元素*/
int count = 0;
for(int k = 0;k < 10;k++){
for(;temp.get(k).size()>0;count++){
ArrayList<Integer> temp2 = temp.get(k);
data[count] = temp2.get(0);
temp2.remove(0);
}
}
}
}
降序排序法：
/**
* 基数排序法
* 降序排列
* @param data
*/
public void sortByDesc(int[] data) {
/** step1:确定排序的趟数*/
int max=data[0];
for(int i=1;i<data.length;i++){
if(data[i]>max){
max=data[i];
}
}
/** step2:判断位数*/
int digit = 0;
while(max > 0){
max/=10;
digit++;
}
/**初始化一个二维数组，相当于二维数组，可以把重复的存进去*/
List<ArrayList<Integer>> temp = new ArrayList<>();
for(int i = 0;i < 10;i++){
temp.add(new ArrayList<Integer>());
}
/**开始合并收集*/
for(int i = 0; i < digit; i++){
/** 对每一位进行排序 */
for(int j = 0; j < data.length; j++){
/**求每一个数的第i位的数，然后存到相对应的数组中*/
int digitInx = data[j]%(int)Math.pow(10, i + 1)/(int)Math.pow(10, i);
ArrayList<Integer> tempInside = temp.get(digitInx);
tempInside.add(data[j]);
temp.set(digitInx,tempInside );
}
int count = data.length - 1;
for(int k = 0;k < 10;k++){
for(;temp.get(k).size()>0;count--){
ArrayList<Integer> temp2 = temp.get(k);
data[count] = temp2.get(0);
temp2.remove(0);
}
}
}
}
数据结构之排序算法Java实现（4）—— 基数排序法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。