# 09 线性排序

![linkedlist](/images/algo/sort/bucket.jpg)
非基于比较的三个排序算法: 桶排序，计数排序，基数排序

<!-- more -->

## 1. 线性排序
桶排序、计数排序、基数排序的时间复杂度是线性的，所以我们把这类排序算法叫作**线性排序**（Linear sort）。之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。

这几种排序算法理解起来都不难，时间、空间复杂度分析起来也很简单，但是对要排序的数据要求很苛刻，所以我们今天学习重点的是掌握这些排序算法的适用场景。

桶排序和计数排序的排序思想是可以对数剧集进行**有限分类**，都是针对范围不大的数据，将数据划分成不同的桶来实现排序，只不过二者桶的粒度不同。基数排序要求数据可以划分成高低位，位之间有递进关系。比较两个数，我们只需要比较高位，高位相同的再比较低位。而且每一位的数据范围不能太大，因为基数排序算法需要借助桶排序或者计数排序来完成每一个位的排序工作。

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

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

```python
from collections import deque


def sort_bucket(S):
    """
    :param S: [(v, item)]
    :return:
    """
    m = max((i[0] for i in S))
    bucket_map = [deque() for i in range(m + 1)]
    for i in S:
        bucket = bucket_map[i[0]]
        bucket.append(i)

    c = 0
    for i in range(m + 1):
        b = bucket_map[i]
        while len(b) > 0:
            S[c] = b.popleft()
            c += 1
```

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


### 2.2 计数排序
计数排序可视为桶排序的特殊情况，当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。计数排序之所以叫作计数排序，是因为其特殊的通过“计数”进行排序的算法得名的。

```python
def sort_count(S):
    if len(S) <= 1:
        return S
    m = max(S)
    bucket = [0] * (m + 1)
    for i in S:
        bucket[i] += 1

    for i in range(1, m + 1):
        bucket[i] += bucket[i - 1]

    tmp = [0] * len(S)
    for i in S:
        bucket[i] -= 1
        tmp[bucket[i]] = i
    for i in range(len(S)):
        S[i] = tmp[i]

```

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


### 2.3 基数排序
基数排序的核心是可以将数据分割出独立的“位”来比较，然后按照从低位到高位依次排序，只要每次按位排序的算法是稳定的就可以得到正确的排序。

根据每一位来排序，我们可以用刚讲过的桶排序或者计数排序，它们的时间复杂度可以做到 O(n)。如果要排序的数据有 k 位，那我们就需要 k 次桶排序或者计数排序，总的时间复杂度是 O(k*n)。当 k 不大的时候基数排序的时间复杂度就近似于 O(n)。

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

```python
def sort_base(S, num):
    if len(S) <= 1:
        return S
    T = [(0, i) for i in S]
    for n in range(num):
        T = [(i[1] // 10 ** n % 10, i[1]) for i in T]
        sort_bucket(T)
        print T
    for i in range(len(S)):
        S[i] = T[i][1]


aa = [43, 41, 31, 57]
sort_base(aa, 2)
print aa

```

**参考:**
- [王争老师专栏-数据结构与算法之美](https://time.geekbang.org/column/126)
- [《数据结构与算法：python语言实现》](https://book.douban.com/subject/30323938/)