线性时间排序
@ Shen Jianan · Wednesday, Sep 23, 2015 · 2 minute read · Update at Sep 23, 2015

任何基于决策树的比较排序在最坏情况下都要经过$\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;

About Me

2018.02至今 杭州嘉云数据 算法引擎

2017.6-2017.12 菜⻦网络-⼈工智能部-算法引擎

2016.09-2018.06 南京大学研究生

2015.07-2015.09 阿里巴巴-ICBU-实习

2012.09-2016.06 南京大学本科