喜闻乐见之一(快速排序)


喜闻乐见系列之

quickSort

快排运用还是蛮广的,很多语言内置的排序算法都是这个,效率O(nlogn),其实还有不少也是O(nlogn),合并排序,堆排序神马的。不过合并
需要一个额外的数组,要是样本好大的话,就挺伤的,堆排序的话元素每次移动的范围可能有点大,没有什么局部性,不利于优化。

1. 原理其实很简单

import random

l = [random.randint(1,100) for i in range(100)]
def qsort(L):
    if len(L) <= 1: return L
    return qsort([x for x in L if x < L[0]]) + [L[0]] + qsort([x for x in L if x > L[0]])

print qsort(l)

选一个数当成中位数,比它小的放左边,比它大的放右边,然后对左边和右边同理。对,就是这么简单

2. 万一选的那个数不是最大就是最小的,就不是快排了...
所以这个数是中位数,其实还挺重要滴,不能乱选. Imagine that, 每次选的这个数是都在中间,那如果递归的话,函数栈深度少了不少,PC得少调来调去多少次啊。SO,关键的点就是尽量选出靠中间的那个数。

int partition(void* base, int elemSize, int lo, int hi, int(*cmpfn)(void*, void*))
{
    char* cmp = (char*) base + elemSize * lo;
    int i = lo;
    int j = hi + 1;
    while (true)
    {
    while (cmpfn(cmp, (cmp + elemSize * (--j - lo))) < 0) { if (j == lo) break; }
    while (cmpfn((void *)cmp, (void *)(cmp + elemSize * (++i - lo))) > 0) { if (i == hi) break; }
    if (i >= j) break;
    swap((void*)(cmp + (i - lo) * elemSize), (void*)(cmp + (j - lo) * elemSize), elemSize);
    }
    swap((void*)cmp, (void *)(cmp + (j - lo) * elemSize), elemSize);
    return j;
}

这个partition的思路是,从两边向中间遍历,选出左边大于CMP,右边小于CMP的数,然后交互它们的位置,这个算法交换的次数是最优的。

void quicksort1(void* base, int lo, int hi, int elemSize, int(*cmpfn)(void*, void*))
{
    if (lo >= hi) return;
    int mid = partition(base, elemSize, lo, hi, cmpfn);

    quicksort1(base, lo, mid - 1, elemSize, cmpfn);
    quicksort1(base, mid + 1, hi, elemSize, cmpfn);
}

void quicksort(void* base, int size, int elemSize, int(*cmpfn)(void*, void*))
{
    quicksort1(base, 0, size - 1, elemSize, cmpfn);
}

这段代码C语言实现了泛型的快排

3. 等等,要是有些极端案例,样例中相等的元素特别多,研究一下程序的运行轨迹,感觉废操作是不是有点小多
优化的手段是加一个index变量,当(*cmpfn)(lo, hi) == 0的时候,可以去记录某一段相等元素的边界,然后在递归的时候可以忽略这一段相等的元素,这段代码我就不贴出来了,大家可以自己下来亲自敲一敲。

Summary:
其实快排这个partition可以解决一个求第K个小或者是大的数,可以是O(n)的喔.
然后快排这个程序其实还挺特殊的,大家有木有发现快排划分以后,每一个递归的数据段和其它递归的数据段完全不相关... 所以把partition分下来的一段段抛给多线程去搞,这个对于数据量特别大的,可以快很多很多,现在连手机都8核了,这个算法多线程去加速来搞太适合了

要是有什么地方有错误的,欢迎指正哈!
----------------
PS:今天面试一个HR竟然问我是什么星座的,我勒个ca,我又不是处女座,无语

评论

暂无评论