排序算法下界

对任意的比较排序算法都可以抽象为一棵决策树，它是一棵完全二叉树，可以表示在给定输入规模下对所有元素的比较操作，其中，控制、数据移动等其它操作都被忽略。对于一个正确的排序算法，它都能够生成输入的每一种排列，所以对一个正确的比较排序算法来说，n个元素的$n!$种可能的排列都应该出现在决策树的叶结点上，对于一个给定的输入，其排序结果必然就是这所有可能中的某一个。

根据这个比较排序的决策树模型，从根结点到一个可达的叶结点之间的最长简单路径的长度，表示的是对应排序算法中最坏情况下的比较次数，它等于决策树的高度。因此，当决策树中的每种排列都是以可达的叶结点形式出现时，该决策树高度的下界也就是比较排序算法运行时间的下界。

最坏情况的下界

考虑一棵高度为h，具有l个可达叶结点的决策树，它对应一个对n个元素所做的比较排序，输入的$n!$种可能的排序都是叶结点，并且一棵高度为h的二叉树中，叶结点的数量不多于$2^h$，因此有： $$ n! \leq l \leq 2^h $$ 得到 $$ h \geq \lg (n!) = \Omega (n\lg n) $$

计数排序

适用场景

n个输入元素是0到k区间的整数，或者元素可以通过转换函数，在不丢失大小信息的情况下，唯一地映射到0到k区间某一个整数。

基本思想

对每一个输入元素x确定小于x的元素个数，利用这一信息可以直接将x放到它在输出数组中的位置上。

实现

def counting_sort_integer(A, B, k):
    C = [0 for x in xrange(0, k+1)]
    for x in A:
        C[x] += 1
    for i in xrange(0, k+1):
        if i > 0:
            C[i] += C[i-1]
    for x in A:
        # index start with 0, so minus 1
        B[C[x]-1] = x
        C[x] -= 1

if __name__ == '__main__':
    A = [123, 21, 14321, 0, 120, 98, 1000, 1024, 123, 1, 0, 123, 24, 123, 3, 2, 12]
    B = [None] * len(A)
    counting_sort_integer(A, B, 14321)
    print B

基数排序

适用场景

对具有多关键字域的记录或某一基数表示的数（二进制位表示，10进制数，16进制数，字符串等）进行排序，其共同的特点是每个元素有d位，每一位有一个固定的取值区间，因此可以利用到计数排序的方法。

基本思想

对于有n个d位元素的输入，从每个元素的最低有效位开始，到最高有效位，使用一个稳定的排序算法对n个元素进行排序。一个稳定的排序算法指对相等元素的排序不改变它们已有的顺序。

稳定的排序

计数排序可以很容易做到稳定排序，只需在使用计数序号将输入元素放入输出元素时，先放入输入序列中靠后的元素即可，因此上面的计数排序的稳定版本为：

def counting_sort_integer(A, B, k):
    C = [0 for x in xrange(0, k+1)]
    for x in A:
        C[x] += 1
    for i in xrange(0, k+1):
        if i > 0:
            C[i] += C[i-1]
    for j in xrange(len(A)-1, -1, 0):
        x = A[j]
        # index start with 0, so minus 1
        B[C[x]-1] = x
        C[x] -= 1

其它排序算法也可以设计为稳定的排序，但可能需要额外的的时间和空间复杂度，这也是算法导论中的一道练习题。

实现

def counting_sort_char(index, A, B, k):
    """
    i: the digit index for comparation
    """
    C = [0 for x in xrange(0, k+1)]
    for x in A:
        # digit index exceed digit length
        if index >= len(x):
            C[0] += 1
        else:
            C[ord(x[index])] += 1
    for i in xrange(0, k+1):
        if i > 0:
            C[i] += C[i-1]
    # Now C[i] contains the number of element smaller or equal to i,
    # which i is "index"th digit of element of A
    for j in xrange(len(A)-1, -1, -1):
        x = A[j]
        i = 0
        if index < len(x):
            i = ord(x[index])
        # index start with 0, so minus 1
        B[C[i]-1] = x
        C[i] -= 1

def radix_sort_string(A, d):
    size = len(A)
    for i in xrange(0, d):
        B = [None] * size
        counting_sort_char(i, A, B, 255)
        A = B
        print A
    return A

if __name__ == '__main__':
    A = ["a", "bc", "def", "c", "hello world", "asdasdf", "code", "python", "081324asdf", "1", "shark-"]
    d = 1
    for e in A:
        length = len(e)
        if length > d:
            d = length
    B = radix_sort_string(A, d)
    print B

桶排序

适用场景

输入数据服从均匀分布，它由一个随机过程产生，该过程将元素均匀、独立地分布在[0, 1)区间上。

基本思想

输入序列的大小为n，桶排序将[0, 1)区间划分为n个相同大小的子区间，也称这些子区间为桶。然后将n个输入数分别放到各个桶中。因为输入数据是均匀分布的，一般不会出现很多元素落入同一个桶中的情况。将所有元素都放入相应的桶中后，对每个桶中的元素进行排序，然后按顺序遍历所有桶中的元素即可。

实现

def swap(A, i, j):
    temp = A[i]
    A[i] = A[j]
    A[j] = temp

def bubble_sort(A):
    for i in xrange(len(A) - 1, -1, -1):
        max = A[i]
        for j in xrange(i - 1, -1, -1):
            if A[j] > max:
                max = A[j]
                swap(A, i, j)

def bucket_sort(A):
    n = len(A)
    min_v = min(A)
    max_v = max(A)
    range = max_v - min_v
    range += range / n
    bucket = [[] for _ in xrange(0, n)]
    for x in A:
        i = int((x - min_v) / range * n)
        bucket[i].append(x)
    current = 0
    for i in xrange(0, n):
        bubble_sort(bucket[i])
        for x in bucket[i]:
            A[current] = x
            current += 1

if __name__ == '__main__':
    A = [57, 35, -100.2, -12, -20, -23.123, 0, -12, -20, -23.123, 0, 1, 23, 214, 123, 135]
    bucket_sort(A)
    print A