在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。

计数排序

平均时间复杂度：O(n+k)；最好情况：O(n+k)；最坏情况：O(n+k)；

空间复杂度：O(k)

排序方式：Out-place （占用常数内存，不占用额外内存）

稳定性：稳定

Implementation:

/**
 * 计数排序
 * @author hxr
 * @see https://github.com/MisterBooo/LeetCodeAnimation
 * 核心：申请数组中(max-min)大小的数组，统计数组中各元素的个数，并按元素与min的关系放入申请的数组中，即可输出有序数组。
 */
public class CountingSort {
	public static void main(String[] args) {
		int[] sourceArray = { 8, 5, 6, 9, 5, 5, 5, 4 };
		
		// 对 arr 进行拷贝，不改变参数内容
		int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
		sort(arr);
		System.out.println("排序前："+Arrays.toString(sourceArray));
		System.out.println("排序后："+Arrays.toString(arr));
	}

	private static int[] sort(int[] arr) {
		if (arr.length > 1) {
			//假设下标为0的值最小，下标为1的值最大。
			int min = 0;
			int max = 1;
			if (arr[0] > arr[1] ) {
				min = 1;
				max = 0;
			}
			//同时找出数组中的最大最小值
			for (int i = 2; i < arr.length; i++) {
				if (arr[i] < arr[min]) {
					min = i;
				}
				if (arr[i] > arr[max]) {
					max = i;
				}
			}
			//对统计数组每个数计数
			int[] sort = counting(arr,arr[max],arr[min]);
			System.out.println("数组中的数计数："+Arrays.toString(sort));
			//重新排列arr,使有序
			int minarr = arr[min];
			for (int i = 0,j = 0; i < sort.length;) {
				if (sort[i] > 0) {
					arr[j] = minarr+i;
					j++;
					sort[i]--;
				}else{
					i++;
				}
			}
		}
		return arr;
	}
	
	//对统计数组每个数计数
	private static int[] counting(int[] arr, int max, int min) {
		int[] count = new int[max-min+1];
		for (int i = 0; i < arr.length; i++) {
			count[arr[i] - min] ++;
		}
		return count;
	}
}

Go after

计数排序-排序算法

计数排序