搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 大师兄编程 > 排序方法之五:快速排序

排序方法之五:快速排序

大师兄编程 2019-11-08
排序方法之五:快速排序

排序方法之快速排序

基于分治的思想,是冒泡排序的改进型。通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

排序方法之五:快速排序


1

算法讲解

设定原始序列{ 6  、1 、 2 、7  、9 、 3  、4 、 5 、10 、 8 }

第一步:将序列第一个元素作为基数,然后定义i、j两个哨兵分别从左边和右边进行嗅探。先从右边j开始向左嗅探。

排序方法之五:快速排序


第二步
:哨兵j从右边依次向左嗅探,直到找到第一个比基数6小的元素然后停下,也就是停留在5的位置。这时候i从左边开始向右嗅探,直到找到第一个比基数大的元素7然后停下,也就是7的位置。这时候就要交换i和j对应的元素7和5。

排序方法之五:快速排序

得到结果:

排序方法之五:快速排序

第三步:哨兵j又开始从右向左嗅探,直到找到下一个比基数小的元素4然后停下,此时哨兵i又开始向右嗅探,直到找到下一个比基数大的元素9然后停下,这时候交换两个元素的位置。

排序方法之五:快速排序

得到结果:

排序方法之五:快速排序

第四步:哨兵j又开始向左嗅探,遇到下一个比基数小的元素3然后停下,哨兵i又向右嗅探。完了,这时候哨兵i和j相遇了,他们就准备私奔,但是私奔之前还有一件事要做,就是把这个元素和基数进行交换。

排序方法之五:快速排序
排序方法之五:快速排序

得到结果:

排序方法之五:快速排序

这时候,第一轮嗅探就算完成了,这个序列也被基数6分为了两个部分,左边都小于等于基数,右边都大于等于基数。但是排序还没完哦,我们继续将原来的序列,以6为分界点拆分成了两个序列,分别用上述方法再次进行排序,依次递归下去,直到序列不能被拆分就结束了哦。



2

代码实现

这里我们换用C语言代码实现一下

排序方法之五:快速排序


怎么样?还不错吧,其实还挺好理解的,相信你一定行的。下面我们分析一下这个算法。


3

算法分析

1、时间复杂度:时间复杂度O(nlogn)

2、空间复杂度:快速排序使用递归,递归使用栈,因此它的空间复杂度为O(logn)。

3、稳定性:快速排序无法保证相等的元素的相对位置不变,因此它是不稳定的排序算法。

今天的快速排序到此就结束啦

或者加私人微信进微信群:bin18382734270

一百分服务,只为你十分满意

排序方法之五:快速排序
排序方法之五:快速排序
排序方法之五:快速排序
排序方法之五:快速排序
排序方法之五:快速排序

我知道你在看


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《排序方法之五:快速排序》的版权归原作者「大师兄编程」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注大师兄编程微信公众号

大师兄编程微信公众号:Feng_Lan_Mu

大师兄编程

手机扫描上方二维码即可关注大师兄编程微信公众号

大师兄编程最新文章

精品公众号随机推荐