Question

题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

如果不考虑时间复杂度，最简单的思路应该是从头扫描这个数组，每碰到一个偶数时，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，这时把该偶数放入这个空位。由于每碰到一个偶数就需要移动O（n）个数字，因此总的时间复杂度是O（n²）。但是，这种方法不能让面试官满意。不过如果我们在听到题目之后马上能说出这个解法，面试官至少会觉得我们的思维非常敏捷。

只完成基本功能的解法，仅适用于初级程序员

这个题目要求把奇数放在数组的前半部分，偶数放在数组的后半部分，因此所有的奇数应该位于偶数的前面。也就是说我们在扫描这个数组的时候，如果发现有偶数出现在奇数的前面，我们可以交换它们的顺序，交换之后就符合要求了。

因此我们可以维护两个指针，第一个指针初始化时指向数组的第一个数字，它只向后移动；第二个指针初始化时指向数组的最后一个数字，它只向前移动。在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，我们就交换这两个数字。

下面以一个具体的例子比如输入数组{1,2,3,4,5}来分析这种思路。在初始化时，把第一个指针指向数组第一个数字1，而把第二个指针指向最后一个数字5（如图3.4（a）所示）。第一个指针指向的数字1是一个奇数，不需要处理，我们把第一个指针向后移动，直到碰到一个偶数2。此时第二个指针已经指向了奇数，因此不需要移动。此时两个指针指向的位置如图3.4（b）所示。这个时候我们发现偶数2位于奇数5的前面，符合我们的交换条件，于是交换两个指针指向的数字（如图3.4（c）所示）。

接下来我们继续向后移第一个指针，直到碰到下一个偶数4，并向前移动第二个指针，直到碰到第一个奇数3（如图3.4（d）所示）。我们发现第二个指针已经在第一个指针的前面了，表示所有的奇数都已经在偶数的前面了。此时的数组是{1,5,3,4,2}，的确是奇数位于数组的前半部分而偶数位于后半部分。

图3.4　调整数组{1,2,3,4,5} 使得奇数位于偶数前面的过程

注：（a）把第一个指针指向数组的第一个数字，第二个指针指向最后一个数字。（b）向后移动第一个指针直至它指向偶数2，此时第二个指针指向奇数5，不需要移动。（c）交换两个指针指向的数字。（d）向后移动第一个指针直至它指向偶数4，向前移动第二个指针直至它指向奇数3。由于第二个指针移到了第一个指针的前面，表明所有的奇数都位于偶数的前面。

基于这个分析，我们可以写出如下代码：

考虑可扩展性的解法，能秒杀Offer

如果是面试应届毕业生或者工作时间不长的程序员，面试官会满意前面的代码。但如果应聘者申请的是资深的开发职位，那面试官可能会接着问几个问题。

面试官：如果把题目改成把数组中的数按照大小分为两部分，所有负数都在非负数的前面，该怎么做？

应聘者：这很简单，可以重新定义一个函数。在新的函数里，只要修改第二个和第三个while循环中的判断条件就行了。

面试官：如果再把题目改改，变成把数组中的数分为两部分，能被3整除的数都在不能被3整除的数的前面。怎么办？

应聘者：我们还是可以定义一个新的函数。在这个函数中……

面试官：（打断应聘者的话）难道就没有更好的办法？

这个时候应聘者应该要反应过来，面试官期待我们提供的不仅仅是解决一个问题的办法，而是解决一系列同类型问题的通用办法。这就是面试官在考查我们对扩展性的理解，即希望我们能够给出一个模式，在这个模式下能够很方便地把已有的解决方案扩展到同类型的问题上去。

回到面试官新提出的两个问题上来。我们发现要解决这两个新的问题，其实只需要修改函数ReorderOddEven中的两处判断的标准，而大的逻辑框架完全不需要改动。因此我们可以把这个逻辑框架抽象出来，而把判断的标准变成一个函数指针，也就是用一个单独的函数来判断数字是不是符合标准。这样我们就把整个函数解耦成两部分：一是判断数字应该在数组前半部分还是后半部分的标准，二是拆分数组的操作。于是我们可以写出下面的代码：

在上面的代码中，函数Reorder根据func的标准把数组pData分成两部分；而函数isEven则是一个具体的标准，即判断一个数是不是偶数。有了这两个函数，我们可以很方便地把数组中的所有奇数移到偶数的前面。实现代码如下：

如果把问题改成把数组中的负数移到非负数的前面，或者把能被3整除的数移到不能被3整数的数的前面，都只需定义新的函数来确定分组的标准，而函数Reorder不需要做任何改动。也就是说解耦的好处就是提高了代码的重用性，为功能扩展提供了便利。

源代码：

本题完整的源代码详见14_ReorderArray项目。

测试用例：

- 功能测试（输入数组中的奇数、偶数交替出现，输入的数组中所有偶数都出现在奇数的前面，输入的数组中所有奇数都出现在偶数的前面）。

- 特殊输入测试（输入NULL指针、输入的数组只包含一个数字）。

本题考点：

- 考查应聘者的快速思维能力。要在短时间内按照要求把数组分隔成两部分，不是一件容易的事情，需要较快的思维能力。

- 对于已经工作过几年的应聘者，面试官还将考查其对扩展性的理解，要求应聘者写出的代码具有可重用性。