这是《剑指Offer》第 21 题：

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

这个题，我一开始想到的解法是用一个和原数组一样大的空数组，两个指针 p1 和 p2，p1 指向数组第一个 元素的位置，p2 指向数组最后一个元素的位置。然后，从头遍历原数组，如果发现元素是奇数，我们就把 这个元素赋值给 p1 指向的位置，然后 p1 加 1；反之，把元素赋值给 p2 指向的位置，p2 加 1。这种 方法的时间复杂度是 O(n)；因为需要一个空数组，所以空间复杂度为 O(n)。

这是我的提交记录。

然后我转念一想，有没有更加高效的解法呢？比如把这个“空数组”去掉从而让空间复杂度为 O(1) 呢？

如果没有空数组这个辅助空间，那么我们就必须在原数组中进行调换操作，这时，我就想起了快速排序的 实现过程。快速排序也是在原数组中实现交换，找准一个 pivot，然后将数组中所有小于 pivot 的数放到 它的前面，把所有大于 pivot 的数放到它的后面。嗯，我们可以这样，同样是两个指针 p1 和 p2，p1 指向 原数组的第一个元素， p2 指向原数组的最后一个元素。然后我们在 p1 < p2 的情况下，从 p1 找出一个 偶数，再从 p2 找出一个奇数，将两者互换不就可以了？于是，我很快的用代码把算法实现了出来。

这是我的提交记录。

这样的话，相比第一个方法，我们的时间复杂度都是 O(n)，但是因为没有了空数组的辅助空间，所以我们的 空间复杂度降到了 O(1)。

然后，书中还将问题扩展了一下，如果实际情况中，我们不仅需要将数组中的奇偶数分开，还需要将正负数分开， 是否可以被 3 整除的数分开等等，那么这又应该如何处理呢？这时我想到的方法是，用一个函数指针来传递不同的 比较函数进去。因为我们可以发现，对于上述每个不同的需求，我们的核心代码框架都是一样的，只是比较函数 不同，所以我们用函数指针将比较函数和核心框架实现解耦，使得代码可以更加通用。

这是我针对书中的三个不同需求进行的练习。

启示：

  • 通过这个练习，一个让我惊喜的发现就是我自己可以利用所学习过的快速排序的思想去解决实际问题，这让我体会到 经典算法思想的重要性
  • 此外，书中的扩展问题让我复习了函数指针的用法，这也让我很开心

以上。