排序算法之线性排序分析——桶排序、计数排序、基数排序_计数排序最好情况下的空间复杂度为o(n + k)

线性排序

桶排序、计数排序、基数排序是时间复杂度是 O(n) 的序算法。

因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。

之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。 

此外，线性排序对排序数据的要求很苛刻，要注意线性排序算法的适用场景。

 

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶；
• 计数排序：每个桶只存储单一键值；
• 桶排序：每个桶存储一定范围的数值；

桶排序

算法思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。

桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

桶内可能使用别的排序算法（根据桶内数据情况选择排序算法，一般选择时间复杂度为O(nlogn)的算法，桶内数据较少可以选择插入排序算法）或是以递归方式继续使用桶排序进行排序

 

桶排序的限制（桶排序的适用场景）

桶排序对于数据要求十分苛刻：

一、要排序的数据需要很容易就能划分成 m 个桶

二、桶与桶之间有着天然的大小顺序。（这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。）

三、数据在各个桶之间的分布是比较均匀的。

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

桶排序比较适合用在外部排序中。

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

假如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。

我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内的订单，以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02…99）。

理想的情况下，如果订单金额在 1 到 10 万之间均匀分布，那订单会被均匀划分到 100 个文件中，每个小文件中存储大约 100MB 的订单数据，我们就可以将这 100 个小文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。

但是订单按照金额在 1 元到 10 万元之间并不一定是均匀分布的 ，所以 10GB 订单数据是无法均匀地被划分到 100 个文件中的。有可能某个金额区间的数据特别多，划分之后对应的文件就会很大，没法一次性读入内存。

针对这些划分之后还是比较大的文件&