专栏首页码海图文详解什么是快速排序

图文详解什么是快速排序

排序的重要性在第2章中已经说明。要高效地搜索数据集,比如采用第1章中介绍的二分搜索,数据集必须是有序的。就像大城市的电话号码簿,如果没有按照字母顺序排序,想象一下你该如何找一个需要的号码。实际生活中的大多数情况如同上述例子,得处理数百万的对象。因此排序算法的效率非常重要,换句话说,即使数据集很大,我们也需要能在相对短的时间内进行排序。对同一个数据集,不同的算法可能差别很大。

本章将介绍两种排序算法。它们看上去很不直观,但当要排序的对象数量很大时,它们需要的运行时间与第2章中介绍的插入排序相比会缩短很多。

为了讨论简单,我们假设待排序的是号码卡片。不过就像插入排序一样,这样的算法并非只能处理数字,对于按照字母顺序给书名排序的问题同样有效,甚至可以推广到更一般的情况,只要处理对象能够按照某种意义上的“尺寸”或“价值”比较大小,同样可以使用这里介绍的算法。执行这些算法也未必非得计算机不可。例如,你可以按照算法给轻重不等的包裹排序,每次基本操作是用天平比较两个包裹。我本人通常使用算法1按照姓名的字母顺序给学生的考试排序。

为此,我们首先用自然语言描述算法,而不用标准程序设计语言或者伪代码表示的程序。

3.1 算法

简单地说,设想你的老师给你送来一叠卡片,上面写有数字。你要按照数字从小到大给卡片排好序再交给老师。你可以按照如下的方法做:

算法11.如果总共只有1张卡片,直接交给老师。否则:2.将所有卡片分为数量相等的两部分,将每部分交给一个助手并要求助手按照递归的方式给各部分排序,即完全按照这里描述的算法排序。3.等两个助手都上交了各自完成排序的卡片部分,从头到尾遍历这两部分卡片,并按照“拉链闭合”的原理将这两部分合并为完全排好序的一叠卡片。4.将这叠卡片上交。

图3-1显示了算法的执行过程。

算法2采用完全不同的方式解决同样的问题:

算法2

1.如果总共只有1张卡片,直接交给老师。否则:2.取出第1张卡片。遍历所有其他卡片并将它们分为两部分,一部分是数字不大于第1张卡片上数字的那些卡片(称为Stack 1),另一部分则是数字大于第一张卡片上数字的那些卡片(称为Stack 2)。3.如果每一部分至少有一张卡片,将它们分别交给两个助手,要求各自以递归的方式排序,即完全按照本算法描述的方式执行。4.等两个助手上交了各自的结果后,先将已排好序的Stack1放在最下面,接着放上开始取出的那张卡片,然后再将排好序的Stack 2放上去。将一整叠卡片上交,自底向上一定是数字从小到大排好序的。

图3-2显示了算法的执行过程。

3.2 两个算法的详细解释

算法1称为合并排序(mergeSort)。早在计算机科学尚未作为独立学科出现时,著名的匈牙利数学家冯·诺依曼(1903—1957)就已经发明了这个算法。当时它是在机械计算装置上使用的。

算法2称为快速排序(quickSort)。它是在1962年由著名的英国计算机科学家C. A. R.霍尔提出的。

前面我们说过这些算法不一定非得由计算机执行。你不妨试试“手动”执行这些算法,并自己充当“助手”的角色,这样就能更好地理解算法了。

所有高级程序设计语言(诸如C、C++、Java等)都允许程序调用其自身,以完全相同的方式解决规模较小的子问题。这种方式称为递归,在计算机科学中起着重要的作用。例如,你要用合并排序处理含16个元素的序列,两个助手各自领取的任务是给含8个元素的子序列排序。而他们再调用各自的助手,让每人给含4个元素的子序列排序,依次类推。形如图3-3的图在计算机科学中称为“树”,它描述了合并排序算法对16个元素的序列排序的整个过程。

当子问题足够小,可以直接给出解的时候递归便终止。在上述算法中就是当序列长度为1时,这时什么也不必做,直接返回结果。在两个算法的描述中都考虑了递归终止条件。

综上所述,这里的算法采用的方法是:划分子问题,分别递归求解,然后再将子问题的解合并为原问题的解。计算机科学中称这种策略为“分治法”。分治法不仅用于排序,也在大量其他完全不同的问题上得到成功应用。

3.3 排序算法的实验比较

有人会问,排序这么简单的问题,为什么要用那么奇怪的算法。为了解释这个问题,我们将上述两种算法以及第2章中的插入排序均编为程序在计算机上运行,采用长度不等的序列作为输入。图3-4显示了执行结果。很显然,合并排序比插入排序快得多,而快速排序也明显快于合并排序。

在半秒(500ms)时间内,插入排序最多处理8000个对象,而合并排序能处理的对象数多20倍。快速排序则比合并排序快4倍。

3.4 确定算法的理论运行时间

正如第2章中讨论的,我们能用数学方法确定对n个对象排序所需要的算法运行时间,不必将算法编程后去度量计算机上的运行时间。数学方法表明插入排序等简单排序算法运行时间与n2成正比。

现在我们对合并排序进行类似的运行时间的理论估计(又称为运行时间分析)。

首先考虑算法第3步,即合并两个已排序长度为n/2的子序列需要执行多少次比较。合并过程首先比较每个子序列最下面的两张卡片,然后将其中小的一张放入新的合并序列中。对两个子序列中余下的卡片按照同样过程处理。每一步均比较两张卡片并将较小的那张放入合并序列中。由于合并序列最终会含n张卡片,所以比较次数不会超过n(严格地说,最多n-1次)。

考虑整个算法的递归结构,我们再看看图3-3中的树。

在顶端老师要处理16张卡片。他交给两个助手每人8张卡片;而助手们又交给他们各自的助手每人4张卡片,以此类推。第3步中顶端的老师必须将两个8张卡片(一般来说是n/2张)合并为一叠,这样就完成了整个16张卡片(n张)的排序。我们前面说过这最多用16(n)次比较。而两个助手在下一层各自合并n/2张卡片,因此每人最多进行n/2次比较,加起来也是n次。类似地,第3层中的4个助手每人要合并n/4张卡片,总共也最多执行n次比较操作。

因此在递归树的每一层最多需要n次比较。剩下的问题就是计算共有多少层了。图中显示当n = 16时递归树有4层。递归树从上往下看,很容易看出每往下一层,子序列的长度会由上一层的n缩小为n/2;再往下,则进一步缩小为n/4,n/8,等等。总之,每往下一层,子序列长度减半,直到长度为1时到达树的底层。因此树的层数也就是n每次减半直到1所能够减半的次数。第1章中我们已经知道这就是以2为底的n的对数log2n。由于每层最多进行n次比较,所以对长度为n的序列做合并排序,最多需要执行n log2(n)次比较。

考虑得简单些,可以假设分析时遇到的n每次除以2直到1为止总能整除。换句话说,n是2的整次幂,也就是1,2,4,8,16,…。如果n的取值并非2的整次幂,分析会稍微复杂一些。原理还是一样的,结果是最多执行n ?log2(n)?次比较。这里?log2(n)?表示log2n向上取整,也就是不小于log2n的最小整数。

上面我们仅仅估计比较操作的次数。将此数乘以执行算法的计算机做一次比较的时间就得到比较操作的总时间。但这还不是总的运行时间,因为除了比较,计算机还得做别的操作,例如存取对象的时间、组织递归的时间等。尽管如此,分析可知总的运行时间和比较操作时间是成正比的。因此,我们通过分析至少可以知道合并排序算法的运行时间与n log2(n)成正比。

以上分析解释了为什么前面的实验反映出合并排序优于插入排序。第2章中得到的结果告诉我们,插入排序的比较次数是n(n-1)/2,当n增大时,这个函数的值增长速度快于n log2(n)。

至于快速排序,情况就更复杂了。可以证明,对某些输入(比如一个已经从小到大排好的序列),快速排序执行时间会很长,与n2成正比。如果你“手动”试过一些例子,可能也会得到类似的印象。只有当输入完全排好了序,而算法选择用来分割序列的元素x(所谓的支点(pivot))恰好是第一个或最后一个元素时才会发生这样“最坏”情况。假如算法从整个序列中随机地选择支点x,算法执行很慢的概率会很小。快速排序平均运行时间也与 n log2(n)成正比。从前面的实验结果可以看出,n log2(n)前面的常数因子明显优于合并排序。在实际应用中,快速排序确实是最快的排序算法,这和前面的实验结果一致。

3.5 Java语言实现

3.1节中已明确定义了算法,也给出了清楚的解释。不过熟悉Java语言的读者可能对技术细节有兴趣,本节给出算法的实现。其实Java语言中提供了这两个算法,可以直接使用。合并排序在类Collections中,用的名是Collections.sort;快速排序在类Arrays中,用的名是Arrays.sort。这些方法不仅可用于数,也能用于任何可以进行两两比较操作的对象。

不过以下给出的是我们自己编写的处理整数的程序,比较容易理解。3.3节实验中用的也是这些程序。每次调用这些方法总是用在数组A的一部分上,边界作为参数。

我们先看合并排序。首先列出的是将两个已排序的序列合并为一个有序序列的方法:

合并排序本身也很容易写为Java中的一个方法:

这段程序还可以改进以运行得更快:不是仅对数组A应用递归,而是让递归交替地用于A和B,就可以避免将数组B存入数组A。这里不再详细讨论了。

相比合并排序,快速排序还有个优点,它不需要辅助数组B,只在输入的数组A上操作。分割序列(算法第2步)是通过“指针变量”i来实现的。开始时i指向待排序区间的起始位置,一旦发现一个大于支点的A[i](这说明A[i]不该属于左侧的子序列),i就不再移动;此时从待排序区间右端开始的变量j向左移动,一旦发现A[j]小于支点j便停止。当两个指针都停止时,交换A[i]和A[j]。这样的过程一直持续到两个指针相遇。

本文分享自微信公众号 - 码海(seaofcode),作者:kunge

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-01

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 巧用 Trie 树实现搜索引擎关键词提示功能

    我们几乎每天都在用搜索引擎搜索信息,相信大家肯定有注意过这样一个细节:当输入某个字符的时候,搜索引框底下会出现多个推荐词,如下,输入「python」后,底下会出...

    kunge
  • 垃圾回收-实战篇

    上文 GC 理论颇受大家好评,学习了之后,相信大家对 GC 的工作原理有了比较深刻的认识,这一篇我们继续趁热打铁,来学习下 GC 的实战内容,主要包括以下几点

    kunge
  • 优雅解决 SpringBoot 工程中多环境下 application.properties 的维护问题

    我们知道 SpringBoot 有一个全局的配置文件 application.properties, 可以把工程里用到的占位符,第三方库的配置项如 dubbo ...

    kunge
  • 朴素贝叶斯分类器的应用

    生活中很多场合需要用到分类,比如新闻分类、病人分类等等。 本文介绍朴素贝叶斯分类器(Naive Bayes classifier),它是一种简单有效的常用分类算...

    ruanyf
  • 朴素贝叶斯分类器的应用

    本文介绍朴素贝叶斯分类器(Naive Bayes classifier),它是一种简单有效的常用分类算法。

    bear_fish
  • 算法与数据结构(十三) 冒泡排序、插入排序、希尔排序、选择排序(Swift3.0版)

    本篇博客中的代码实现依然采用Swift3.0来实现。在前几篇博客连续的介绍了关于查找的相关内容, 大约包括线性数据结构的顺序查找、折半查找、插值查找、Fibon...

    lizelu
  • 技术解析|如何绘制密度分布图

    在前几天对数据分析师与算法工程师进行岗位对比分析的文章中,我们使用了密度分布图和箱线图对薪资水平与学历对薪资的影响进行了分析,那么早起就对这两种图形的绘制方法进...

    刘早起
  • 读懂三向快速排序

    快速排序的缺点 想象一下如果按照生日日期对员工进行排序,排序过程的子数组中肯定存在大量重复的子数组,我们不应该对子数组再进行排序。

    用户2436820
  • composer系列之介绍及安装

    Composer 是 PHP5.3以上 的一个依赖管理工具。它允许你声明项目所依赖的代码库,它会在你的项目中为你安装他们。Composer 不是一个包管理器。是...

    申霖
  • Java程序设计(Java9版):第4章 简单复合类型

    第4章 简单复合类型 4.1 数组 在C语言中,数据类型除了基本数据类型之外,还存在着大量复合数据类型。数组就是一类最简单且非常重要的复合数据类型,数组是具有相...

    程裕强

扫码关注云+社区

领取腾讯云代金券