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

灰太狼 2023-02-20 02:35 68阅读 0赞

# 比较排序VS非比较排序 #

常见的快速排序、归并排序、堆排序、冒泡排序等术语比较排序。在排序的最终结果里，元素之间的次序依赖于他们之间的比较。每个数都必须和其他数比较，才能确定自己的位置。

在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。  
比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr\[i\]之前有多少个元素，则唯一确定了arr\[i\]在排序后数组中的位置。

非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。

非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

# 非比较排序 #

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

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

## 桶排序 ##

### 算法原理 ###

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

### 图片演示 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

### 桶排序的时间复杂度为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)。

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

### 桶排序的使用条件与适用场景 ###

桶排序对要排序的数据的要求是十分苛刻的。适用条件如下：

*  首先，要排序的数据需要很容易就能划分为m个桶，并且，桶与桶之间有者天然的大小顺序，这样每个桶内数据都排序完成之后，桶与桶之间的数据不需要再进行排序。
 *  其次，数据再各个桶之间的分布比较均匀。如果数据经过桶的划分之后，有些桶的数据非常多，有些非常少，很不平均，那么桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。

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

### 应用案例 ###

#### 需求描述 ####

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

#### 解决思路： ####

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

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

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

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

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

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

## 计数排序 ##

### 算法原理 ###

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

### 适用场景 ###

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

### 算法描述 ###

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

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

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

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

### 应用案例 ###

[具体参考][Link 1]

### 算法分析 ###

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

## 基数排序 ##

### 算法原理 ###

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

### 使用条件 ###

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

### 过程 ###

*  得到数组中的最大数，并取得位数
 *  arr为原始数据，从最低位开始取每个为组成radix数组；
 *  对radix进行基数排序（利用计数排序适用于小范围数的特点）；

### 应用案例 ###

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

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

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

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

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

原文链接：https://blog.csdn.net/a745233700/article/details/86693150

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200622112840693.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/zhizhengguan/article/details/106879225