任何基于决策树的比较排序在最坏情况下都要经过$\Omega(nlgn)$次比较。因此，任何已知的比较排序最多在常数因子上优于归并排序和堆排序。

计数排序

计数排序假设n个输入元素中的每一个都是在0到k之间的一个整数。对每个输入元素x，如果有i个元素小于x,那么x就被放在i+1的位置上。

在计数排序的算法中，输入数组为A[1..n]，那么需要B[1..n]来放置排序结果，C[1..k]来提供临时的存储空间。由此可见，计数排序适合于数值范围相较于元素数目不大的情况，也就是k=O(n)的情况。

def counting_sort():
    for i in A:
        B[i] = B[i]+ 1;  #大小为i的数量

    cur = 0;
    for i in range(0, B.__len__()):
        for j in range(0, B[i]):     #有几个为i的值，就将结果放入C几次
            C[cur] = i;
            cur = cur+1;

基数排序

基数排序对数字的每一位进行排序，排序顺序是由低到高。不采用由高到低的理由是：如果使用由高到低的排序顺序，那么10个容器中的9个必须暂时不管放在一边。这样效率会比较低。

基数排序的代码比较简单…其实是对每一位上使用排序算法，大概是这样的画风：

def radix_sort():
	for i in range(0,d):
		#对第i位使用稳定的排序算法

桶排序

桶排序假设输入数据服从均匀分布，平均情况下时间代价为0(n)。如果有冲突，需要在同一个槽中使用排序算法进行排序。在下面的代码中，quick_sort就是处理冲突时使用的排序。当然，在冲突不多的时候，用插入排序性能应该更好一点。

B = [[] for i in range(10)];
def bucket_sort():
    for i in A:
        B[int(i/10)].append(i);

    for i in range(0, B.__len__()):
        quick_sort(B[i], 0, B[i].__len__()-1);
        for j in range(0, B[i].__len__()):
            print(B[i][j]);



def quick_sort(L, p, r):
    if (p >= r):
        return;  # 只有一个元素,不需要再排序

    q = L[p];  # 取第一个数字为比较变量
    j = p;  # 索引j从第二个数字开始
    for i in range(p + 1, r + 1):
        if (L[i] < q):
            j = j + 1;
            swap(L, i, j);  # j自增，并将边界右边的大值和当前的小值交换位置。
    swap(L, p, j);  # 最后将比较标量和边界的小值交换，整体完成有序(数组1，q，数组2)
    quick_sort(L, p, j - 1);
    quick_sort(L, j + 1, r);


def swap(L, a, b):
    tmp = L[a];
    L[a] = L[b];
    L[b] = tmp;