作为一个处理问题的很基础的手段,排序在计算机科学的各个方面广泛应用着——例如在查找算法中,如果我们面对的是有序列的话,那么用二分查找我们就倍感顺利、快速,而要获得有序列,首先就得对待查找序列进行排序;又例如,在操作系统的内存管理机制中,内存分配存在许多策略,其中一种被称作 First Fit——遍历可用内存,找到第一个大于等于所需内存大小的内存块,在这块内存块中分配所需内存供使用——而为了让遍历的过程更为快速,或者说降低 First Fit 分配策略实现的时间复杂度,我们可以维护一个按可用内存块大小进行降序排序的内存块索引表,当我们分配内存时便总是可以在索引表中第一位得到最大的可用内存块的地址,从而减少遍历时间,而为了维护这个降序的可用内存索引表,在内存的分配的过程中就必须对内存索引表进行以内存大小为主键的排序操作;再例如,在一些 web 后端程序的页面 cache 机制实现中,我们会按照自己的计算标准对各个页面记录下热度,进而让热度高的页面能够被优先缓存到资源有限的 cache 服务器内存中,为了维护这个表,我们就必须定期对该表进行以页面热度为主键进行降序排序操作。类似的例子,常见的、不常见的还有很多。可以说,排序基本上被应用在软件开发的各个层级、领域。

因为排序在工程实践中是如此重要,优秀的科学家、工程师们发明了许许多多适合于不同场景的排序算法Tony Hoare 发明的快速排序是其中最有名、应用最广、在面试过程中最经常被考察到的排序算法之一。

快速排序使用了分治法

维基百科上的这幅动图很形象地展示了一次快速排序的执行过程:

根据该图,我们可以这样描述快速排序算法的策略:将大问题划分为小问题,而且保证问题的需求以及问题被解决的手段是对于各个问题而言是相同的,这样一来就可以用相同的方式求解各个子问题,等我们解决了所有子问题后,子问题解的组合就是母问题的解。这就是分治法

快速排序利用分解数组来达到排序的目的

当面对一个需要被排序的乱序数组时,我们可以用下面的形式递归地把它分解为一级级的子数组:

(比基准数小的数组成的前部数组)(基准数)(比基准数大的数组成的后部数组)

上面的基准数是指按照一定的方式从被分解数组中选出来的某个元素(基准数的挑选是一个很有意思的话题,它直接影响到快排实现的效率,相关讨论见)。快速排序利用上述结构来分解数组进而达到了排序的目的,然而具体的分解步骤是怎样的呢?用下面的例子可以进一步阐释:

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
Array: [1, 5, 2, 7, 6, 15, 20, 10, 9, 11, 8]

① 第一次分解
[
([1, 5, 2, 7, 6]) //小于基准数的元素在其前形成了前部数组,元素之间的顺序没有改变
([8]) //选择最后的元素 8 为基准数
([15, 20, 10, 9, 11]) //大于基准数的元素在其后形成了后部数组,元素之间的顺序没有改变
]
② 再按照上一步的分解方式对前部、后部数组进行分解
[
([
([1, 5, 2]) //这个数组还不是只含两个或两个以下元素的原子数组,可以继续分解
([6])
([7])
])
([8])
([
([10, 9]) //已经被分解为只含两个元素的数组,选择 2 为基准数再操作一次得到的就是有序排列了
([11])
([15, 20])
])
]
③ 至此所有数组都是原子数组了,而且元素的排列已经是有序的了
[
([
([
([1])
([2])
([5])
])
([6])
([7])
])
([8])
([
([
([])
([9])
([10])
])
([11])
([
([15])
([20])
([])
])
])
]

从上面的例子我们不难理解数组分解的具体步骤:

  1. 选取一个基准数;
  2. 将数组的元素进行移动,大于基准数的放其前面,小于基准数的放其后面——这样就形成了前部子数组以及后部子数组。前部的所有元素都小于基准数,后部的所有元素都大于基准数;
  3. 在新获得的前部、后部数组上重复 1、2 步骤;
  4. 当数组被分解为最小数组时,选取基准数后分解数组再合并前部、基准数、后部,其结果本身就是有序的了。

一个需要额外解释的概念是原子数组:当一个数组只含有两个以及两个以下的元素时,对其按照基准数进行分解操作后,获得的结果一定是有序的,这样的数组被称为原子数组。当然,这个概念并没有哪个权威教材有介绍,是我为了加强理解创造的。下面是一个原子数组的分解过程:

1
2
3
Origin: [5, 4]
① -> 分解完后整个元素的排列就是有序的了
[([])([4])([5])]

当数组被分解到原子数组的粒度后,我们再逐层合并结果,最后得到的总合并结果就是原数组元素组成的有序数组了,至此则算法结束。

##具体实现

下面是一份来自于维基百科的快速排序的 C 语言实现,它是利用递归来实现的数组分解过程:

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
30
31
32
33
34
void quickSort(int data[], int left, int right)
{

int temp = data[left]; //选取数组的最左边元素作为基准数
int ptr = left;
int i = left + 1, j = right;
if(data[i] <= temp)
{
data[ptr] = data[i];
ptr = i;
}
while(i!=j)
{
if(data[j] >= temp)
{
j--;
}
else
{
data[ptr] = data[j];
ptr = j;
while(data[i] <= temp && i != j)
{
i++;
}
data[ptr] = data[i];
ptr = i;
}
}
data[ptr] = temp;
if(left < ptr - 1)
quickSort(data, left, ptr - 1);
if(ptr + 1 < right)
quickSort(data, ptr + 1, right);
}

我记得有一个“都市传说”,是说 90% 的程序员无法在没有辅助信息的情况下徒手写出一个完全没有错误的快速排序,大家可以尝试一下。

##进一步讨论

我们继续在一个更有意思的层面上讨论一下快速排序算法——快排和二叉排序树的关系。在快速排序的算法中,利用分治法的思想,我们将大问题(对无序数组排序)分解为了一个二叉树形的问题。这个过程用语言描述不是很方便,我们用图来解释。

第一次进行问题转化,选出基(准)数,并将问题分解为了子问题 1 和子问题 2:

第二次,在子问题上进行进一步的相同操作则会形成如下的问题结构:

继续下去,你就会发现,其实原始问题被划分为了一个二叉树形的结构——很完美的是,它甚至还是一个满的完全二叉树。

我们以数组 [2,5,3,6,1,10,9,7,8,4] 为例子,选取最后一个数字为基(准)数。按照之前的算法进行操作,最后我们得到了如下结构:

这其实本身就是一棵二叉查找树。也就是说,通过快速排序的分治以及递归的处理之后,基(准)数之间存在一个父基数以及子基(准)数的关系,而这个关系结合基(准)数本身的值构成了一个二叉查找树。与其说快排之后我们按照数列的下标进行遍历就得到了排序好的序列,不如说我们按照基(准)数组成的二叉查找树进行了一次按中序进行的遍历——而二叉查找树的中序遍历结果就是有序结果。

##备注

这篇文章最早是我在 2011 年写完,并发布于当时的博客上的。我对其内容进行修改、添加,形成了此文。