快速排序(基础版)

面试官:聊聊快速排序

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

排序思想

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

一尘

慧能

快,天下武功,唯快不破

慧能

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

哦?什么是快速排序

一尘

慧能

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

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

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

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

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

相关文章

来自专栏欧阳大哥的轮子

常用的数学函数以及浮点数处理函数

在编程中我们总要进行一些数学运算以及数字处理,尤其是浮点数的运算和处理,这篇文章主要介绍C语言下的数学库。而其他语言中的数学库函数的定义以及最终实现也是通过对C...

1342
来自专栏技术之路

算法时间复杂度

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

1836
来自专栏落影的专栏

程序员进阶之算法练习(三十三)LeetCode专场

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继续Lee...

1101
来自专栏Python小屋

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

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

3215
来自专栏chenjx85的技术专栏

leetcode-39-组合总和(有趣的递归)

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

1162
来自专栏落影的专栏

程序员进阶之算法练习(三十三)LeetCode专场

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继...

781
来自专栏Python专栏

浅尝Python快速排序

1244
来自专栏算法channel

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

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

2867
来自专栏aCloudDeveloper

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

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

7599
来自专栏小樱的经验随笔

HUST 1586 数字排列

1586 - 数字排列 时间限制:1秒 内存限制:128兆 91 次提交 36 次通过 题目描述现有n个k位的数字,你的任务是重新安排数字每一位的位置,使得...

28412

扫码关注云+社区