Algorithm-Sort

比较排序：插入排序、归并排序、堆排序、快速排序

线性时间排序

排序算法的下界

在最坏的情况下，任何比较算法都需要做$\Omega(n \lgn)$
堆排序和归并排序都是渐进最优的比较排序算法

计数排序

基本思想：假设输入数据都属于一个小区间内的整数。对每一个输入元素x，确定小于x的元素个数

Python实现

假设输入A[1…n]，还需要两个数组：B[1…n]存放排序的输出，C[0…k]提供临时存储空间。

def CountingSort(A):
    k=max(A)
    n=len(A)

    C=[0 for i in range(k+1)]
    B=[None for i in range(n)]

    for a in A:
        C[a]+=1
    for i in range(1,len(C)):
        C[i]=C[i]+C[i-1]
    print(C)
    for a in A[::-1]:
        B[C[a]-1]=a
        C[a]-=1
    return B

if __name__=='__main__':
    import random
    # A=random.sample(range(10),k=5)
    A=[54,26,93,17,77,31,44,55,20]
    print("Now displaying CountingSort")
    print('Unsorted sequence:\t', A)
    print('Sorted sequence:\t', CountingSort(A))

复杂度分析

总的时间代价是$\Theta (k+n)$，当k=O(n)，一般采用计数排序，运行时间是$\Theta(n)$

桶排序

假设输入有一个随机过程产生的，该过程将元素均匀、独立地分布在[0,1]区间上。桶排序将[0,1]区间划分为n个相同大小的子区间，或称为桶。然后将n个数据分别放到各个桶中。因为输入数据是均匀独立分布在[0,1]区间上，所以一般不会出现很多数据在同一个桶中。

同一个桶中的元素，采用插入排序算法排序；不同桶的元素，按照桶的下标进行串联。

Python实现

def BucketSort(A):
    n=len(A)
    largest=max(A)
    size=largest/n

    B=[[] for i in range(n)]
    for i in range(n):
        j=int(A[i]/size)
        if j!=n:
            B[j].append(A[i])
        else:
            B[n-1].append(A[i])
    for i in range(n):
        InsertionSort(B[i])

    result=[]
    for i in range(n):
        result=result+B[i]
    return result

def InsertionSort(A):
    for i in range(1,len(A)):
        key=A[i]
        j=i-1
        while j>=0 and A[j]>key:
            A[j+1]=A[j]
        A[j+1]=key

if __name__=='__main__':
    import random
    # A=random.sample(range(10),k=5)
    A=[54,26,93,17,77,31,44,55,20]
    print("Now displaying CountingSort")
    print('Unsorted sequence:\t', A)
    print('Sorted sequence:\t', BucketSort(A))

复杂度分析

$n_i$是表示桶B[i]中元素个数的随机变量，因为插入排序的时间代价为平方阶的，所以桶排序的时间代价是$T(n)=\Theta(n)+ \sum_{i=0}^{n-1}O(n_i^2)$

即使输入数据不服从均匀分布，桶排序依然可以线性时间内完成：只要输入数据满足下列性质：所有桶的大小的平方和与总的元素数呈线性关系。

参考资料

Python Program to Implement Bucket Sort