跟我学算法（三）——最常用的快速排序

上一节学习的是冒泡排序，时间复杂度是O(N²)，如果我们的计算机每秒运算10亿次，排序1亿个数字，那么最开始我们介绍的桶排序只需要0.1秒，而冒泡排序则需要1千万秒，换算成天也就是115天，这，...

那么有没有什么排序是既省时，又省空间的呢？下面我们就来学习一下快速排序。

现在我们要对6、1、2、7、9、3、4、5、10、8这十个数字进行排序。按照快速排序的思想，先找一个数字作为基准数（这只是个专用名词，不可怕，不可怕...）。为了方便，我们就用第一个数字6作为这个基准数吧。那么下面我们就需要把所有小于6的数字放到6的左边，大于6的数字放到右边。

其实就是在初始的时候，我们的6这个数字在第一位，现在我想把它移动到中间某个位置k，现在就需要寻找这个k，并且已k为分界点，左边的数字都小于6，右边的数字都大于6 。大家相出怎么做了吗？这里提示一下我们的冒泡排序是怎么做的，但是那样交换太累了，大家有没有更好的方式？

快速排序是这样操作的，分别从序列的两端开始看，先是从右往左找一个小于6的数，再从左往右照一个大于6的数，然后交换他们。从左往右的变量就设为i吧，从右往左的变量就设为j。

首先j先从最右往左移动（即j--），这里需要注意一下，因为我们的基准数是第一个数，所以必须先从j开始移动（这里大家想想是为什么），直到j找到一个比6小的数字停下来，然后i开始从左往右找一个比6大的数字停下来，在这里i和j所指的数字交换位置。

在我们这个例子中，结果如下图：

 

交换后的数字序列上图也展示了，即是6、1、2、5、9、3、4、7、10、8 。

这样第一次交换完成，再然后j--继续，找到4比6小，i++也继续，发现9比6大，于是ihej所指的数继续交换，结果即是6、1、2、5、4、3、9、7、10、8 。这时候j还是应该执行j--操作，发现3比6小，但是i++之后发现与j相遇了即i==j，这时候就应该停止了，但是还有一步就是需要交换3和基准数6，然后就完成了一次交换动作。

这次之后，序列变为了3、1、2、5、4、6、9、7、10、8 。此时就已经完成了6前面的数都小于6，6后面的数都大于6这个任务了。最后我们在总结一下，实际上j是为了找小于基准数的数字，i是为了找大于基准数的数字，直到i、j碰头。此时的6其实已经完成了排序，因为他正好前面的数都小于他，后面的数都大于他。

我们接下来只需要再继续分别排序左右两边的序列就行了。

先看左边的序列，3、1、2、5、4，我们以3为基准数，用上面的方法进行排序，大家可以自己先拿出笔来试试。

这里我们还是设i和j，首先j开始做j--操作，一直到2发现2比3小，i开始做i++操作，但是走到2的时候与j碰面了，于是交换2和3完成这次排序，这时候3已经完成了排序。序列为2、1、3、5、4 。

再然后就是分别排序2、1和5、4，这里我们再举例一下2、1，同样设置2为基准数，j--，发现1比2小，i++发现到1时与j相等，此时交换。如果是本来就排好序的，那么j一直从最尾到j==0也没有需要交换的，说明基准数本来就在正确位置上。

就这么下去，我们接着排好了5、4，9、7、10、8，最终就完成了排序。

快速排序是不是也很简单呢？快速排序实际上就是在冒泡排序的基础上改进而来的，冒泡排序每次都只能相邻的两个交换，而冒泡排序是跳跃的，交换的距离很大，因此总的比较和交换次数就少了很多。当然也就提速咯~

但是最坏的情况下还是和冒泡排序一样，时间复杂度还是O(N²)，但是它的平均时间复杂度是O(NlogN)。这种算法思想实际上是一种分治法思想，顾名思义就是分而治之的意思。

快速排序是C. A. R. Hoare（东尼•霍尔，Charles Antony Richard Hoare）在1960年提出来的，后续也有很多改进，如果你对快速排序感兴趣可以去看看东尼•霍尔1962年在Computer Journal发表的论文“Quicksort”以及《算法导论》的第七章。这个人也是在ALGOL X这个语言中发明了case语法，也被我们很多现在很流行的语言使用着呢。

本文原创于本人博客，请访问 http://irfen.me

©原创文章，转载请注明来源： 赵伊凡's Blog
©本文链接地址: 跟我学算法（三）——最常用的快速排序