本文将对快速排序进行深入的分析和介绍。通过学习本文,您将
八卦花絮快速排序是由图灵奖获得者、计算机语言设计大佬C. A. R. Hoare在他26岁时提出的。说起C. A. R. Hoare老爷爷,可能很多人的第一印象就是快速排序,但是快排仅仅是他人生中非常小的成就而已。例如,他在1978年提出的Communicating Sequential Processes(CSP)理论,则深深的影响了并行程序设计,Go语言中的Goroutine就是这种典范。 基本思想快速排序的思想非常简单:对于一个数组S,我们选择一个元素,称为pivot。将数组S中小于等于pivot的元素放在S的左边,大于等于pivot的元素放在S的右边。左右两部分分别记为S1和S2,然后我们递归的按上述方式对S1、S2进行排序。 具体说来,我们维护两个指针,采用两边扫描。从左到右扫描,当遇到一个元素大于等于pivot时,暂停。从右到左扫描,当遇到一个小于等于pivot元素时,暂停。然后交换这两个元素。继续扫描,直到两个指针相遇或者交叉。 从直观上看,每次递归处理的两个子数组S1、S2的大小最好是相等或者接近的,这样所花费的时间最少。 实现细节说起来容易,做起来难了。要想正确实现快速排序非常不容易,很容易犯错。简单的修改就可能导致程序死循环或者结果错误。如果你一度感到很难在几分钟内实现一个正确的快速排序,说明你是正常人。那些五分钟内就能把快速排序写对的,几乎都是背代码。 我在实现以下代码时,就反复调试了十几分钟。而且,我会告诉你曾经JDK的某个版本实现中都存在bug么? 在给出完整代码之前,我们来考虑几个非常重要的问题。 如何选择pivot?至少有几种显而易见的方法: 尝试1:选择数组中的第一个元素。成本低,但是当输入数组已经有序时,将导致O($n^2$)的复杂度。例如S={1,2,3,4,5,6,7,8,9},如果选择第一个元素也就是1作为pivot,那么S1={1}, S2={2,3,4,5,6,7,8,9},两个子数组非常的不平衡。当递归对S2排序时,选择2也就是S2中第一个元素作为pivot排序时,又会将S2分成两个极其不平衡的子数组。经过简单分析可知,此时算法复杂度为O($n^2$)。因此这不是一个理想、健壮的方法。 尝试2:随机选择一个。这种方法一般都能很好work,但是随机子程序可能非常昂贵,这可能拖慢整个程序。 尝试3:取中位数。取中位数可以保证S的两个子数组是等大小的(或者相差1),但是计算中位数可不是一个轻轻松松的活儿,将会严重拖慢算法速度。 尝试4:三数取中。尝试3方法太昂贵,我们可以稍微改变下:取数组第一个元素、最后一个元素、中间元素这三个元素的中位数。 遇到相等的元素怎么办?左右扫描,如果遇到和pivot相等的元素怎么办?是暂停扫描还是继续扫描? 首先,两个方向采取的策略应该是一样的,也就是要么都暂停(然后交换),要么都继续扫描。否则将导致两个子数组不平衡。 其次,为了更好分析这个问题,我们不妨考虑所有元素都相同的情形。如果我们遇到和pivot相等的时候不停止,那么从左到右扫描时,两指针将相遇,此次过程结束。结果呢?什么都没做,却得到了两个大小极其不均衡的数组。算法时间复杂度为O($n^2$)。如果我们选择遇到相等元素时停止扫描,然后交换,那么虽然看上去交换的次数变多了,但是我们将得到大小相等(或者差1)的两个子数组。算法的时间复杂度为O($nlgn$)。 因此,遇到和pivot相等的元素时候我们都暂停扫描,交换元素后继续,直到指针相遇或者交叉。 小数组怎么处理?随着不断的递归,待排序的子数组大小越来越小,所含元素越来越少。当子数组所含元素较少(比如说,20个)时,由于它们已经基本有序,我们改变策略,对它们改用插入排序。这也方便了三数取中策略的实现,否则我们在三数取中的时候还得特殊考虑子数组有0个、1个、2个元素的情形。当子数组多大时我们转换排序方法呢?这个最优值就依赖于体系结构了。为了找到你系统中它的最优值,请多测试!测试!测试! 完整实现
我们把以上实现的快速排序称为YedisSort。 测试结果测试程序已经放到了github上,可以从 这里 下载。 我们pk的对象包括STL中的sort,以及C语言里大名鼎鼎的qsort。 测试结果: 1000W个随机打乱的32位无符号整数 开启O2优化(单位:秒): sort: 1.06 YedisSort: 1.20 qsort: 2.08 未开启O2优化(单位:秒): sort: 3.29 YedisSort: 2.93 qsort: 2.91 1000W个相同的整数 开启O2优化(单位:秒): sort: 0.23 YedisSort: 0.27 qsort: 0.59 未开启O2优化(单位:秒): sort: 2.60 YedisSort: 1.56 qsort: 0.76 什么结论? 没开优化,那么所需时间 qsort < YedisSort < sort 开了优化,那么所需时间 sort < YedisSort < qsort 为什么sort可以这么叼?据说它综合了插入排序、快速排序和堆排序。这让我想起了推荐和广告比赛里,有些队伍利用Ensemble Learning没节操地堆了几百个model。。。 Further Thinking
1,64行的 2,30-46行能否改为:
深入分析这样的case,将会对编写正确的快速排序的困难性有更深的体会,虽然我们已经有循环不变式这个强大的工具。 3,快速排序所需的栈空间是多少?能否进一步优化? 4,YedisSort的时间复杂度是多少?O($n^2$)还是O($nlgn$)?如果是前者,那么,什么情况下是二次的? |
|
来自: codingparty > 《开发》