1. 背景
前面几节我们介绍了时间复杂度为的冒泡排序，插入排序，选择排序，时间复杂度为的归并排序、快速排序，今天我们来介绍一下时间复杂度为 的排序算法，他们分别是 桶排序、计数排序、计数排序。<br /> 因为上述三种算法的时间复杂度是线性的，因此也被称为线性排序，同时因为这三种排序对数据的要求比较严格，因此本节我们主要学习这三种特殊的排序算法的应用场景。
2. 桶排序
2.1 核心思想
桶排序的核心思想就是确定几个有序的桶，然后分别对桶内的数据进排序并合并。
2.2 时间复杂度分析
假设我们有个数据，个桶，我们把个数据分别放入有序的个桶中，对每个桶采用快速排序进行排序，这样每个桶排序的复杂度为，（假设每个桶的数据都很均匀），个桶排序的时间复杂度为=。当我们桶足够多，那么k的值就越加接近1，时间复杂度也就越接近。<br /> 通过上述分析我们可以看出，桶排序对待排序的数据要求非常高：
- 数据必须要能分割成几个有序的桶
每个桶的数据必须是均匀的，当桶的数据极为不均匀时，桶排序就会退化为时间复杂度为
的排序算法。
2.3 应用场景
通常，桶排序都被使用在外部排序中。所谓外部排序就是数据存储在磁盘中，内存比较小，无法将全部数据加载到内存中进行处理。<br /> 下面我们思考一个问题：假设有10GB的订单数据，我们希望按照订单金额进行排序（订单金额都是正整数），但是机器的内存有限，只有几百MB，那么我们如何完成这一操作呢？<br /> 这里我们就可以使用桶排序的思想。首先我们先扫描一遍订单文件。假设我们得到的订单金额最小值为1，最大值为10万元。我们根据订单金额将订单数据划分为100个桶中（即文件中），这样第一个桶的订单金额单位为1-100， 第二桶的金额范围为101-200等等，这样我们就可以将所有订单数据分配到100个桶中，假设我们桶的范围分配合理，每个桶中的数据为100MB，这样我们将每个桶（文件）中的数据读入内存进行排序，排序完成之后再写回文件，等到所有桶都排序完成后，按照桶序号将文件合并起来即可。
3. 计数排序
3.1 介绍
计数排序是桶排序的一种特殊情况。适用于数据最大值与最小值差值不大的情况。假设一组数据的最大值，那么我们将桶设置，这样每个桶内的数据都是相同的，就省去了桶内排序的时间。<br /> 大家都经历过考试吧，每次考试结束之后都会学校都会出一个全年级成绩排名表，我们如何快速完成这一排序呢？<br /> 假设成绩的最大值为750分，最小值为0分，那我们就设置751个桶，分别对应0分的同学、1分的同学等等，然后对全年级师生进行扫描，按照每位同学的考试成绩将其放入相应的桶中，最后将各个桶数据一次合并即可。<br /> 下面我们来看一下具体做法：<br /> 为了方便说明，我们缩小数据规模，假设我们有8位考生，他们的成绩放在A[8]中，分别为：2、5、3、0、2、3、0、3。<br /> 考生的成绩从0-5，那么我们 使用大小为6的数组C[6]表示桶，采用下标k的数组元素代表成绩为k的学生个数。依次对学生成绩进行扫描，就可以得出C[6]为：<br /><br /> 从上图中可以看出，成绩为3的同学有3个，成绩小于3的同学有4个，那么成绩为3的同学在排序后的A中，就应该占用下标为4,5,6,的位置。<br />
那么我们如何快速确认每一个A数组元素所在的位置呢？
思路非常巧妙，可能不太容易想到。首先，我们先计算数组C中每个元素与其前一元素的和。即：
这样处理之后，C中各元素的含义自然就发生了变化。下标为K的元素表达的含义为成绩小于等于K的学生的 数量。
那么我们如何根据C数组判断A中各元素应该在的位置呢？
首先对A数组逆向遍历，A的最后一个元素为3，对应到数组C中，小于等于3的元素有7个，而我们当前遍历的这个3又是A数组的最后一个，所以其应当在C[3]-1(6)的位置上，即A数组的第6位，同时我们将C数组中下标为3的元素-1，表明当前A数组中，小于等于3的元素只有六个，即下一个3应该在C[3]-1(5)的位置上。以此类推，知道遍历完整个A数组。
下面我们看一张图：
3.2 复杂度分析
从第一小结可以知道，计数排序执行过程中仅对全部数据执行遍历操作，因此时间复杂度为
。
3.3 应用场景
适合应用于待排序数据的差值不太大，方便对每一种数据单独划分桶的情况。
4. 基数排序
4.1 介绍
介绍基数排序之前，我们先看一个问题：<br /> 假设我们有十万个电话号码，如何对其进行排序？<br />可以采用桶排序吗？答案是否定的，因为电话号码的跨度太大，不适合分桶，但是对于电话号码的每一位，就很适合使用桶排序。<br /> 电话号码排序有这样的特点：当高位比较大时，就不需要对低位进行比较了。 这样的数据特点让我们想到之前的一个范例：按照金额对订单进行排序，当金额相同时按照订单时间进行排序。当时我们的思路为先将订单按照订单时间进行排序，然后使用稳定排序算法将订单按照金额进行排序即可。电话号码排序也是一样，我们先将电话号码按照最后一位排序（使用桶排序/计数排序），然后再对电话号码倒数第二位进行排序，以此类推，经过11次排序之后，就可以得到排序后的电话号码了。
为什么要从最后一位开始排序呢？<br /> 从最后一位开始排序，即使前一位数字是相同的，那么后面数字排好的顺序也不会被打乱，有利于排序。若是从第一位开始排序，第一位排好序后，第二位的排序可能会打乱第一位的排序，这样整个排序就是错误的。
4.2 复杂度分析
整个基数排序过程中，每次排序的时间复杂度为，排序的次数也是常数，因此最终的时间复杂度为。
4.3 应用场景
基数排序适用于下面情景：
若有收获，就点个赞吧
0 人点赞
