十大排序算法之计数排序

本文首发于个人博客

前言

本系列排序包括十大经典排序算法。

• 使用的语言为：Java
• 结构为：
  定义抽象类Sort里面实现了，交换，大小比较等方法。例如交换两个值，直接传入下标就可以了。其他的具体排序的类都继承抽象类Sort。这样我们就能专注于算法本身。

/*
	 * 返回值等于0，代表 array[i1] == array[i2]
	 * 返回值小于0，代表 array[i1] < array[i2]
	 * 返回值大于0，代表 array[i1] > array[i2]
	 */
	protected int cmp(int i1, int i2) {
		return array[i1].compareTo(array[i2]);
	}
	
	protected int cmp(T v1, T v2) {
		return v1.compareTo(v2);
	}
	
	protected void swap(int i1, int i2) {
		T tmp = array[i1];
		array[i1] = array[i2];
		array[i2] = tmp;
	}

• 冒泡、选择、插入、归并、希尔、堆排序都是基于比较的排序

  • 平均时间复杂度最低O(nlogn)

• 计数排序、桶排序、基数排序不是基于比较的排序

  • 使用空间换时间，某些时候，平均时间复杂度可以低于O(nlogn)

什么是计数排序

• 计数排序（Counting sort）是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组 C ，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C 来将A中的元素排到正确的位置

算法思想

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

核心思想：统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引

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

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

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

算法稳定性

• 计数排序是一种稳定排序算法。

是否是原地算法

• 何为原地算法？
  • 不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入
  • 空间复杂度为 𝑂(1) 的都可以认为是原地算法
• 非原地算法，称为 Not-in-place 或者 Out-of-place
• 计数排序不属于 In-place

时空复杂度

• 最好、最坏、平均时间复杂度：O(n+k)

• 空间复杂度：O(n+k)

代码

先使用最简单的实现方案，先求最大值，用于创建数组，然后遍历出来，统计元素出现的次数，最后再按照顺序赋值

public class CountingSort extends Sort<Integer>{

	protected void sort() {
		//找出最大值
		int max = array[0];
		for (int i = 1; i < array.length; i++) {
			if (array[i]>max) {
				max= array[i];
			}
		}// O(n)
		
		// 开辟内存空间，存储每个整数出现的次数
		int[] counts = new int[max+1];
		// 统计每个整数出现的次数
		for (int i = 0; i < array.length; i++) {
			counts[array[i]]++;
		}// O(n)
		
		// 根据整数的出现次数，对整数进行排序
		int index = 0;
		for (int i = 0; i < counts.length; i++) {
			while (counts[i]-->0) {
				array[index++] = i;
				
			}
		}// O(n)
		
		
	}
		
}

优化

上述代码有些问题

• 无法对负整数进行排序
• 浪费内存空间
• 不是稳定排序

优化思路：

• 假设array中的最小值是min，最大值为max，就以min为索引0开始
  • 例如数组为 -2 4 5,那么 -2索引为0，4索引为6，5的索引为7
• 定义个counts数组，里面存放着每个次数累加上前面的所有次数，得到的就是元素在有序序列中的位置信息
  

优化过的代码为

protected void sort2() {
		//找出最大值和最小值
		int max = array[0];
		int min = array[0];
		for (int i = 1; i < array.length; i++) {
			if (array[i]>max) {
				max= array[i];
			}
			if (array[i]<min) {
				min= array[i];
			}
		}// O(n)
		
		// 开辟内存空间，存储次数
		int[] counts = new int[max-min+1];
		// 统计每个整数出现的次数
		for (int i = 0; i < array.length; i++) {
			counts[array[i]-min]++;
		}// O(n)
		
		// 累加次数
		for (int i = 1; i < counts.length; i++) {
			counts[i]+= counts[i-1];
		}
		
		//从后向前遍历元素，将她放在有序数组中的合适位置
		int[] newArray = new int[array.length];
		for (int i = array.length-1; i >=0 ; i--) {
			//获取元素在counts中的索引
			int index = array[i]-min;
			//获取元素在counts中的值
			//counts[index];
			//放在合适位置
			newArray[--counts[index]] = array[i];
		}
		
		// 将有序数组赋值到array
		for (int i = 0; i < newArray.length; i++) {
			array[i] = newArray[i];
		}
	}

结果

数据源：

从1到80000之间随机生成20000个数据来测试

Integer[] array = Integers.random(20000, 1, 80000);

结果如下

【CountingSort】
稳定性：true 耗时：0.005s(5ms) 比较次数：0 交换次数：0

【QuickSort】
稳定性：false 耗时：0.009s(9ms) 比较次数：33.27万 交换次数：1.32万

【MergeSort】
稳定性：true 耗时：0.01s(10ms) 比较次数：26.10万 交换次数：0

【ShellSort】
稳定性：false 耗时：0.016s(16ms) 比较次数：43.34万 交换次数：0

【HeapSort】
稳定性：false 耗时：0.023s(23ms) 比较次数：51.09万 交换次数：2.00万

【SelectionSort】
稳定性：true 耗时：0.514s(514ms) 比较次数：2.00亿 交换次数：2.00万

【InsertionSort1】
稳定性：true 耗时：1.362s(1362ms) 比较次数：9935.15万 交换次数：9933.15万

【BubbleSort】
稳定性：true 耗时：2.529s(2529ms) 比较次数：2.00亿 交换次数：9933.15万

可以看到这种情况下计数排序的甚至比快速排序，归并排序还要快。

代码地址：

• 文中的代码在git上：github地址