java实现基数排序算法

Myth丶恋晨 2022-05-13 05:42 143阅读 0赞

前面我们详细讲解了[基数排序算法][Link 1]，现在我们使用代码来实现，直接上代码，java代码如下

我们先要做的就是求数组中最大值，然后算出最大值得位数，这样才能判别需要循环几次

package ttt;
    
    import java.util.Arrays;
    
    public class RadixSort {
    	public static int getMax(int[] theArray) {
    		//获取数组中最大的数
        	int i,max = 0;
        	max = theArray[0];
        	for(i=0; i<theArray.length; i++) {
        		if(theArray[i]>max){
        			max = theArray[i];
        		}
        	}
        	//获取最大的数的位数
        	int count = 0;
    		while(max > 0){
                max = max / 10;
                count++;
    		}
    		System.out.println("最大位数是："+count);
    		
    		return count;
    	}
        public static int[] radixSort(int[] theArray,int radix) {
        	int count = getMax(theArray);
        	
    		//给桶中对应位置放数字
    		for(int j=0; j<count; j++) {
    			//取余的底数
    			int theData = (int) Math.pow(10,j);//10的j次方
    			
    			//================================
    			System.out.print("初始数组 ");
    	        for(int i = 0; i < theArray.length; i++) {
    	            System.out.print(theArray[i] + " ");
    	        }
    	        
    			//=================================
    	        //建立一个空桶
    			int bucket[][] = new int[10][10];
    			for(int k=0; k<theArray.length; k++) {
    //				System.out.println("计算值是"+theArray[k]+"/"+theData);
    				int theResidue = (theArray[k]/theData) %10 ;//取余
    //				System.out.println("余数是"+theResidue);
    				int[]childArray =new int[10];//= bucket[theResidue];//获取子数组
    				for(int m=0; m<10; m++) {
    					if (bucket[theResidue][m]==0) {
    						childArray[m] = theArray[k];
    						bucket[theResidue][m] = childArray[m];
    						break;
    					}else {
    						continue;
    					}
    				}
    				
    			}
    			Arrays.fill(theArray, 0);
    			int x=0;
    			System.out.println("");
    			for (int p=0; p<bucket.length; p++) {
    				for(int q=0; q<bucket[p].length; q++) {
    					if (bucket[p][q]!=0) {
    //						System.out.println(p+","+q+"桶中的元素=======："+bucket[p][q]);
    						theArray[x] = bucket[p][q];
    						x++;
    					}else {
    						break;
    					}
    				}
    			}
    		}
        	return theArray;
        }
        public static void main(String[] args) {
        	int []the_array = {10,1,18,30,23,12,7,5,18,233,144};
    //    	int []the_array = {10,18,1,11,66,23,8};
            System.out.print("之前的排序：");
            for(int i = 0; i < the_array.length; i++) {
                System.out.print(the_array[i] + " ");
            }
            
            int []result_array = radixSort(the_array,10);
            
            System.out.print("基数排序：");
            for(int i = 0; i < result_array.length; i++) {
                System.out.print(result_array[i] + " ");
            }
        }
    }

运行结果如下

之前的排序：10 1 18 30 23 12 7 5 18 233 144 最大位数是：3
    初始数组 10 1 18 30 23 12 7 5 18 233 144 
    初始数组 10 30 1 12 23 233 144 5 7 18 18 
    初始数组 1 5 7 10 12 18 18 23 30 233 144 
    基数排序：1 5 7 10 12 18 18 23 30 144 233

符合预期

[Link 1]: https://blog.csdn.net/stronglyh/article/details/82598186