看完动画你还会不懂 快速排序么

前言

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画来描述常见的数据结构和算法。本系列包括十大排序、堆、队列、树、并查集、图等等大概几十篇。

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。

算法步骤

  1. 从数列中挑出一个元素,称为 “基准”(pivot);
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

来源:https://github.com/hustcc/JS-Sorting-Algorithm

算法演示

image

排序动画过程解释

  1. 首先,操作数列中的所有数字
  2. 在所有数字中选择一个数字作为排序的基准(pivot), pivot 通常是随机选择的,在这里为了演示方便,我们选择最右边的数字作为 pivot
  3. 选取好 pivot 后,在操作数列中选择最左边的数字标记为 左标记 ,最右边的数字标记为 右标记
  4. 将左边的标记向右移动
  5. 当 左标记 达到超过 pivot 的数字时,停止移动
  6. 在这里,8 > 6 ,所以停止移动
  7. 然后将右边的标记向左移动
  8. 当 右标记 达到小于 pivot 的数字时,停止移动
  9. 在这里,4 > 6 ,所以停止移动
  10. 当左右标记停止时,更改标记的数字
  11. 因此,左标记 的作用是找到一个大于 pivot 的数字,右标记 的作用是找到一个小于 pivot 的数字
  12. 通过交换数字,可以在数列的左边收集小于 pivot 的数字集合,右边收集大于 pivot 的数字集合
  13. 交换之后,继续移动 左标记
  14. 在这里,9 > 6 ,所以停止移动
  15. 然后将右边的标记向左移动
  16. 当 右标记 碰撞到 左标记 时也停止移动
  17. 如果左右侧的标记停止时,并且都在同一个位置,将这个数字和 pivot 的数字交换
  18. 这就完成了第一次操作
  19. 小于 6 的都在 6 的左侧,大于 6 的都在 6 的右侧
  20. 然后递归对这分成的两部分都执行同样的操作
  21. 完成 快速排序

代码实现

为了更好的让读者用自己熟悉的编程语言来理解动画,笔者将贴出多种编程语言的参考代码,代码全部来源于网上。

C++代码实现

C++代码实现

Java代码实现

Java代码实现

Python代码实现

Python代码实现

JavaScript代码实现

JavaScript代码实现

如果你是iOS开发者,可以在GitHub上 https://github.com/MisterBooo/Play-With-Sort-OC 获取更直观可调试运行的源码。

欢迎关注获取更多内容:

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Phoenix的Android之旅

说一个小bug

这个bug其实很简单,因为String是不可变内容的,想获得新值,必须重新赋值。正确应该是

1023
来自专栏WD学习记录

Python数据结构与算法笔记(4)

当数据项存储在诸如列表的集合中时,我们说它们具有线性或顺序关系。每个数据项都存储在相对与其他数据项的位置。在Python列表中,这些相对位置是单个项的索引值。由...

1251
来自专栏撸码那些事

C#委托之我见

委托的使用方式很简单,了解一下基本语法就可以开撸了。但是使用委托的真正难题是不知道应用场景,就像习得了一门新功夫,但是却找不到任何施展拳脚的地方。这个难题一直困...

813
来自专栏北京马哥教育

这段代码很Pythonic | 相见恨晚的 itertools 库

1723
来自专栏轮子工厂

8. 一花一世界,while for 循环?

wo这周有点懒啊,这才第 2 篇,个人有点事情,本来预计可以更新……1 篇的,︿( ̄︶ ̄)︿

1122
来自专栏编程

您真的会用switch吗?

C语言的理念,程序员应该知道自己正在干什么,而且保证自己的所作所为是正确的。 switch知多少 各个case和default的顺序可以是任意的,但习惯上总是d...

2107
来自专栏向治洪

迭代器模式

迭代器模式(Iterator): 提供一种方法顺序访问一个聚合对象中的各个元素,而又不暴露其内部的表示。 用途:在软件构建过程中,集合对象内部结构常常变化各异。...

19410
来自专栏斑斓

引入Option优雅地保证健壮性

REA的Ken Scambler在其演讲《2 Year of Real World FP at REA》中,总结了选择函数式编程的三个原因:Modularity...

3615
来自专栏老司机的技术博客

宝宝都能学会的python编程教程16:map和reduce

如果你学习过大数据相关知识一定不会陌生MapReduce。 如果你没有学过大数据,也没关系,本文将带你了解python的map和reduce函数。 map()...

3715
来自专栏CodingBlock

Java数据结构和算法总结-冒泡排序、选择排序、插入排序算法分析

前言:排序在算法中的地位自然不必多说,在许多工作中都用到了排序,就像学生成绩统计名次、商城商品销量排名、新闻的搜索热度排名等等。也正因为排序的应用范围如此之广...

2779

扫码关注云+社区

领取腾讯云代金券