算法导论8.3-4 O(n)时间内对[0..n^-1]之间的n个数排序

ゞ浴缸里的玫瑰 2022-05-14 03:47 173阅读 0赞

Java实现如下：

package com.application.sample;
    
    import java.util.Arrays;
    import java.util.Random;
    //算法导论第8章练习题8.3-4
    
    public class Algorithm8 {
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int n=10;//n表示有多少个整数
    		int[] array=new int[n];
    		Random r=new Random(47);//生成n个界于0到n^2-1的整数
    		for(int i=0;i<10;i++)
    		{
    			array[i]=r.nextInt(n*n-1);
    		}
    		System.out.println(Arrays.toString(array));
    		radixSort(array,n,2);
    		System.out.println(Arrays.toString(array));
    	}
    	
    	//计数排序
    	public static void countingSort(int[] a,int k,int radix)
    	{
    		int[] c=new int[k];
    		int[] b=new int[a.length];
    		for(int i=0;i<k;i++)
    			c[i]=0;
    		for(int j=0;j<a.length;j++)
    		{
    			c[(a[j]/(int)Math.pow(k, radix-1))%k]++;
    		}
    		for(int i=1;i<k;i++)
    			c[i]+=c[i-1];
    		for(int j=a.length-1;j>=0;j--)
    		{
    			b[c[(a[j]/(int)Math.pow(k, radix-1))%k]-1]=a[j];
    			c[(a[j]/(int)Math.pow(k, radix-1))%k]--;
    		}
    		for(int j=0;j<a.length;j++)
    			a[j]=b[j];
    	}
    	
    	public static void radixSort(int[] a,int k,int maxradix)
    	{
    		for(int i=1;i<=maxradix;i++)
    		{
    			countingSort(a,k,i);
    		}
    	}
    }

运行结果如下所示：

\[74, 89, 31, 65, 22, 11, 1, 59, 27, 13\]  
\[1, 11, 13, 22, 27, 31, 59, 65, 74, 89\]