说一说程序员“举一反三”的能力

题图：“私想者”

        获得思想的能力，我们称之为智力。解决一个问题，如果你能做到举一反三，那么你就真正获得了解决这一类问题的思想了。

        好吧，我们一起来体会一下自己“举一反三”的能力究竟怎么样。

        一、从快速排序说起

        快速排序可以说是应用最广的一种排序算法。其思想是基于分治模式，将问题不断缩小，对小的问题进行排序，合并，后最终完成排序。

        其中，快速排序最为核心的一个步骤是划分（partition）待排序数组：从数组中选择一个元素(主元)，然后以这个主元为基准，将数组划分成两部分，使得前边部分元素都小于主元，后边部分元素都大于主元。(这里假设为从小到大排序)，更详细的快速排序介绍见此文：快速排序

        如下图所示为一个划分数组的实例，这里选取数组的最后一个元素作为主元。

        其伪代码如下：

//核心函数，对数组A[p,r]进行就地重排，将小于A[r]的数移到数组前半部分，  将大于A[r]的数移到数组后半部分。 PARTITION (A,p,r)      pivot <—— A[r]      i <—— p-1 for j <—— p to r-1 do if A[j] < pivot              i <—— i+1             exchange A[i]<——>A[j]      exchange A[i+1]<——>A[r]return i+1

         二、如果你理解了快速排序算法思想

        假设你知道并理解了快速排序算法，我们接下来解决如下一个问题。

        问题描述：

        输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

        分析与解答：

        最容易想到的办法是从头扫描这个数组，每碰到一个偶数，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一 个空位，然后把该偶数放入这个空位。由于每碰到一个偶数，需要移动O(n)个数字，所以这种方法总的时间复杂度是O(n^2)，不符合题目要求。

        事实上，若把奇数看做是小的数，偶数看做是大的数，那么按照题目所要求的奇数放在前面偶数放在后面，就相当于小数放在前面大数放在后面，联想到 快速排序中的 partition 过程，不就是通过一个主元把整个数组分成大小两个部分么，小于主元的小数放在前面，大于主元的大数放在后面。

        而 partition 过程有以下两种实现：

1. 一头一尾两个指针往中间扫描，如果头指针遇到的数比主元大且尾指针遇到的数比主元小，则交换头尾指针所分别指向的数字；
2. 一前一后两个指针同时从左往右扫，如果前指针遇到的数比主元小，则后指针右移一位，然后交换各自所指向的数字。

        类似这个 partition 过程，奇偶排序问题也可以分别借鉴 partition 的两种实现解决。

        为何？比如 partition 的实现一中，如果最终是为了让整个序列元素从小到大排序，那么头指针理应指向的就是小数，而尾指针理应指向的就是大数，故当头指针指的是大数且尾指针指的是小数的时候就不正常，此时就当交换。

        因此，我们的做法是维护两个指针i和j，一个指针指向数组的第一个数的前一个位置，我们称之为后指针i，向右移动；一个指针指向数组第一个数， 称之为前指针j，也向右移动，且前指针j先向右移动。如果前指针j指向的数字是奇数，则令i指针向右移动一位，然后交换i和j指针所各自指向的数字。

        如果你能很快想到类似快排 partition 的解决方案，说明你理解了快速排序。

        三、举一反三——是金子，你就应该发光

        奇偶调序问题我们顺利用 partition 思想在O(n)的复杂度下解决了战斗，恩，我们获取思想的能力还是不错的。接下来，我们再来一瓶：荷兰国旗问题。

        拿破仑席卷欧洲大陆之后，代表自由，平等，博爱的竖色三色旗也风靡一时。荷兰国旗就是一面三色旗（只不过是横向的），自上而下为红白蓝三色。

        该问题本身是关于三色球排序和分类的，由荷兰科学家 Dijkstra 提出。由于问题中的三色小球有序排列后正好分为三类，Dijkstra 就想象成他母国的国旗，于是问题也就被命名为荷兰旗问题（Dutch National Flag Problem）。

        问题的正规描述：

        有n个红白蓝三种不同颜色的小球，乱序排列在一起，请通过两两交换任意两个球，使得从左至右，依次是一些红球、一些白球、一些蓝球。

        分析与解法：

        首先，你看到在问题，可能会无从下手。但如果给你提示，让你尽量往快排思想上靠拢呢？

        我们知道，快速排序依托于一个 partition 分治过程，在每一趟排序的过程中，选取的主元都会把整个数组排列成一大一小的部分，那我们是否可以借鉴 partition 过程设定三个指针完成重新排列，使得所有球排列成三个不同颜色的球呢？

        由此，我们得到此问题的一个解决方法：

        通过前面的分析得知，这个问题类似快排中 partition 过程，只是需要用到三个指针：一个前指针 begin，一个中指针 current，一个后指针 end，current 指针遍历整个数组序列，当

1. current 指针所指元素为 0 时，与 begin 指针所指的元素交换，而后 current++，begin++ ；
2. current 指针所指元素为 1 时，不做任何交换（即球不动），而后 current++ ；
3. current 指针所指元素为 2 时，与 end 指针所指的元素交换，而后，current 指针不动，end– 。

        为什么上述第 3 点中，current 指针所指元素为 2 时，与 end 指针所指元素交换之后，current 指针不能动呢？因为第三步中 current 指针所指元素与 end 指针所指元素交换之前，如果 end 指针之前指的元素是0，那么与 current 指针所指元素交换之后，current 指针此刻所指的元素是 0，此时，current 指针能动么？不能动，因为如上述第 1 点所述，如果 current 指针所指的元素是0，还得与 begin 指针所指的元素交换。

        说这么多，你可能不甚明了，直接引用下 gnuhpc 的图，就一目了然了：

        通过以上几个问题，你现在可以给自己“举一反三”的能力打个分了。

        如果你觉得你懂了快速排序算法，在给出提示的情况下，却没能想到荷兰国旗问题的相关解法，甚至奇偶调序问题都想不到相关的解法，你应该问问自己：你真的懂了吗？

        不管你懂不懂，我反正不懂！

        全文大部分内容整理自《程序员编程艺术》一书部分章节。