快速排序(基础版)

面试官:聊聊快速排序

快速排序,顾名思义,是一种排序速度非常快的排序方法,该算法之所以非常快,是因为高度优化的内部循环,该算法在实际应用中非常广泛。今天我们聊聊快速排序

排序思想

师傅,我听说山下的李公子武术高超,战无不胜,你知道他制胜的秘诀吗

一尘

慧能

快,天下武功,唯快不破

慧能

算法中也常常将速度列为非常重要的一个指标,排序算法中的快速排序也是因为它的快而出名

哦?什么是快速排序

一尘

慧能

快速排序是一种采用分治思想,在实践中通常运行较快一种排序算法,它的思路如下

对于一个无序数组(排序前先将数组随机打乱)

首先,任意选取一个元素(这里选择数组第一个元素),该元素称为中轴元素

然后将大于或者等于中轴元素的元素放在右边,小于或者等于中轴元素的元素放在左边

上面两个过程(选元素和调整位置)称为分割(partition)

然后对左右两个子数组分别按照同样的方法进行分割操作(递归进行)

一直递归分割到子数组只有一个或零个元素为止,此时整个数组有序

子数组是相对而言的

那这个分割操作是怎么进行的呢?

一尘

慧能

分割操作是快速排序的核心,有许多版本,今天给你先说一种常见的

首先,用两个变量 i 和 j 从数组两边开始向中间扫描,i 向右走,j 往左走

i 初始化为第一个元素的下标,j 初始化为最后一个元素的下标加 1

i 往右走,直到遇见比中轴元素大的(或等于)元素停止移动,j 向左走,直到遇到比中轴元素小的(或等于)的元素停止移动

此时,如果 i < j 则交换 i、j 所指向的元素

上图或等于是因为 i 指向的元素或 j 指向的元素可能与中轴元素相等

然后继续向右向左走,直到 i >= j 整个扫描停止

此时 i 对应元素的左边(不包含arr[i])必定小于或等于5,j 对应元素的右边(不包含arr[j])必定大于或等于5

交换中轴元素 5 与 arr[j]

分割完成

排序代码

哦,原来快排是这样的,终于对快排不陌生了

一尘

慧能

快排非常重要,写写快排代码练练手吧

这个...,一尘仔细想了一下,其实也不那么难

对数组arr[low...high]进行快速排序

首先进行分割操作,返回中轴元素下标 j,然后对左数组arr[low...j-1] 和 右数组arr[j+1...high]分别递归进行排序

什么时候递归终止?当然是数组大小为小于等于1(0或1)时

一尘很快写出了quickSort的代码

然后就是分割操作了,把上面的分割过程实现一下

i == high 和 j == low 这两个条件防止i、j 越界

一尘

一尘解释道

时间复杂度

慧能

看来编码能力提高了,那你分析一下时间复杂度吧

这个。。。,我试试

一尘

最坏情况

对于规模为N的数组

如果数组有序的话,此时是最坏情况,因为每次递归右子数组规模只比原数组减一,这样递归次数就会很多

每次分割后,数组都会被划分一个大小为0的子数组和原数组大小减一的子数组

设规模为排序规模为N的数组所花费的时间为T(N)

那么T(N)应该等于分割时所花的时间加上左右子数组所花的时间,而分割时会遍历整个数组,所花的时间为O(N)

则可以得到T(N)=T(0)+T(N-1)+O(N)

处理数组大小为0或1所花费的时间为:

T(0) = T(1) = 1

现在只需要算出T(N)即可

排序前先将数组随机打乱就是防止输入为有序数组而导致排序效率低下,随机打乱将这种可能性(有序)降为极低

最好情况

最好情况就是每次选到一个中轴元素刚好位于中间,此时两个子数组刚好是原数组的一半,那么

T(N)= 2*T(N/2)+O(N)

logN个等式推导请看:归并排序

平均情况

平均时间复杂度分析比较困难,分割操作后中轴元素会落在哪里(排序好的位置)?会落在数组的任意位置。假设是等概率落在了数组的任意位置

此时时间复杂度就是将所有可能情况加起来除以N

由数学归纳法可得:

T(N)=O(NlogN)

具体证明过程就不在此证明了,感兴趣的伙伴可参考《数据结构与算法分析》一书或其他资料

慧能

恩恩,不错

师傅,我看快排时间复杂度也是O(nlogn),并且最坏情况下可能为O(n^2),为什么说它块呢?

一尘

慧能

快排之所以块,就是因为它高度优化的内部循环(分割),它既不像归并那样需要辅助数组来回复制元素,也不像堆排序无法利用缓存并且有许多无用的比较,并且最坏情况可以采用一些方法避免

哦,原来这样

一尘

关于时间复杂度可看:

算法分析神器—时间复杂度

稳定性

慧能

最后一个问题:稳定性

不是稳定的,因为在整个扫描结束时,中轴元素与arr[j]发生交换的时候,可能破坏稳定性

一尘

慧能

看来对快排基本的思路理解的不错

哦,好的

一尘

慧能

走,为师带你去学学李公子的武功

原文发布于微信公众号 - 趣谈编程(gh_51e791ad9174)

原文发表时间:2018-03-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Leetcode名企之路

【Leetcode】81. 搜索旋转排序数组 II

( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

532
来自专栏老马说编程

(47) 堆和PriorityQueue的应用 / 计算机程序的思维逻辑

45节介绍了堆的概念和算法,上节介绍了Java中堆的实现类PriorityQueue,PriorityQueue除了用作优先级队列,还可以用来解决一些别的问题,...

17710
来自专栏算法channel

1800字普林斯顿大学课程浓缩笔记:程序员必知的算法之查找和排序算法

老生常谈,偶尔遇到阐述这两类问题相关的极好素材,它们结合示意图,言简意赅,清晰明了。故分享出来。

540
来自专栏算法channel

程序员必看:实现栈有这两种策略,有完整分析和代码实现

这两篇中分别总结了程序的时间性能度量指标,典型的时间复杂度类型,Java中类型的空间消耗的量化情况。后一篇考虑计算机中最重要的基础算法查找和排序算法,这篇可以说...

870
来自专栏企鹅号快讯

Python算法分享系列-查找,排序,递归

iTesting,爱测试,爱分享 沉寂了一段时间,继续学习。 算法这个系列我想分享很久了,奈何本身对算法不是特别了解,又找不到合适的载体来分享。 最近看了本有趣...

3936
来自专栏灯塔大数据

每周学点大数据 | No.8基础数据结构之线性表

No.8期 基础数据结构之线性表 Mr. 王:为了以后的知识描述方便,这里简单介绍一下数据结构的概念。数据结构是一个广泛存在于计算机科学中的概念。曾经有一位计...

33011
来自专栏余林丰

1.比较排序之冒泡排序

  冒泡排序可以说是在排序算法中最为入门级别的算法之一了。因为其简单易于理解,常在课堂中作为排序的入门算法。   冒泡排序见名生意,其排序过程如同水里的泡一般由...

1706
来自专栏Bingo的深度学习杂货店

从M走到N最少步数

假设一个人站在 X 轴的正半轴上,起始点在 M 点(0 <= M <= 100000),他每次可以向左走一步,向右走一步,或者走到所在坐标乘以2的位置,最终来到...

442
来自专栏PHP技术

PHP实现四种基本排序算法

许多人都说算法是程序的核心,算法的好坏决定了程序的质量。作为一个初级phper,虽然很少接触到算法方面的东西。但是对于基本的排序算法还是应该掌握的,它是程序开发...

34912
来自专栏林德熙的博客

不使用数据结构反转栈

昨天有人问我一道题,我有一个栈,我不使用其他数据结构,不使用另一个栈,把这个栈里所有数据反转。

411

扫码关注云+社区