设待排序的n个数都是介于0~k之间的整数，当k=O(n)时，我们常采用计数排序，其时间复杂度为O(n)。
计数排序的思想是，对于每一个元素x，统计出小于等于x的元素个数，从而直接确定它在排序后的位置。
样例输入：
10 1 2 11 33 11 23 6 9 2 6
样例输出：
1 2 2 6 6 9 11 11 23 33
import java.util.Scanner; public class Main { public static int[] arr; public static void counting_sort(int[] count,int[] temp){ for(int i=0;i<arr.length;i++) count[arr[i]]++; //count[x]首先统计出数组arr中，等于x的元素个数 for(int i=1;i<count.length;i++) count[i]+=count[i-1]; //然后，count[x]统计出数组arr中，小于等于x的元素个数 for(int i=arr.length-1;i>=0;i--){ //将元素放到正确位置即可，必须从后往前才是稳定排序 int index=count[arr[i]]--; temp[index-1]=arr[i]; } } public static void main(String[] args){ Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ int n=scanner.nextInt(); arr=new int[n]; int k=0; for(int i=0;i<n;i++){ arr[i]=scanner.nextInt(); if(arr[i]>k) k=arr[i]; } int[] count=new int[k+1]; //count[x]存放数组arr中，小于等于x的元素个数 int[] temp=new int[n]; //存放排序结果 counting_sort(count, temp); StringBuffer str=new StringBuffer(); for(int i:temp) str.append(i+" "); System.out.println(str.substring(0,str.length()-1)); } scanner.close(); } }基数排序是从最低有效位依次往前进行排序，其中最关键的一点是按位排序要稳定，常用计数排序作为基数排序的子排序，因为每位都是介于0~9之间。
样例输入：
7 329 457 657 839 436 720 355
样例输出：
329 355 436 457 657 720 839
以下程序并不完善，要求所有输入的数据位数相同。
import java.util.Arrays; import java.util.Scanner; public class Main { public static int[] arr; public static int getVal(int num,int i){ //得到某个数字倒数第i位的值 String s=num+""; int len=s.length(); return Integer.parseInt(s.charAt(len-1-i)+""); } public static void counting_sort(int cursor,int[] count,int[] temp){ for(int i=0;i<arr.length;i++) count[getVal(arr[i], cursor)]++; //count[x]首先统计出数组arr中，等于x的元素个数 for(int i=1;i<count.length;i++) count[i]+=count[i-1]; //然后，count[x]统计出数组arr中，小于等于x的元素个数 for(int i=arr.length-1;i>=0;i--){ //将元素放到正确位置即可，必须从后往前才是稳定排序 int index=count[getVal(arr[i], cursor)]--; temp[index-1]=arr[i]; } for(int i=0;i<arr.length;i++){ arr[i]=temp[i]; } } public static void radix_sort(){ int[] count=new int[10]; int[] temp=new int[arr.length]; int len=(arr[0]+"").length(); for(int i=0;i<len;i++){ Arrays.fill(count, 0); counting_sort(i, count, temp); } } public static void main(String[] args){ Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ int n=scanner.nextInt(); arr=new int[n]; int k=0; for(int i=0;i<n;i++){ arr[i]=scanner.nextInt(); if(arr[i]>k) k=arr[i]; } radix_sort(); StringBuffer str=new StringBuffer(); for(int i:arr) str.append(i+" "); System.out.println(str.substring(0,str.length()-1)); } scanner.close(); } }
