喜闻乐见之一(快速排序)
文章目录
喜闻乐见系列之
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,我又不是处女座,无语
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论