剑指offer面试题系列

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

思路

刚拿到这个题时，脑子中有三种思路：

思路一：原地调整。类似于插入排序的思路，从数组的第一个元素开始遍历，遇到偶数就跳过，遇到奇数，就看此数字的前面有没有遍历过偶数，如果遍历过，就插入到最开始的那个偶数前面，如果没有，接着向前遍历。

但是这种算法的时间复杂度：O(n^2).因为几乎每次都要找到前面的第一个偶数，然后再插进去。

思路二：为了降低时间复杂度，开辟另外两个数组，一个存储奇数，一个存储偶数。遍历完了，将两个数组拼接。

但是这种思路太过于耗费空间了。最终也放弃。

思路三：基于交换，用一个游标odd表示奇数，even表示偶数，isPreEven表示当前遍历到的数的前面是否是偶数。

从数组的第一个元素开始遍历，遍历到偶数，就设置isPrevEven为true，遍历到奇数就与前面最开始遍历到的偶数交换。但是这种思路实现起来，很麻烦，也作罢。

基于思路三的繁琐，想起了从一边遍历不如从数组两端开始同时遍历。

灵光一现，想起来了快速排序。快速排序的思路不就是从两端开始遍历的吗，将两边大于枢纽元的数字和小于枢纽元的数字交换。这种算法的时间复杂度不会超过O(n).

于是就有了下面的代码：

代码

public static void Adjust(int[] arr) {
        int i = 0, j = arr.length - 1;
        for(;;) {
            while(arr[i] % 2 != 0)
                i++;
            while(arr[j] % 2 == 0)
                j--;
            if(i < j)
                Swap(arr, i, j);
            else 
                break;
        }
    }

代码特别简洁，但是实现了功能。实现的一瞬间，成就感爆棚。

总结

前面两天排序真没有白看，《数据结构与算法分析》真是本好书，一定要反复看。终于明白了思路迁移的重要性。
同时也知道，当你的算法实现的太过于繁琐的时候，试试有没有更简洁的算法，或许会让你大吃一惊呢。