前言

又好久没有水博客了，最近要准备期末考试和若干大作业，还要准备夏令营有些分身乏术……今天复习明天下午的算法考试，复习到分治算法后看到了快速排序，觉得还是蛮重要的（虽然明天多半不会考），但是毕竟是算法里必讲的一环，今天来水一篇快排的博客。

正文

快速排序由 C. A. R. Hoare 在 1960 年提出。（这个老先生是一个在莫斯科拿到博士学位的英国人）

快速排序被作为分治算法的经典来介绍。

简要来说，快速排序的核心在于 PARTITION 算法。（你可以理解成快排的一个子算法）

PARTITION算法的工作很简单，对于给定的数组，他能够找到一个PIVOT（可以理解做分界点，这个分界点的选择是算法实现者的自由，本篇文章中均选择数组的最后一个元素，你选择第一个甚至随机都可以），把数组中比PIVOT大，或小的元素分别排开在PIVOT的两边（具体左右取决于你是从小到大排序还是从大到小排序）。也就是说 PARTITION 算法完成了数组的基本有序。

理解了 PARTITION 算法的思想后，快速排序就显得很简单了。

快速排序的思路就是对于给定的数组，先调用 PARTITION 算法，把数组变得部分有序（下文以从小到大排序为例），使得数组按顺序可以分为3部分，分别是：比 PIVOT 小的数， PIVOT，比 PIVOT 大的数。但是注意第一部分和第三部分内部的数不一定是有序的。然后接下来如果第一部分、第三部分的长度不为1的话，我们就继续对第一部分或者第三部分调用快速排序算法。这样逐层递归，每一个子部分都变得有序，最后整体数组就也是有序的了。

那么思路已经说完了，接下来上伪代码。（以《算法导论》中的伪代码为例）

PARTITION(A,p,r)
	x = A[r]   // 将最后一个元素作为 PIVOT
	i = p-1
	for j=p to r-1     
		do if A[j] <= x
			i = i+1
			exchange A[i] <-> A[j]
	exchange A[i+1]<->A[r]   
	return i+1   //返回 PIVOT 的索引

其实说实话这个伪代码要读懂理解还是要花点时间的……在这里嘲讽一哈只发伪代码不给解释的博客[doge]

首先我们看 PARTITION 函数的参数。A 是输入数组，p 是算法负责的部分的第一个元素的索引，r是最后一个元素的索引。

首先我们取出最后一个元素作为 PIVOT，然后接下来的过程就是从第一个元素开始遍历到倒数第二个元素。那么做什么呢？如果遍历到的元素（ A[j] ）小于等于 PIVOT，就把这个元素和索引是 i ++ 的元素交换。OK，这个操作第一次见应该要迷惑一下。

实际上，i 作为一个变量，可以这样理解：他存储着当前比 PIVOT 小的最后一个元素的索引。我们前面说到，PARTITION 算法结束后，数组应该是按顺序的三部分：比PIVOT小的，PIVOT，比PIVOT大的。那么 i 其实记录的是第一部分的最后一个元素的索引，之所以一开始赋值 p - 1，是因为一开始还没有遍历到比 PIVOT 小的元素，也就是说第一部分是空的。

理解了 i 的意思就很好理解上面的伪代码了。变量 i 维护了比 PIVOT 大和比 PIVOT 小的数组的边界。因为我们是最后遍历完除了 PIVOT （也就是最初数组最后的元素 A [r]）之后，才将 PIVOT 插入到数组中它合适的位置的（也就是第八行伪代码做的事情）。所以在前期遍历的过程中，如果遍历过的，比 PIVOT 小的数组不为空，那么它的范围就是 [p, i] 。i 后面的部分就是比 PIVOT 大的了。

那么我们回头看第五行到第七行的代码。当 A[j] 遍历到的元素比 PIVOT 大的时候，什么事情都不会发生。就是 j 继续往前遍历。而当遍历到的元素小于 PIVOT 的时候，i 指针也会跟着往前走，同时把 A[i+1] 与 A[j] 交换。还记得前面说 A[i] 是什么吗？是小于等于 PIVOT 的数组的最后一个元素。那么 A[i + 1]其实就是大于 PIVOT 的第一个元素，将 A[i+1] 与 A[j] 交换后，i 也要增加一，表示小于 PIVOT 的元素的边界增加了，同时那个之前的 A[i+1]因为本身就大于 PIVOT 换到 A[j] 后也满足条件。

哈哈哈希望没有把简单的问题说的太复杂了，希望这段话能够帮到第一次看到这段伪代码懵逼的童鞋吧。

PS：这个伪代码将等于 PIVOT 的元素与小于 PIVOT的元素视作一样的类型处理了。所以前文就没有特意说等于 PIVOT 的情况。

QUICKSORT(A,p,r)
    if p<r
       q = PARTITION(A,p,r)    //确定划分位置
       QUICKSORT(A,p,q-1)     //子数组A[p...q-1]
       QUICKSORT(Q,q+1,r)     //子数组A[q+1...r]

最后 QUICKSORT 的部分应该就不用多说了。就是不断的划分，然后对于两个子部分继续快排。如果快排的输入已经不合规了（ p < r ）就结束算法。

END

继续复习了[doge]

Haulyn5 的博客

算法：快速排序

前言

正文