快速排序的要点、过程与算法图解

2018-10-3010:02:33数据结构与算法Comments9,869 views字数 1899阅读模式

快速排序

快速排序由C.A.R.Hoare在1962年提出,是冒泡排序的一种改进。其基本思想为:通过一趟排序将待排序数据分割成独立的两部分,其中一部分的所有值都比另一部分的所有值都小,然后再对分割的两部分分别进行快速排序,整个过程可以递归进行,最终所有数据变为有序序列。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

排序要点

设待排序数组为a[0],a[1],...a[n-1],快速排序步骤为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

  1. 初始化两个变量i、j,刚开始i=1,j=n-1。
  2. 将第一个元素a[0]作为基准数。
  3. 从i开始向后搜索,找到第一个大于基准数的元素a[i]。
  4. 从j开始向前搜索,找到第一个小于基准数的元素a[j]。
  5. 将a[i]与a[j]互换。
  6. 重复3到5步骤,直到i=j,然后将a[0]与a[j-1]对换。
  7. 序列被基准数分割成两个分区,前面分区全部小于基准数,后面分区全部大于基准数。
  8. 递归对分区子序列进行快速排序,最终完成整个排序工作。

每趟快速排序的核心工作是:选一个元素作为基准数,然后将所有比它小的数都放到它前面,大于它的都放在它后面。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

排序过程

假设我们有如下8个元素,分别为59, 25, 71, 16, 62, 84, 34,45,现在进行快速排序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

初始化变量i=1,j=7,并且将第一个元素a[0]作为基准数,然后开始从i向后寻找第一个大于a[0]的元素,59先与25比较,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

由于25小于59,所以往后移一步继续比较,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

71大于59,找到第一个大于59的元素。接着我们从j开始向前搜索,寻找第一个小于基准数的元素,59与45比较,45小于59,于是找到第一个小于基准数的元素,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

此时对换a[i]与a[j]的值,即71与45对调,发现对调的效果了吗?就是将大的甩后面,小的向前推。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

继续寻找下一个大于基准数的元素,将i向后一步,16小于59,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

i再往后移一步,此时62大于59,找到大于59的元素了。接着j向前寻找第一个小于基准数的元素,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

34小于59,于是找到要找的元素,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

此时对换a[i]与a[j]的值,即62与34对调,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

继续寻找下一个大于基准数的元素,将i向前后一步,84大于59,找到,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

而j向前寻找,发现与i已经重合了,停止继续往前比较,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

直接将重合位置的前一个元素的值与基准数对换,即a[j-1]与a[0]的值对调,也就是34与59对调。至此,完成第一趟快速排序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

接下去准备第二趟快速排序,第一趟执行完后,基准数将序列分成两个分区,而待排序对象就是上一次基准数前面的那些元素,即59前面的元素。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

对于该子序列,初始时i=0,j=3,这一趟基准数a[0]为34。然后开始从i向后寻找第一个大于a[0]的元素,34先与25比较,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

由于25小于34,所以往后移一步继续比较,此时45大于34,找到第一个大于基准数的元素,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

接着j向前寻找第一个小于基准数的元素,16小于34,它即是要找的元素。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

此时对换a[i]与a[j]的值,即45与16对调,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

继续寻找下一个大于基准数的元素,将i向前后一步,发现与j已经重合了,停止继续往后比较,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

直接将重合位置的前一个元素的值与基准数对换,即a[j-1]与a[0]的值对调,也就是34与16对调。至此,完成第二趟快速排序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

接下去准备第三趟快速排序,基准数34将序列又分成两个分区,对其前一分区继续进行处理。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

此时该分区子序列只有16和25两个元素,初始时i=1,j=1,基准数a[0]为16。一开始i和j就重合了,此时的i找到大于基准数的元素,而j没找到小于基准数的元素,所以不对换。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

接下去准备第四趟快速排序,在第一趟执行完后,先处理的是59前面的分区,现在接着处理59后面的分区。这个处理顺序是由递归处理方式决定的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

对于后面分区子序列,初始时i=6,j=7,该子序列的第一个元素作为基准数,即84。然后开始从i向后寻找第一个大于a基准数的元素,84先与62比较,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

由于62小于84,所以往后移一步,此时也到达序列最末尾,此时71小于84,未能找到大于基准数的元素。接着j向前寻找小于基准数的元素,71小于84,找到该元素。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

然后将71与基准数84对换,完成第四趟快速排序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

接下去准备第五趟快速排序,基准数84只有前面一个分区,对该分区子序列继续进行处理。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

此时该分区子序列只有71和62两个元素,初始时i=6,j=6,基准数为71。一开始i和j就重合了,此时i找不到大于基准数的元素,而j找到了小于基准数的元素,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

于是将71和62进行对换,完成第五趟快速排序。至此,整个序列都完成排序工作。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

快速排序的要点、过程与算法图解

作者:超人汪小建
链接:https://juejin.im/post/5bd65581e51d454c410e5df0
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/7579.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/7579.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定