计数排序

2020-11-13

无论冒泡排序，还是快速排序，都是基于元素之间的排序进行比较。计数排序是利用数组的下标来来确定元素的正确位置。

对 11 个随机整数进行排序（[9，3，5，4，9，1，2，7，8，1，3]），假设这些整数的取值范围是 0-10 ，那么每个整数就必定是 0-10 中的任意一个数。

因此我们可以建立一个统计数组（下标 i 的数值代表着元素 i 出现的次数），首先建立一个长度为 11 的数组，每个元素初始化为 0.

然后遍历数组，在统计数组中对出现的元素，次数 + 1，作为该元素的频次。

比如按照上面那个数组，第一个元素是 9 ，那么下标为 9 的元素就更改为 1 。最后频率数组为 [0，2，1，2，1，1，0，1，1，2]

有了统计结果，排序就是直接输出 a[index] 个 index

[1，1，2，3，3，4，5，7，8，9，9]

计数排序存在两中情况：

1）数组个数已知，统计数组长度就是数组个数。

2）数组个数未知，不再以（输入数列的最大值+1）作为统计数组的长度，而是以（数列最大值和最小值的差+1）作为统计数组的长度

2.1）出现重复的元素（每个元素数值相同，但意义不同），怎么知道排名前后。

初始化统计数组，统计数组从第二个元素开始，每一个元素都加上前面所有元素之和，这样相加的目的，是让统计数组存储的元素值，等于相应整数的最终排序位置。比如下标是9的元素值为5，代表原始数列的整数9，最终的排序是在第5位。
创建输出数组 sortedArray，长度和输入数列一致。然后从后向前遍历输入数列：
- 第一次遍历到 x ，让 x 的数值 -1 ，代表下次遇见 x （同数值），是排在数值 -1 位。

算法实现

//	 计数排序
	public static int[] countSort(int[] nums){
		int len = nums.length;
//		 1. 找出最大值和最小值，计算出 d
		int max= nums[0];
		int min = nums[0];
		for(int i = 0; i < len;i++ ){
			if(nums[i] > max){
				max = nums[i];
			}else if(nums[i] < min){
				min = nums[i];
			}
		}
		int d = max - min +1;
//	2. 创建统计数组，初始化全为 0 
		int[] countArray = new int [d];
		for(int i = 0; i < nums.length;i++ ){
//			统计次数
			countArray[nums[i] - min] ++ ;
		}  
		
		
//		不需要知道相同元素出现的前后次序 就直接输出统计数组
//// 3. 统计数组，直接输出  
//		int index = 0;
//		int[] sortArray = new int [len];
////		外层遍历的是统计数组 的下标
//		for(int i = 0; i < countArray.length;i++){
////			内层遍历，如果统计数组数值不为0 ，说名 index 出现了 countArray[j]次
//			for(int j = 0 ;j < countArray[j];j++){
//				sortArray[index++] = i;
//			}
//		}

//	3	需要知道相同元素出现的前后次序，对统计数组做变形 后面的元素等于前面的元素之和
		for(int i = 1; i < countArray.length;i++ ){
			// 除第一个元素外，其他元素都等于前面元素的累加和
			countArray[i] += countArray[i-1];
		}
		
//    4.倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
		int[] sortArray = new int [len];
		for(int i = nums.length -1; i >= 0; i-- ){
//		数组的第一个数据排在排在第 countArray[nums[i] - min]  位子，但是因为拿数组存储，所以下标 -1
//			nums[i] 排在第 countArray[nums[i] - min] 个上面
			sortArray[countArray[nums[i] - min] -1] = nums[i];
			countArray[nums[i] - min] --;
		}
		return sortArray;
	}

时间复杂度： 1.2.4都涉及到遍历原始数列运算量为 N，第 3 步统计遍历数列，运算量为 M，3N+M,时间复杂度为 N+M。

空间复杂度：如果不考虑结果数组，只考虑数组大小的话，空间复杂度是 m 。

当数列最大最小值差距过大时，并不适用计数排序。

当数列元素不是整数，并不适用计数排序。