算法导论——计数排序

通过统计元素的个数来达到排序的目的。
优点：
不需要对元素比较就能对元素进行排序（这个想法很巧妙）。
缺点：
1：只能对自然数进行排序。
2：自然数的数值不能太大（排序过程中需要创建一个计数数组，其长度要不能小于数组中的最大值）

实现代码：

import java.lang.reflect.Array;

public class CountSort<T extends Number> {

	private T[] array;

	public CountSort(T[] array) {
		this.array = array;
	}

	public void sort() {
		int[] count = new int[10000];
		//统计每个元素的个数
		for (T i : array) {
			int intValue = i.intValue();
			count[intValue] += 1;
		}
		for (int i = 1; i < count.length; i++) {
			count[i] += count[i - 1];
		}
		@SuppressWarnings("unchecked")
		T[] copy = (T[]) Array.newInstance(Number.class, array.length);
		for (int i = copy.length - 1; i > -1; i--) {
			int value = array[i].intValue();
			copy[count[value] - 1] = array[i];
			count[value]--;
		}
		this.array = copy;
	}

	public static void main(String[] args) {
		Integer[] temp = new Integer[] { 9, 8, 7, 4, 3, 5, 6, 1 };
		// temp = new Integer[] { 9, 8, 7, 6, 5,4, 3, 2 };
		temp = new Integer[] { 2, 5, 3, 0, 2, 3, 0, 3 };
		temp = new Integer[] {  9, 8, 7, 4, 3, 5, 6, 1,0  };
		CountSort<Integer> qs = new CountSort<Integer>(temp);
		qs.sort();
		qs.print();
	}

	private void print() {
		for (T i : array) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

}