首页 > 基础算法 > 排序 > 计数排序-Counting Sort
2014
04-08

计数排序-Counting Sort

常见的非比较排序算法有3个 计数排序,基数排序,桶排序,平均时间复杂度都是O(n)。比较排序就是指通过比较操作(通常是“小于或等于”操作)来确定两个元素中哪个应该放在序列前面。比较排序的算法理论的算法复杂度下线为:O(nlgn)。但是这3个排序算法并没有我们常见的快速排序,归并排序等出名,主要是限制比较多。

 1.计数排序

当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是 Θ(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。例如:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

通俗地理解,例如有10个年龄不同的人,统计出有8个人的年龄比A小,那A的年龄就排在第9位,用这个方法可以得到其他每个人的位置,也就排好了序。当然,年龄有重复时需要特殊处理(保证稳定性),这就是为什么最后要反向填充目标数组,以及将每个数字的统计减去1的原因。 算法的步骤如下:

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

假定输入是个数组A【1…n】, length【A】=n。 另外还需要一个存放排序结果的数组B【1…n】,以及提供临时存储区的C【0…k】(k是所有元素中最大的一个)。算法伪代码

Counting Sort

下面看一个例子来理解:

假设数字范围在 0 到 9. 
输入数据: 1, 4, 1, 2, 7, 5, 2
  1) 使用一个数组记录每个数组出现的次数
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     0  2  2  0   1  1  0  1  0  0

  2) 累加所有计数(从C中的第一个元素开始,每一项和前一项相加)
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     0  2  4  4  5  6  6  7  7  7

更改过的计数数组就表示 每个元素在输出数组中的位置

  3) 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1
 例如对于: 1, 4, 1, 2, 7, 5, 2. 1 的位置是 2.
 把1放在输出数组的第2个位置.并把计数减 1,下一个1出现的时候就放在了第1个位置。(方向可以保持稳定)

下面是java语言的实现:

public class CountingSort {
	// 类似bitmap排序
	public static void countSort(int[] a, int[] b, final int k) {
		// k>=n
		int[] c = new int[k + 1];
		for (int i = 0; i < k; i++) {
			c[i] = 0;
		}
		for (int i = 0; i < a.length; i++) {
			c[a[i]]++;
		}
		System.out.println("\n****************");
		System.out.println("计数排序第2步后,临时数组C变为:");
		for (int m : c) {
			System.out.print(m + " ");
		}

		for (int i = 1; i <= k; i++) {
			c[i] += c[i - 1];
		}
		System.out.println("\n计数排序第3步后,临时数组C变为:");
		for (int m : c) {
			System.out.print(m + " ");
		}

		for (int i = a.length - 1; i >= 0; i--) {
			b[c[a[i]] - 1] = a[i];// C[A[i]]-1 就代表小于等于元素A[i]的元素个数,就是A[i]在B的位置
			c[a[i]]--;
		}
		System.out.println("\n计数排序第4步后,临时数组C变为:");
		for (int n : c) {
			System.out.print(n + " ");
		}
		System.out.println("\n计数排序第4步后,数组B变为:");
		for (int t : b) {
			System.out.print(t + " ");
		}
		System.out.println();
		System.out.println("****************\n");
	}

	public static int getMaxNumber(int[] a) {
		int max = 0;
		for (int i = 0; i < a.length; i++) {
			if (max < a[i]) {
				max = a[i];
			}
		}
		return max;
	}

	public static void main(String[] args) {
		int[] a = new int[] { 2, 5, 3, 0, 2, 3, 0, 3 };
		int[] b = new int[a.length];
		System.out.println("计数排序前为:");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
		countSort(a, b, getMaxNumber(a));
		System.out.println("计数排序后为:");
		for (int i = 0; i < a.length; i++) {
			System.out.print(b[i] + " ");
		}
		System.out.println();
	}
}

输出:

计数排序前为:
2 5 3 0 2 3 0 3 

****************
计数排序第2步后,临时数组C变为:
2 0 2 3 0 1 
计数排序第3步后,临时数组C变为:
2 2 4 7 7 8 
计数排序第4步后,临时数组C变为:
0 2 2 4 7 7 
计数排序第4步后,数组B变为:
0 0 2 2 3 3 3 5 
****************

计数排序后为:
0 0 2 2 3 3 3 5

时间复杂度: O(n+k)
空间复杂度: O(n+k)

其它:

1. 计数排序是有效的,如果输入数据的范围是不显著大于数字的个数。

2. 它不是一个基于比较的排序。它运行的时间复杂度为O(n)

3. 它经常被用来作为另一个排序算法像基数排序的一个子程序。

4. 计数排序可以扩展到负输入也可以。

参考:http://www.cnblogs.com/ttltry-air/archive/2012/08/04/2623302.html


  1. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts