略显神秘的快速排序

继续我的填坑旅程,上次说到《排序算法系列之(二)——冒泡排序名字最为形象的一个》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表示,为了省点力气,我们尽可能的少移动橙子。

  1. 起初桌子上盘子里的橙子情况是这样的:
    6, 2, 7, 3, 8, 9M=*

  2. 用手拿起第一个盘子里的橙子后:
    *, 2, 7, 3, 8, 9M=6

  3. 从后往前找到第一个比M小的橙子放到前面,9、8、3,发现3是第一个符合条件的,把它拿到前面的盘子,变成了这样:
    3, 2, 7, *, 8, 9M=6

  4. 然后第一个不算从前往后找到第一个比M大的橙子放到后面,2、7,发现7是第一个符合条件的,把它放在后面的空盘子:
    3, 2, *, 7, 8, 9M=6

  5. 到此为止,我们已经把所有位置都遍历一遍了,这就是所谓的一趟排序,如果中间还有位置没有比较,重复步骤3和步骤4,直到所有的位置的橙子都被遍历到,把M=6放到最后的空盘子中就变成了:
    3, 2, 6, 7, 8, 9M=*

  6. 执行到这个步骤,原来的这些橙子就被分成了两部分,比M=6小的放到了它的前面,比M=6大的放到了它的后面,现在就变成了两个规模较小的数组排序,我们以前面的待排数组N1为例,重复步骤2,先取出第一个橙子,拿在手里:
    *, 2M=3

  7. 重复步骤3,从后往前找到第一个比M小的橙子放到前面,发现2这个橙子,然后把它放到前面的空盘子,现在的情况如下:
    2, *M=3

  8. 本来应该重复步骤4,但是此时发现所有的位置已经遍历过了,所以步骤4省略,直接步骤5,把M=3放在空盘子中:
    2, 3M=*

  9. 此时被M=3分割的就过只有一部分,并且不大于一个橙子,所以左半部分排序结果,总体来看顺序为:
    2, 3, 6, 7, 8, 9M=*

  10. 接着就要对步骤5后面的右半部分排序了,也就算是对7, 8, 9,虽然现在数据少我们一眼就能看出这结果数是有序的,但是如果在程序代码中,还是会对这部分橙子重复步骤3、4、5来达到有序,这里就不再逐步解释了,最后的结果就是:
    2, 3, 6, 7, 8, 9M=*

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

功能: 快速排序,实现数组元素从小到大排列
参数: array--表示待排序的数组,此处会退化成指针
low --待排序区间的起始索引
high --待排序区间的结束索引
返回值:无
注意: 只用来表示思路,不考虑指针为空等特殊情况
*/
void (int array[], int low, int high)
{
if (low >= high)
return;

int front = low, back = high, key = array[low]; // 选取第一个元素作为中轴
while (front < back)
{
while (front < back && array[back] >= key)
--back;
array[front] = array[back]; // 从后面找到第一个比中轴小的交换

while (front < back && array[front] <= key)
++front;
array[back] = array[front]; // 从前面找到第一个比中轴大的交换
}

array[front] = key;
quick_sort(array, low, front - 1); // 递归快排前半段
quick_sort(array, low, front + 1); // 递归快排后半段
}

代码分析

上述代码与橙子排序的示例思路完全一致,key = array[low]是步骤2,选取第一个元素作为中轴;最外层的while循环是反复重复步骤3和步骤4,保证遍历所有位置的橙子;内部的第一个while循环是步骤3,从后面找到第一个比中轴小的;内部的第二个while循环是步骤4,从前面找到第一个比中轴大的;array[front] = key;就是步骤5,把手里的橙子放回到空盘子中;接下来的两个函数调用都是调用自己,也就是递归调用,分别处理小于M的一段和大于M的一段,怎么样?代码是不是好理解多了?如果觉得我理解的有问题或者代码有错,也欢迎大家批评指正。

运行测试

快速排序–源码

如果你想运行测试一下,可以复制或者下载源代码,在本机运行测试一下,当然也可以选择在线编辑器,这是我新发现的在线编译器,样子还挺好看的,把源代码复制到网页中运行查看结果。