算法这一块是我的弱项。就以快速排序这样简单的算法,大二学完以后,就没有回顾过了。因为C中有qsort()接口,而C++中也有sort()接口。前一阵子想巩固一下基础知识,回顾了这一著名算法。
因为大学学过,所以大致知道它的一个过程——也就是一个递归。设给定一序列arr[0...N],首先通过arr[0]将arr[0...N]一分为二(我比较懒,不画图了,大家将就看哈),如下:
__前半部分,特点:这半部分序列中元素<arr[0]__ arr[0] __后半部分,特点:这半部分序列元素>= arr[0]_ (1)
↑
pilot所在位置(是不是叫pilot的?我忘了,^_^)
接下来,就是递归排序前半部分和后半部分,递归终止条件就是待排序的序列长度<=1。这个过程是不是很简单?那怎么找arr[0]所在位置,换句话说,怎么把原来的序列一分为二,满足(1)给定的条件?其实,这个问题我一开始也想了好久,第一版代码写出来运行结果还是不对的,经过调试才最后运行正确。
这里必然要对序列进行遍历,并且遍历过程中要保持一定的要求——就是所谓的循环不变式(《算法导论》一开始就介绍这个概念了)。我们这里要满足的要求(或学术化一点叫循环不变式)可以这么描述:遍历过程中,假设现在循环变量值为i,我们要保证:
arr'[0]...arr'[pilot-1] < arr'[pilot] <= arr'[pilot+1]...arr'[i] (2)
我们这里符号用的是arr'(上撇号),这里arr'[pilot]存放的是arr[0],采用不同符号以表示与原始序列不同了。
问题:怎么在遍历过程中,保持(2)成立???
其实,想到也不难,可能要花点心思。首先把arr[0]保存下来,放在变量pilot_value中,初始的情形如下:
____ arr[1] arr[2]...arr[N]
↑ ↑
pilot i
因为arr[0]保存下来了,所以pilot所指的位置可以认为是没有意义了,所以我在画了一条线——表示这可以看做是空的。遍历从i=1开始,遍历的目的是把所有小于pilot_value的值放到pilot所指位置的左边(如上:初始的时候,pilot左边是没有元素)。现在我们假设循环变量到i+1了,表明前面i个元素满足(2)式要求了,现在就是移动arr[i+1]到合适位置,如下:
arr'[0]...arr'[pilot-1] < ___ <= arr'[pilot+1]...arr'[i] arr[i+1] (3)
↑
pilot
很简单,就是比较pilot_value和arr[i+1],两种情况咯:
(1)若 pilot_value <= arr[i+1],不需要做任何操作;
(2)若pilot_value > arr[i+1],此时:直接将pilot位置上放置arr[i]吗?那就试试看,如果这么做,就会出现如下情况:
arr'[0]...arr'[pilot-1] arr[i] arr'[pilot+1]...arr'[i] _____ (4)
↑
新的pilot
这时,pilot应该+1,即箭头指向的位置。我们知道pilot指向的位置在遍历完成后,是要存放arr[0](即:pilot_value)的,而此时pilot指向的是一个有意义的位置。注意(4)中最后一个位置存放的是arr[i+1],这个位置现在存放这个值还有意义吗?显然没意义了!这时只要把arr’[pilot+1]和下划线所在位置的值换一下就好了,这样新的pilot所指向的位置就可以认为没意义了——可以看做是空的了。最后结果如下:
arr'[0]...arr'[pilot-1] arr[i] _____ arr'[pilot+2]...arr'[i]arr'[pilot+1] (5)
↑
新的pilot