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

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]