雅乐网

计算机技术、学习成长

计算机 » 算法 » 详解快速排序

详解快速排序

快速排序通常是在实际应用中排序的最好算法,虽然在最坏情况下它的时间复杂度是O(n^2),但是在平均情况下,它的时间复杂度是O(nlogn),并且它的常数因子非常小,因此效率极高。

下面的描述中对数组a中的[lo,hi)进行排序。([lo,hi)表示一个前闭后开的下标范围,包含元素a[lo],…a[hi-1],不包含a[lo],共有hi-lo个元素)

思想

快速排序使用了分治的思想,它的主要步骤如下:

1. 选取一个元素x,并以这个元素为基础,把数组分成左右两个部分,其中左半部分都小于x,右半部分都大于x 。当然,等于x的部分归于左边和右边都可以。

scrn20150314134830

2.递归的快速排序左半部分

3.递归的快速排序右半部分

因为x的位置就是最终排序后正确的位置,所以两次递归后不需要合并结果,左右分别排序好后整个数组自然就是有序的了。

主算法代码

根据上面的步骤,可以很简单的写出快速排序的步骤

调用partition之后,[lo,mid)都小于x,[mid,mid+1)等于x,[mid+1, hi)大于x ,因此只需要递归的排序左右两个部分即可。

当数组中只有1个元素的时候,它就是平凡的有序,这时候需要退出递归,因此需要加上一句来处理递归基。

最终的快速排序函数如下:

划分

快速排序的关键在于划分,也就是上面的partition函数,该函数返回一个mid值,并原地将数组调整为左中右三部分。

scrn20150314140622

 

我们选取a[l0]作为x,尝试把数组分成小于x和大于等于x的两部分。使用lo和hi当做指针,分别从左边和右边遍历数组。

首先我们把a[lo]保存起来,

然后a[lo]就相当于一个空位,这时候我们从最右边出发,由于最右边元素是a[hi-1]所以这里我们先把hi减一。然后在while里面hi向左移动,我们知道右半部分应该大于等于x,因此只要hi>lo并且a[hi] >= x的情况下,我们一直递减hi,直到发现a[hi] < x,那么a[hi]元素应该属于左边才行,这时候我们把a[hi]复制到a[lo]的位置。

我们看这个while循环,跳出的时候如果hi>lo不满足 ,那么跳出后的a[lo]=a[hi]可以正确的移动元素。

如果是因为hi>lo而跳出循环,那么执行的是a[lo]=a[hi]相当于自己等于自己,对数组没有影响。

scrn20150314142156

之后,a[hi]就相当于一个空位了,这时候我们转入左边,在lo < hi的情况下递增lo,直到找到a[lo]大于x,这时候我们把a[lo]移动到a[hi]处

然后我们在转入右边,递减hi 。可以看出右边和左边是交替进行的,我们可以把这两个while写进一个大的while里面。那么这个整体while的条件是什么呢?

在比较和复制的过程中,lo不断前进,hi不断减小,那么当lo<hi不成立的时候就可以停止了

我们看大的while循环,每次循环执行后,lo前面的元素都<x,  hi后面的元素都>=x ,而且a[lo]是一个空位

因此循环终止的时候lo==hi,这时候lo前面的元素小于x 后面的元素都大于等于x,这时候我们需要把最初备份的轴点x移动到a[lo]处就完成了划分。

我们的最终划分算法代码如下:

 划分选取元素的改进

快速排序的效率取决于每次把数组分成两个部分的时候是否平均,如果每次差不多分成一样大小的两个区间,那么递归的二分树就会矮胖矮胖,效率也会变高。

因此一种改进就是随机选取一个元素作为x,而不是每次选取a[lo] 。这种改进只需要在最开始吧a[lo]和选取的x互换位置,就可以仍然按照上面的代码来运行。

性能

首先划分partition的时间复杂度是O(n)。

在最坏情况下,假设每次都划分产生的两部分都有一部分是0,那么会导致时间复杂度达到O(n^2)。

幸运的是,只要两部分的划分是常数比例,即使是99:1 那么产生的递归树的深度也只有logn的级别。

在平均情况下,假设元素出现的概率相同。每次划分为[0,k]和[k+1,n],其中k的各个取值是等概率的。

假设总算法耗时T(n),递归左边耗时 T(k) ,右边耗时T(n-k-1),有

T(n) = O(n) + T(k) + T(n-k-1)

所有的情况下,k可以取值0到n-1 ,并且是等概率的。

scrn20150314150801

n+1是划分过程的时间,右边是递归产生的平均时间

在求和中的T(k)和T(n-k-1)是相等的,因为k=0到n-1的时候,k和n-k-1的范围都是0到n-1 ,因此

scrn20150314151014

scrn20150314152903

可以看到,快速排序在平均情况下时间复杂度仅为O(1.39nlogn)。

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/quick_sort.html

上一篇:

下一篇:

我要评论

验证码*: 9 + 3 =