相关博客：

排序算法：冒泡排序、插入排序、选择排序、希尔排序

排序算法：归并排序、快速排序

排序算法：桶排序、计数排序、基数排序

排序算法：堆排序

十大排序算法小结

这篇博客将主要介绍三种时间复杂度是O(n)的排序算法：桶排序、计数排序、计数排序。因为这些排序算法的时间复杂度都是线性的，所以也把这类排序算法称为线性排序。之所以能够做到线性的时间复杂度，主要原因是这几个算法是非基于比较的排序算法，不涉及元素之间的比较操作。

这几种排序算法的时间复杂度虽然低，但是对要排序的数据要求比较苛刻，所以我们关键是要知道这些排序算法的适用场景。

一、桶排序：

1、算法原理：

桶排序的核心思想就是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶排序完之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

2、图片演示：

3、桶排序的时间复杂度为O(n)：

如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用归并排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

所以，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少，但相应的空间消耗就会增大。 

4、桶排序的使用条件和适用场景：

桶排序对要排序的数据的要求是非常苛刻的。使用条件如下：

（1）首先，要排序的数据需要很容易就能划分成m个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内数据都排序完之后，桶与桶之间的数据不需要在进行排序。

（2）其次，数据在各个桶之间的分布比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。

所以，桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

5、应用案例：

（1）需求描述：有10GB的订单数据，需按订单金额（假设金额都是正整数）进行排序，但内存有限，仅几百MB。

（2）解决思路：

扫描一遍文件，看订单金额所处数据范围，比如1元-10万元，那么就分100个桶。

第一个桶存储金额1-1000元之内的订单，第二个桶存1001-2000元之内的订单，依次类推。

每个桶对应一个文件，并按照金额范围的大小顺序编号命名（00，01，02，…，99）。

将100个小文件依次放入内存并用快排排序。

所有文件排好序后，只需按照文件编号从小到大依次读取每个小文件并写到大文件中即可。

注意点：若单个文件无法全部载入内存，则针对该文件继续按照前面的思路进行处理即可。

二、计数排序：

1、算法原理：

计数排序可以看成是桶排序的一种特殊情况，只是桶的大小粒度不一样。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

2、适用场景：

计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

3、动图演示：

4、算法描述：

（1）找出待排序的数组中最大和最小的元素；

（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；

（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

5、应用案例：

（1）假设只有8个考生分数在0-5分之间，成绩存于数组A[8] = [2，5，3，0，2，3，0，3]。

使用大小为6的数组C[6]表示桶，下标对应分数，即0，1，2，3，4，5。

C[6]存储的是考生人数，只需遍历一边考生分数，就可以得到C[6] = [2，0，2，3，0，1]。

对C[6]数组顺序求和则C[6]=[2，2，4，7，7，8]，C[k]存储的是小于等于分数k的考生个数。

（2）数组R[8] = [0，0，2，2，3，3，3，5]存储考生名次。那么如何得到R[8]的呢？

从后到前依次扫描数组A，比如扫描到3时，可以从数组C中取出下标为3的值7，也就是说，到目前为止，包括自己在内，分数小于等于3的考生有7个，也就是说3是数组R的第7个元素（也就是数组R中下标为6的位置）。当3放入数组R后，小于等于3的元素就剩下6个了，相应的C[3]要减1变成6。

以此类推，当扫描到第二个分数为3的考生时，就会把它放入数组R中第6个元素的位置（也就是下标为5的位置）。当扫描完数组A后，数组R内的数据就是按照分数从小到大排列的了。

6、Java代码实现：

public class CountingSort {

	public  void countingSort(int[] a){
		int len = a.length;
		if(len<=1) return;
		
		//1、查找数组中数据的范围
		int max = a[0];
		for(int i=1;i<len;i++){
			if(max<a[i]) max=a[i];
		}
		
		//2、申请一个数组c
		int[] c = new int[max+1]; 
		//3、遍历数组，计算每个元素的个数，放入c中。
		for(int i=0;i<len;i++)
			c[a[i]]++;
		
		//4、依次累加
		for(int i=1;i<=max;i++)
			c[i]=c[i-1]+c[i];
		
		//5、申请一个临时数组，存储排序后的结果，并反向填充。
		int[] r = new int[len];
		//计数排序的关键步骤，参照上图：
		for(int i=len-1;i>=0;i--){
			int index = c[a[i]]-1;
			r[index] = a[i];
			c[a[i]]--;
		}
		
		//6、将结果拷贝回原数组
		for(int i=0;i<len;i++)
			a[i]=r[i];
	}
}

7、算法分析：

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

三、基数排序：

1、算法原理：

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

2、使用条件：

基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，因为基数要借助桶排序或者计数排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

3、动图演示：

（1）得数组中的最大数，并取得位数；

（2）arr为原始数组，从最低位开始取每个位组成radix数组；

（3）对radix进行计数排序（利用计数排序适用于小范围数的特点）；

4、算法分析：

（1）基数排序基于分别排序，分别收集，所以是稳定的。

（2）如果要排序的数据有 k 位，那我们就需要 k 次桶排序或者计数排序，总的时间复杂度是 O(k*n)。当 k 不大的时候，当 k 不大的时候，比如手机号码排序的例子，k 最大就是 11，所以基数排序的时间复杂度就近似于 O(n)。

（3）基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。

5、应用案例：

需求：排序10万个手机号：

（1）比较两个手机号码a，b的大小，如果在前面几位中a已经比b大了，那后面几位就不用看了。但是这种排序不稳定。

（2）借助稳定排序算法的思想，可以先按照最后一位来排序手机号码，然后再按照倒数第二位来重新排序，以此类推，最后按照第一个位重新排序。

（3）经过11次排序后，手机号码就变为有序的了。

（4）每次排序有序数据范围较小，可以使用桶排序或计数排序来完成。

本篇博客主要参考《极客时间》王争的《数据结构与算法之美》专栏第13节。