快速排序(基础版)

面试官:聊聊快速排序

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

排序思想

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

一尘

慧能

快,天下武功,唯快不破

慧能

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

哦?什么是快速排序

一尘

慧能

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

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

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

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

上面两个过程(选元素和调整位置)称为分割(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 条评论
登录 后参与评论

相关文章

来自专栏阮一峰的网络日志

快速排序(Quicksort)的Javascript实现

日本程序员norahiko,写了一个排序算法的动画演示,非常有趣。 这个周末,我就用它当做教材,好好学习了一下各种排序算法。 ? 排序算法(Sorting al...

2765
来自专栏dalaoyang

递归基础思想

1483
来自专栏Python专栏

浅尝Python快速排序

1064
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(06-10打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

842
来自专栏aCloudDeveloper

公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 ...

5749
来自专栏编程之旅

唠唠快速排序算法

每一个从事计算机相关方向工作的同学一定听说过快速排序算法,在面试的准备过程中,快排也一定是一个必须要牢牢掌握的算法。那么今天就来唠唠快速排序算法。

842
来自专栏生信技能树

R语言中的排序,集合运算,reshape,以及merge总结

不想排版,心情也不好,但是这个知识点很重要,尤其是学习R语言的朋友,请仔细看~ 一直以来我都是随便看了点R的编程教程,因为我学了一点点C,所以还算有基础,现在基...

28011
来自专栏Python小屋

Python模拟大整数乘法的小学竖式计算过程

让我们先看个图回顾一下小学学过的计算整数乘法的竖式计算过程 ? 然后再来看如何使用Python来模拟上面的过程,虽然在Python中计算任意大的数字乘法都没有问...

2935
来自专栏技术之路

算法时间复杂度

     算法复杂度分为时间复杂度和空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。      随着计算机硬件和软件的提升,一个算法的执行时间是算...

1796
来自专栏算法channel

直接选择排序到堆排序做的那些改进

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

2777

扫码关注云+社区