算法之旅 | 快速排序法

HTML5学堂-码匠:前几期“算法之旅”跟大家分享了冒泡排序法和选择排序法,它们都属于时间复杂度为O(n^2)的“慢”排序。今天跟大家分享多种排序算法里使用较广泛,速度快的排序算法 —— 快速排序法 [ 平均时间复杂度为O (n logn) ]。

Tips 1:关于“算法”及“排序”的基础知识,在此前“选择排序法”中已详细讲解,可点击文后的相关文章链接查看,在此不再赘述。

Tips 2:如果无特殊说明,本文的快速排序是从小到大的排序。

快速排序法的原理

快速排序是一种划分交换排序,它采用分治的策略,通常称其为分治法。

分治法

基本思想:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解决这些子问题,然后将这些子问题的结果组合成原问题的结果。

基本原理

从序列中任选一个数作为“基准”;

所有小于“基准”的数,都挪到“基准”的左边;所有大于等于“基准”的数,都挪到“基准”的右边;

在这次移动结束之后,该“基准”就处于两个序列的中间位置,不再参与后续的排序;

针对“基准”左边和右边的两个子序列,不断重复上述步骤,直到所有子序列只剩下一个数为止。

原理图解

现有一个序列为 [8, 4, 7, 2, 0, 3, 1],如下演示快速排序法如何对其进行排序。

实现快速排序的步骤分解

选择“基准”,并将其从原始数组分离

先获取基准的索引值,再使用splice数组方法取出基准值。

Tips:该实例中, 基准的索引值 = parseInt(序列长度 / 2)

Tips:splice方法会改变原始数组。例如,arr = [1, 2, 3]; 基准索引值为1,基准值为2,原始数组变为arr = [1, 3];

遍历序列,拆分序列

与“基准”比较大小,并拆分为两个子序列

小于“基准”的数存储于leftArr数组当中,大于等于“基准”的数存储于rightArr数组当中

Tips:当然,也可以将 小于等于“基准”的数存于leftArr,大于“基准”的数存于rightArr

由于要遍历序列,将每一个数与“基准”进行大小比较,所以,需要借助for语句来实现

递归调用,遍历子序列并组合子序列的结果

定义一个函数,形参用于接收数组

function quickSort(arr) { };

实现递归调用遍历子序列,用concat数组方法组合子序列的结果

判断子序列的长度

递归调用的过程中,子序列的长度等于1时,则停止递归调用,返回当前数组。

快速排序法完整代码

快速排序法的效率

时间复杂度

最坏情况:每一次选取的“基准”都是序列中最小的数/最大的数,这种情况与冒泡排序法类似(每一次只能确定一个数[基准数]的顺序),时间复杂度为O(n^2)

最好情况:每一次选取的“基准”都是序列中最中间的一个数(是中位数,而不是位置上的中间),那么每次都把当前序列划分成了长度相等的两个子序列。这时候,第一次就有n/2、n/2两个子序列,第二次就有n/4、n/4、n/4、n/4四个子序列,依此类推,n个数一共需要logn次才能排序完成(2^x=n,x=logn),然后每次都是n的复杂度,时间复杂度为O(n logn)

空间复杂度

最坏情况:需要进行n‐1 次递归调用,其空间复杂度为 O(n)

最好情况:需要logn次递归调用,其空间复杂度为O(logn)

算法的稳定性

快速排序是一种不稳定排序算法

例如:现有序列为[1, 0, 1, 3],“基准”数字选择为第二个1

在第一轮比较之后,变成了[0, 1, 1, 3],左序列为[0],右序列为[1, 3](右序列的1是此前的第一个1)

不难发现,原序列的两个1的先后顺序被破坏了,改变了先后顺序,自然就是“不稳定”的排序算法了

关于O

在此前的“冒泡排序法”一文当中,我们详细讲解过O是什么,在此就不多说了,直接上图吧

生活艰辛,代码不易,但,不要忘记微笑!

版权声明:该图来自“【美】莉兹·克里莫 (author)”的书籍《你今天真好看》

原文发布于微信公众号 - HTML5学堂(h5course-com)

原文发表时间:2017-09-20

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏杨建荣的学习笔记

重温快速排序(r4笔记第73天)

说起排序,总是会想起大名鼎鼎的快速排序,等自己再次翻开快速排序时,感觉是很陌生的,从这个对比也能看出自己确实是已经忘记了曾经重要的日子。 快速排序使用了分治思想...

36470
来自专栏PPV课数据科学社区

【学习】视觉直观感受 7 种常用排序算法

10月14日发布《统计世界的十大算法》后,很多朋友在后台询问,哪里有“视觉直观感受 7 种常用排序算法”,今天分享给大家,感谢todayx.org。 1. 快速...

32450
来自专栏Crossin的编程教室

【Python 第73课】reduce 函数

上次说了 Python 中一个比较有意思的内置函数 map,今天再来介绍另一个类似的函数:reduce map 可以看作是把一个序列根据某种规则,映射到另一个序...

29160
来自专栏轮子工厂

八大排序算法稳定性分析,原来稳定性是这个意思...

2、在一趟选择中,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了;

25860
来自专栏程序员叨叨叨

7.4 输入\输出修辞符(in\out\inout)

参数传递是指:函数调用实参值初始化函数形参的过程。在 C\C++中,根据形参值的改变是否会导致实参值的改变,参数传递分为“值传递(pass-by-value) ...

11710
来自专栏用户画像

排序算法 归纳总结

一、直接插入排序、冒泡排序和简单选择排序是最基本的排序方法,它们主要用于元素个数n(n<10000)不是很大的情形。

8920
来自专栏蓝天

常见指针定义解读

最近做的C/C++技术面试比较多,发现了一些共同的问题,对于如下所示的指针认识,多数面试者都答错了,作为过来人,这种情况还可以理解的,放在一起确实有些复杂。 ...

5310
来自专栏java一日一条

面试中的 10 大排序算法总结

查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只...

21430
来自专栏趣谈编程

希尔排序

21360
来自专栏人工智能LeadAI

排序算法对比、总结(Python代码)

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

41580

扫码关注云+社区

领取腾讯云代金券