计数&桶&基数排序算法

基数排序 vs 桶排序 vs 计数排序：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异。

• 计数排序：每个桶只存储一个类型值，但是数量不限
• 桶排序：存储一定范围的值
• 基数排序：根据每一位的关键字来分配桶

一、计数排序 1、算法描述：

计数排序，不是基于元素比较，而是利用数组下标确定元素的正确位置。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

适用范围：量大但是范围小。

算法的步骤如下：

• 1）找出待排序的数组中最大和最小的元素
• 2）统计数组中每个值为 i的元素出现的次数，存入数组 C的第 i项
• 3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
• 4）反向填充目标数组：将每个元素 i放在新数组的第 C(i)项，每放一个元素就将 C(i)减去1。

2、示例

	public static void main(String[] args) {
		int[] array = { 8, 5, 2, 9, 3, 15, 5, 9999, 2, 7, 5 };
		countingSort(array);
		System.out.println("最终排序结果为：" + Arrays.toString(array));
	}


	public static void countingSort(int[] array) {
		if (array == null || array.length