java语言描述基数排序(桶排序)
程序员文章站
2024-03-02 16:26:28
...
java语言描述基数排序(桶排序)
简单介绍桶排序(基数排序)
具体的文字说明不做介绍,需要可以百度,我只举个栗子。如下每一个蓝色方框代表每一位的“桶”,对个位进行排序,按要排序的数组元素的顺序进行添加排序,先看个位,如下图所示,从0到9,依次添加。
注:本文展示的基数排序不能对负数进行排序,若想用基数排序对负数排序需要添加一些方法,请参考他人的文章。
个位排序完成后进行十位的排序,在上图中各个“桶”的基础上进行排序操作。
百位排序操作类似,如果最高位为百位的话经过3轮排序就会得到相应的结果。
代码如下
//基数排序(桶排序)稳定得很典型的空间换时间的算法,但是海量数据时会存在内存不足的情况
//对负数进行排序时需要另外的步骤
public class RadixSort {
public static void main(String[] args) {
int[] arr={542,59,9,14,214,748};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
//一个得到数组元素最大位数的方法。
public static int getMaxFigure(int[] arr){
int max=arr[0];
for (int i=1;i<arr.length;i++){
if (arr[i]>max){
max=arr[i];
}
}
return (max+"").length();
}
public static void radixSort(int[] arr){
//初始化桶
int[][] bucket=new int[10][arr.length];
//初始化一个数组记录每次添加到每个桶的那个位置了
//数组的index对应桶号,数组的值对应存储了几个
int[] buckElementCount=new int[10];
//数组元素中的最大位数
int maxFigure=getMaxFigure(arr);
int index=0;
for (int k=0,n=1;k<maxFigure;k++,n*=10){
//将元素按对应位置放进桶里(个位,十位,百位)
for (int i=0;i<arr.length;i++){
//取出元素对应位置上的值
int digitOfElement=arr[i]/n%10;
bucket[digitOfElement][buckElementCount[digitOfElement]]=arr[i];
buckElementCount[digitOfElement]++;
}
index=0;
//十位先把第一轮过后的桶里的元素依次拷到arr里
for (int i=0;i<10;i++){
for (int j=0;j<buckElementCount[i];j++){
if(bucket[i][j]!=0){
arr[index++]=bucket[i][j];
bucket[i][j]=0;
}
}
buckElementCount[i]=0;
}
}
}
}
运行结果如下。
参考:尚硅谷韩顺平老师的数据结构与算法java语言描述(b站尚硅谷官方视频)
上一篇: Hibernate关联映射总结