前言
继续我的填坑旅程,上次说到《排序算法系列之(二)——冒泡排序名字最为形象的一个》2017-09-16 10:42:07,又过了半年多,终于再一次鼓起勇气决定聊一聊快速排序的思路,不过与冒泡排序不同的是,这个快速排序的名字似乎和算法的思路没有什么关系,这个名字太抽象了,起这个名字可能当初仅仅是因为它比别的排序快一点。咳咳!
抽象的名字不利于我们对于算法思路的理解,或许这就是我为什么当初认为快速排序是最难理解的排序算法,也可能是当初还没接触过堆排序、希尔排序等这些另类的排序吧!毕竟工作5年之后再来看这个快速排序,思路也是很清晰的,忽然发现它当初那份神秘的气息消散了许多。
快速排序
我们今天同样略过各种复杂度,直奔主题——快速排序,既然它的名字不是说算法思路,那就是说性质了,通俗点说就是在一般情况下它比选择排序、冒泡排序要快,先不用关心它为什么快,我们先来模拟一个最简单的快速排序。
快速排序的核心思想是分治、递归,将原本问题的规模不断缩小,递归求解,这类算法往往代码很简单,但是理解起来难度大一点,说一下总体思路,我们先来举个例子。假设将N个数从小到大排序,首先是在等待排序的数组N中随便选一个数M,为了简单我们选择第一个,然后遍历待排数组,把比M小的数放到M的左边,把比M大的数放到M的右边,一次遍历结束M左边有m1个数,右边有m2个数(m1+m2+1=N),然后就形成了两个待排数组N1和N2,对于每个待排数组重复上述操作,直到待排数组缩小到一个数字,则待排数据排序完毕,整个数组变为有序。
因为这个排序比较抽象,所以前面的橘子、苹果的例子很难解释清楚,但是我们可以用标了号的橙子来理解,是不是感觉橙子伟大了一点,为什么橙子可以,因为早上刚刚吃过橙子,嗯!就是这么任性!假设桌上摆着一排橙子,他们的重量分别是6, 2, 7, 3, 8, 9,什么?你问我重量单位是什么,那就是斤吧,谁叫这些橙子变异了呢,大的大,小的小,好了,能帮助我们理解算法就好了,自从有了转基因,今后多重的橙子都可能遇到。
事先解释一下,我们这些橙子在桌上排成了一排,并且每一个橙子都放在了盘子里,盘子不移动,我们只移动盘子里的橙子,空盘子用*
表示,手里的橙子用M表示,为了省点力气,我们尽可能的少移动橙子。
起初桌子上盘子里的橙子情况是这样的:
6, 2, 7, 3, 8, 9
,M=*
用手拿起第一个盘子里的橙子后:
*, 2, 7, 3, 8, 9
,M=6
从后往前找到第一个比M小的橙子放到前面,9、8、3,发现3是第一个符合条件的,把它拿到前面的盘子,变成了这样:
3, 2, 7, *, 8, 9
,M=6
然后第一个不算从前往后找到第一个比M大的橙子放到后面,2、7,发现7是第一个符合条件的,把它放在后面的空盘子:
3, 2, *, 7, 8, 9
,M=6
到此为止,我们已经把所有位置都遍历一遍了,这就是所谓的一趟排序,如果中间还有位置没有比较,重复步骤3和步骤4,直到所有的位置的橙子都被遍历到,把
M=6
放到最后的空盘子中就变成了:3, 2, 6, 7, 8, 9
,M=*
执行到这个步骤,原来的这些橙子就被分成了两部分,比
M=6
小的放到了它的前面,比M=6
大的放到了它的后面,现在就变成了两个规模较小的数组排序,我们以前面的待排数组N1为例,重复步骤2,先取出第一个橙子,拿在手里:*, 2
,M=3
重复步骤3,从后往前找到第一个比M小的橙子放到前面,发现2这个橙子,然后把它放到前面的空盘子,现在的情况如下:
2, *
,M=3
本来应该重复步骤4,但是此时发现所有的位置已经遍历过了,所以步骤4省略,直接步骤5,把
M=3
放在空盘子中:2, 3
,M=*
此时被
M=3
分割的就过只有一部分,并且不大于一个橙子,所以左半部分排序结果,总体来看顺序为:2, 3, 6, 7, 8, 9
,M=*
接着就要对步骤5后面的右半部分排序了,也就算是对
7, 8, 9
,虽然现在数据少我们一眼就能看出这结果数是有序的,但是如果在程序代码中,还是会对这部分橙子重复步骤3、4、5来达到有序,这里就不再逐步解释了,最后的结果就是:2, 3, 6, 7, 8, 9
,M=*
代码实现
1 | /* |
代码分析
上述代码与橙子排序的示例思路完全一致,key = array[low]
是步骤2,选取第一个元素作为中轴;最外层的while
循环是反复重复步骤3和步骤4,保证遍历所有位置的橙子;内部的第一个while
循环是步骤3,从后面找到第一个比中轴小的;内部的第二个while
循环是步骤4,从前面找到第一个比中轴大的;array[front] = key;
就是步骤5,把手里的橙子放回到空盘子中;接下来的两个函数调用都是调用自己,也就是递归调用,分别处理小于M的一段和大于M的一段,怎么样?代码是不是好理解多了?如果觉得我理解的有问题或者代码有错,也欢迎大家批评指正。
运行测试
如果你想运行测试一下,可以复制或者下载源代码,在本机运行测试一下,当然也可以选择在线编辑器,这是我新发现的在线编译器,样子还挺好看的,把源代码复制到网页中运行查看结果。