线性排序

今天做leetcode突然碰到了桶排序，居然想不清楚了，顺便把剩下几个也写下，以后看。

计数排序

计数排序大概就是确定输入数组的上下界后，我们创建数组C[0…k]，用于统计不超过每一个值得元素个数。当得到统计表后，我们就可以很容易的直到原始数组中每个元素排序后应处于的位置信息了。

计数排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def countSort(nums):
    '''
    Sort non-negative intergers.
    O(N+K) time complexity 
    O(N+K) space complexity
    '''
    k = max(nums)
    c = [0] * (k+1)
    sortedArray = [0] * len(nums)
    # Place
    for n in nums:
        c[n] += 1
    # Count
    for ind, val in enumerate(c[:-1]):
        c[ind+1] += c[ind]
    # Sort
    for n in nums:
        sortedArray[c[n]-1] = n
    return sortedArray

桶排序

但是计数排序怎么看都是一个有点逗的排序方法，我们来回扫描了多次数组c，并且当元素比较稀疏时，数组c占用了许多无用的空间。所以就有了桶排序，我们把元素按照大小划分到M个不同的bucket中，随后在每一个bucket中进行排序，最后将这些bucket拼接起来得到最后的排序结果。算法复杂度为 O(N) + MO(N/Mlog(N/M)) = O(N) + O(N)*O(logN - logM)

可以发现当M接近于N时，算法复杂度就会接近于线性，当然这也会需要一些额外的空间开销，但不会超过线性需求，代码如下：

桶排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def bucketSort(nums):
    '''
    Sort non-negative intergers.
    O(N) time complexity 
    '''
    bucketNum = 2000
    k = max(nums)  # The upper bound.
    # Initializing all the buckets
    buckets = [[] for i in xrange(bucketNum)] 

    # Map to buckets
    for n in nums:
        buckets[n/k*(bucketNum-1)].append(n)
    
    # Sort each bucket. O(N/M*log(N/M)) time consumption each
    buckets = [sorted(bucket) for bucket in buckets]
    # Merge
    from itertools import chain
    return list(chain(*buckets))

基数排序

最后呢就是基数排序，其实只是为了可以按照多个关键字进行排序而设计的一种方法，在这里对于整数情况，我们直接按每位拆开，由地位至高位一次排序即可，每一次小的排序过程我们都使用了稳定的桶排序。时间复杂度实际是 k * O(N),代码如下：

桶排序
1
2
3
4
5
6
7
8
9
10
11
12
13
def radixSort(nums):
    radix = 10
    import math
    # Maxium digits
    k = int(math.ceil(math.log(max(nums), radix)))
    sortedNums = nums
    for i in range(k):
        buckets = [[] for j in range(radix)]
        for num in sortedNums:
            buckets[num / (radix**(i+1)) % radix].append(num)
        from itertools import chain
        sortedNums =  list(chain(*buckets))
    return sortedNums