Linear Sort即線性排序震糖，指的是一系列能做到線性時間復雜度即O（n）的排序算法愕贡，這里主要介紹三個：桶排序（bucket sort）穆律，計數(shù)排序（count sort）和基數(shù)排序（radix sort）读慎。
排序算法基于兩類怕品，一類是基于比較的排序野舶，常規(guī)排序一般就是這類秽晚，例如快速排序、歸并排序筒愚、堆排序赴蝇。這種排序方法有著O（nlgn）的下限限制（已有證明比較排序不可能做到比O（nlgn）好）。而非比較排序沒有這個限制巢掺。雖然這些排序方法看上去復雜度比常規(guī)的的時間復雜度O（nlgn）要好句伶，其實都有一些其他方面的限制，所以還是要看情況進行使用陆淀。
- 計數(shù)排序
顧名思義考余，就是通過計算各個元素出現(xiàn)的次數(shù)來排序。 假設出現(xiàn)的元素都在0-k之間轧苫，將這k+1個數(shù)進行頻次計數(shù)楚堤，然后再從小到大把這些數(shù)給排出來。代碼如下：
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
整個算法可以分成兩塊含懊，第一塊計數(shù)身冬，時間復雜度O（n），第二塊擺放岔乔，時間復雜度O（k）酥筝，因此總的時間復雜度是O（n+k），空間復雜度也是O（n+k）雏门。很明顯嘿歌，適用的情況，僅限于所需排序的序列是0-k的整數(shù)而且k比較小茁影。
-
桶排序
桶排序自然要用到“桶”宙帝，所謂的“桶”就是一個個容器，其能容納一個區(qū)間內(nèi)未排序的數(shù)值募闲。利用“桶”步脓，將數(shù)值按照區(qū)域分好，然后各自排序，再連到一起沪编，就是桶排序的思想呼盆。桶內(nèi)排序，可以使用比較排序算法蚁廓。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))
首先是把數(shù)據(jù)壓縮到01的區(qū)間內(nèi)访圃，這里的代碼是取n^(1/2)個桶。假設數(shù)組內(nèi)的最大值是K相嵌，有M個桶腿时，那么相當于把0-K分成M個區(qū)間，即0M-1號桶饭宾。對于某個數(shù)x批糟，應該分到序號為（M-1）*x/K，因為x=0時分到0號桶看铆，x=K時分到第M-1號桶徽鼎。
然后分完數(shù)之后對桶內(nèi)進行排序，排序完之后連起來弹惦。
稍微分析一下復雜度否淤。最壞情況就是所有數(shù)據(jù)都在一個桶里面，那么相當于白干棠隐，還不如直接常規(guī)排序石抡。
最好情況就是數(shù)據(jù)平均分布，總共N個元素M個桶助泽，每個桶就是N/M個元素啰扛，總時間復雜度就是O(N+Nlog(N/M))，當M越大時總復雜度越小嗡贺，但同時空間復雜度也就更高隐解。
此外，只要桶排序內(nèi)部排序算法是穩(wěn)定的暑刃，那么整個桶排序也就是穩(wěn)定的厢漩。
- 基數(shù)排序
基數(shù)排序屬于多key排序，一般是從最小的key分堆排序岩臣，然后再對較大的key排序，直至對所有key完成排序宵膨。
網(wǎng)上很常見的一個例子就是對十進制整數(shù)排序架谎，因為每一位的權重不一樣，因此也是對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是指數(shù)值的最大長度用來確定排序次數(shù)。
總結：線性排序總體來說限制比較多铃将，不夠靈活项鬼，但是在特定場合還是可以用。
例題：maxGap劲阎。給出一個未排序的非負整數(shù)數(shù)組绘盟，找出其排序狀況下的相鄰兩個數(shù)的最大差值。要求線性時間悯仙。
【解】這個題就是線性排序的用武之地奥此。假如不排序，幾乎沒法做雁比。當然也可以用Quick Sort強行線性（其復雜度從O（n）~O（n^2））稚虎，不過用正宗的線性排序顯然更好。
對這道題而言偎捎，計數(shù)排序明顯不靠譜蠢终，基數(shù)排序并沒有多key，所以桶排序是最佳的選擇茴她。事實上寻拂，桶排序時可以不用在桶里面sort，因為題目只是要求max gap丈牢，因此如果能知道每一個桶內(nèi)的max和min祭钉，那么桶與桶之間的gap就知道了。至于桶內(nèi)的呢己沛？平均gap是(max-min)/(N-1)慌核，如果讓每個桶剛好覆蓋平均gap大小，那么極端情況就是每個桶一個元素申尼，桶內(nèi)gap不用考慮垮卓；否則，某些桶多某些桶少师幕，出現(xiàn)分布不均勻的情況時粟按，最大gap也只可能出現(xiàn)在桶與桶之間。
# 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
