本文共 1159 字，大约阅读时间需要 3 分钟。

1、计数排序简介

计数排序是一种基于比较的排序。它的设计思想是，通过开辟额外的一个空间，将原始数据值转化为键，按顺序取出键，即排序后的序列。

计数排序对待排序序列是有一定要求的，待排序序列必须是一个有确定范围的整数。因为计数排序的思想是将待排序序列的值映射为键，所以，必须是整数。

2、算法步骤

1. 先遍历一遍原始序列，找出序列中的最大值。
2. 通过最大值构建一个新的数组，记为target。
3. 再次遍历原始序列，将原始序列的值映射到新数组target的索引，当有值映射到索引的时候，将索引对应的值加1。
4. 最后遍历新数组target，按照索引值从小到大，如果索引对应的值不为0，就将索引值拿出来，然后索引的值-1，直到该索引值为0。

以图为例：

假设给定的初始待排序序列为

4

3

5

9

3

8

4

5

1

首先，先找出最大值，即9； 然后创建一个新的数组，长度为10，最大索引值即为9； 遍历原始数组，遍历完之后，新数组为：

0

1

0

2

2

2

0

1

1

新数组中，值不为0说明该索引在原序列中作为值出现过，索引处的元素值即表示该索引作为原序列的值出现的次数；遍历该数组即可完成排序

1

3

3

4

4

5

5

8

9

3、代码实现

public class CountingSort {	public static void countingSort(int[] arr) {		if (arr == null || arr.length == 0) {			return;		}		// 先遍历一遍原始数组，找出最大值		int max = 0, len = arr.length;		for (int i = 0; i < len; i++) {			if (arr[i] > max) {				max = arr[i];			}		}		// 定义另外一个数组，用来转化原始数组		int[] target = new int[max + 1];		// 第二遍遍历		for (int i = 0; i < len; i++) {			int val = arr[i];			target[val] = target[val] + 1;		}		// 遍历target数组，拿出全部元素		int j = 0;		for (int i = 0; i < max + 1; i++) {			int val = target[i];			while(val > 0) {				arr[j] = i;				val--;				j++;			}		}	}}

4、复杂度分析

计数排序的时间复杂度和空间复杂度均为$O(n+k)$，其中$k$是整数的范围。

转载地址：http://kayin.baihongyu.com/