算法系列——快速排序

算法系列——快速排序挑选一个基准元素,并让其他比它大的元素移动到数列一边,比它小的元素移动到数列的另一边,从而把数列拆解成了两个部分。

大家好,欢迎来到IT知识分享网。

快速排序的思想

快速排序的核心思想在于分治法。挑选一个基准元素,并让其他比它大的元素移动到数列一边,比它小的元素移动到数列的另一边,从而把数列拆解成了两个部分。然后递归对基准元素两边的元素继续依次排序。

因此快速排序的由3个步骤组成

1.挑选一个基准元素

2.将基准元素安置到准确的位置

3.将基准元素两侧的数重复1,2步骤递归排序

下面针对各个步骤进行分析

挑选基准元素

快速排序的时间复杂度会受到基准元素的影响,在理想的情况的下,每一轮排序后(除却最后一轮),基准元素两侧都应该是非空的,即算法复杂度为O(nlogn)。但是因为无法保证这一点,因此在一定情况下,快速排序的时间复杂度可能退化为O(n^2)。一般情况下直接选择左侧第一个数作为基准元素即可。

算法系列——快速排序

按照基准元素多轮排序(理想情况)

算法系列——快速排序

按照基准元素多轮排序(最差情况)

找到基准元素准确位置

找到基准元素位置,我们常用的有两种方法,挖坑法与指针交换法。

算法系列——快速排序

挖坑法

算法系列——快速排序

指针交换法

可以看到,挖坑法和指针交换法的区别,就在于右侧遍历的时候遇到不符合顺序的元素时的处理方式,挖坑法会即刻调整,指针交换法会留待左侧遇到不符合顺序的元素时进行交换。

为什么要从右侧开始处理

算法系列——快速排序

直接说结论,如果基准元素为左侧第一个,则需要从右侧开始处理。

以上图为例,正序排序,先左侧的话,会到9停下,换到右侧也会到9停下,此时因为左右侧相等,将基准元素6放置到9的位置,此时排序就错乱了。交换完成并不能保证所有左边的值都小于基准数,因此当key设置在左侧时应当从右开始向左查找,如果想先从左往右查找,只需把基准元素设置在右侧即可。

递归转非递归

快速排序使用到了分治理法的思想,对于分治法,我们最常使用的处理方法即递归。但是递归会到栈深度的加深,因此我们可以使用非递归的方式。原理也十分简单,使用堆栈保存递归所想保存的状态即可

代码示例

算法系列——快速排序

指针交换法

算法系列——快速排序

填坑法

算法系列——快速排序

递归与非递归调用

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/49674.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信