看图轻松理解数据结构与算法系列(快速排序)

作者:超人汪小建(seaboat)

出处:https://blog.csdn.net/wangyangzhizhou/column/info/25184/2


快速排序

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

排序要点

设待排序数组为a[0],a[1],…a[n-1],快速排序步骤为:

  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. 递归对分区子序列进行快速排序,最终完成整个排序工作。

每趟快速排序的核心工作是:选一个元素作为基准数,然后将所有比它小的数都放到它前面,大于它的都放在它后面。

排序过程

假设我们有如下8个元素,分别为59, 25, 71, 16, 62, 84, 34,45,现在进行快速排序。

image

初始化变量i=1,j=7,并且将第一个元素a[0]作为基准数,然后开始从i向后寻找第一个大于a[0]的元素,59先与25比较,

image

由于25小于59,所以往后移一步继续比较,

image

71大于59,找到第一个大于59的元素。接着我们从j开始向前搜索,寻找第一个小于基准数的元素,59与45比较,45小于59,于是找到第一个小于基准数的元素,

image

此时对换a[i]与a[j]的值,即71与45对调,发现对调的效果了吗?就是将大的甩后面,小的向前推。

image

继续寻找下一个大于基准数的元素,将i向后一步,16小于59,

image

i再往后移一步,此时62大于59,找到大于59的元素了。接着j向前寻找第一个小于基准数的元素,

image

34小于59,于是找到要找的元素,

image

此时对换a[i]与a[j]的值,即62与34对调,

image

继续寻找下一个大于基准数的元素,将i向前后一步,84大于59,找到,

image

而j向前寻找,发现与i已经重合了,停止继续往前比较,

image

直接将重合位置的前一个元素的值与基准数对换,即a[j-1]与a[0]的值对调,也就是34与59对调。至此,完成第一趟快速排序。

image

接下去准备第二趟快速排序,第一趟执行完后,基准数将序列分成两个分区,而待排序对象就是上一次基准数前面的那些元素,即59前面的元素。

对于该子序列,初始时i=0,j=3,这一趟基准数a[0]为34。然后开始从i向后寻找第一个大于a[0]的元素,34先与25比较,

image

由于25小于34,所以往后移一步继续比较,此时45大于34,找到第一个大于基准数的元素,

image

接着j向前寻找第一个小于基准数的元素,16小于34,它即是要找的元素。

image

此时对换a[i]与a[j]的值,即45与16对调,

image

继续寻找下一个大于基准数的元素,将i向前后一步,发现与j已经重合了,停止继续往后比较,

image

直接将重合位置的前一个元素的值与基准数对换,即a[j-1]与a[0]的值对调,也就是34与16对调。至此,完成第二趟快速排序。

image

接下去准备第三趟快速排序,基准数34将序列又分成两个分区,对其前一分区继续进行处理。

此时该分区子序列只有16和25两个元素,初始时i=1,j=1,基准数a[0]为16。一开始i和j就重合了,此时的i找到大于基准数的元素,而j没找到小于基准数的元素,所以不对换。

image

接下去准备第四趟快速排序,在第一趟执行完后,先处理的是59前面的分区,现在接着处理59后面的分区。这个处理顺序是由递归处理方式决定的。

对于后面分区子序列,初始时i=6,j=7,该子序列的第一个元素作为基准数,即84。然后开始从i向后寻找第一个大于a基准数的元素,84先与62比较,

image

由于62小于84,所以往后移一步,此时也到达序列最末尾,此时71小于84,未能找到大于基准数的元素。接着j向前寻找小于基准数的元素,71小于84,找到该元素。

image

然后将71与基准数84对换,完成第四趟快速排序。

image

接下去准备第五趟快速排序,基准数84只有前面一个分区,对该分区子序列继续进行处理。

此时该分区子序列只有71和62两个元素,初始时i=6,j=6,基准数为71。一开始i和j就重合了,此时i找不到大于基准数的元素,而j找到了小于基准数的元素,

image

于是将71和62进行对换,完成第五趟快速排序。至此,整个序列都完成排序工作。

image

赞(1) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 看图轻松理解数据结构与算法系列(快速排序)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏