Linear Sort即线性排序，指的是一系列能做到线性时间复杂度即O（n）的排序算法，这里主要介绍三个：桶排序（bucket sort），计数排序（count sort）和基数排序（radix sort）。
排序算法基于两类，一类是基于比较的排序，常规排序一般就是这类，例如快速排序、归并排序、堆排序。这种排序方法有着O（nlgn）的下限限制（已有证明比较排序不可能做到比O（nlgn）好）。而非比较排序没有这个限制。虽然这些排序方法看上去复杂度比常规的的时间复杂度O（nlgn）要好，其实都有一些其他方面的限制，所以还是要看情况进行使用。
- 计数排序
顾名思义，就是通过计算各个元素出现的次数来排序。 假设出现的元素都在0-k之间，将这k+1个数进行频次计数，然后再从小到大把这些数给排出来。代码如下：
def countingsort( aList, k ):
counter = [0] * ( k + 1 )
for i in aList:
counter[i] += 1
ndx = 0
for i in range( len( counter ) ):
while 0 < counter[i]:
aList[ndx] = i
ndx += 1
counter[i] -= 1
整个算法可以分成两块，第一块计数，时间复杂度O（n），第二块摆放，时间复杂度O（k），因此总的时间复杂度是O（n+k），空间复杂度也是O（n+k）。很明显，适用的情况，仅限于所需排序的序列是0-k的整数而且k比较小。
-
桶排序
桶排序自然要用到“桶”，所谓的“桶”就是一个个容器，其能容纳一个区间内未排序的数值。利用“桶”，将数值按照区域分好，然后各自排序，再连到一起，就是桶排序的思想。桶内排序，可以使用比较排序算法。def bucketsort(A): # get hash codes code = hashing(A) buckets = [list() for _ in range(code[1])] # distribute data into buckets: O(n) for i in A: x = re_hashing(i, code) buck = buckets[x] buck.append(i) for bucket in buckets: bucket.sort() ndx = 0 # merge the buckets: O(n) for b in range(len(buckets)): for v in buckets[b]: A[ndx] = v ndx += 1 import math def hashing(A): m = A[0] for i in range(1, len(A)): if (m < A[i]): m = A[i] result = [m, int(math.sqrt(len(A)))] return result def re_hashing(i, code): return int(i / code[0] * (code[1] - 1))
首先是把数据压缩到01的区间内，这里的代码是取n^(1/2)个桶。假设数组内的最大值是K，有M个桶，那么相当于把0-K分成M个区间，即0M-1号桶。对于某个数x，应该分到序号为（M-1）*x/K，因为x=0时分到0号桶，x=K时分到第M-1号桶。
然后分完数之后对桶内进行排序，排序完之后连起来。
稍微分析一下复杂度。最坏情况就是所有数据都在一个桶里面，那么相当于白干，还不如直接常规排序。
最好情况就是数据平均分布，总共N个元素M个桶，每个桶就是N/M个元素，总时间复杂度就是O(N+Nlog(N/M))，当M越大时总复杂度越小，但同时空间复杂度也就更高。
此外，只要桶排序内部排序算法是稳定的，那么整个桶排序也就是稳定的。
- 基数排序
基数排序属于多key排序，一般是从最小的key分堆排序，然后再对较大的key排序，直至对所有key完成排序。
网上很常见的一个例子就是对十进制整数排序，因为每一位的权重不一样，因此也是对key分次排序的一个例子。
例如170, 45, 75, 90, 802, 2, 24, 66，排序过程如下：
先对个位进行排序：170,90,802,2,24,45,75,66
然后进行十位排序：802,2,24,45,66,170,75,90
最后对百位排序：2,24,45,66,75,90,175,802
当然，key不止限定于十进制的权重。不过基本上就是这么一个思路。假如有k个key，那么一共要排k次，如果使用桶排序，那么就是O（nk）。
def radixSort(a, n, maxLen):
for x in range(maxLen):
bins = [[] for i in range(n)]
for y in a:
bins[(y // 10 ** x) % n].append(y)
a = []
for section in bins:
a.extend(section)
return a
上面的代码，如果是对十进制排序，那至少要有10个桶来放，n=10.maxLen是指数值的最大长度用来确定排序次数。
总结：线性排序总体来说限制比较多，不够灵活，但是在特定场合还是可以用。
例题：maxGap。给出一个未排序的非负整数数组，找出其排序状况下的相邻两个数的最大差值。要求线性时间。
【解】这个题就是线性排序的用武之地。假如不排序，几乎没法做。当然也可以用Quick Sort强行线性（其复杂度从O（n）~O（n^2）），不过用正宗的线性排序显然更好。
对这道题而言，计数排序明显不靠谱，基数排序并没有多key，所以桶排序是最佳的选择。事实上，桶排序时可以不用在桶里面sort，因为题目只是要求max gap，因此如果能知道每一个桶内的max和min，那么桶与桶之间的gap就知道了。至于桶内的呢？平均gap是(max-min)/(N-1)，如果让每个桶刚好覆盖平均gap大小，那么极端情况就是每个桶一个元素，桶内gap不用考虑；否则，某些桶多某些桶少，出现分布不均匀的情况时，最大gap也只可能出现在桶与桶之间。
# Time: O(n)
# Space: O(n)
class Solution:
# @param numss: a list of integers
# @return: the maximum difference
def maximumGap(self, nums):
if len(nums) < 2:
return 0
# Init bucket.
max_val, min_val = max(nums), min(nums)
gap = max(1, (max_val - min_val) // (len(nums) - 1))
bucket_size = (max_val - min_val) // gap + 1
bucket = [{'min': float("inf"), 'max': float("-inf")} for _ in range(bucket_size)]
# Find the bucket where the n should be put.
for n in nums:
# min_val / max_val is in the first / last bucket.
if n in (max_val, min_val):
continue
i = (n - min_val) // gap
bucket[i]['min'] = min(bucket[i]['min'], n)
bucket[i]['max'] = max(bucket[i]['max'], n)
# Count each bucket gap between the first and the last bucket.
max_gap, pre_bucket_max = 0, min_val
for i in range(bucket_size):
# Skip the bucket it empty.
if bucket[i]['min'] == float("inf") and bucket[i]['max'] == float("-inf"):
continue
max_gap = max(max_gap, bucket[i]['min'] - pre_bucket_max)
pre_bucket_max = bucket[i]['max']
# Count the last bucket.
max_gap = max(max_gap, max_val - pre_bucket_max)
return max_gap
