剑指offer13:调整数组顺序使奇数位于偶数前面

题目
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

解析：题目的意思也很明确，就是将奇数放在前面，偶数放在后面，但是相对顺序不能发生改变。

这道题最好画图看变化，一下就可以看出规律了。规律就是可以使用双指针，一个偶数指针，一个奇数指针，偶数指针一直前进，遇到奇数则与奇数指针交换，然后由于奇数指针的位置是上一次偶数指针的位置，此时表示乱序了然后循环交换即可。当时我第一次交换是前一个和后一个交换，后面发现如果中间元素超过2个，不能够复原顺序，所以只能采用每一个都和最后一个交换，这样的话一定能够顺序。

代码如下：我加了注释，跟着画画图绝对能出的

public void reOrderArray(int[] array) {
        if (array.length <= 1) return;
        // 首先定义两个指针
        int odd = 0;// 奇数
        int even = 0;// 偶数
        while (even < array.length) {
            if (array[even] % 2 == 0) {
                // 如果是偶数的话，留奇数指针在原位置，偶数指针前进
                even += 1;
                // 只要符合边界条件且是偶数一直向后查找，只为找到奇数
                while (even < array.length && array[even] % 2 == 0) {
                    even++;
                }
                // 否则就是遇到了奇数
                if (even < array.length) {
                    reOrderSwap(array, odd, even);
                    // 交换之后，由于偶数乱序了，此时需要交换使得位置变为正确的，此时odd位已经交换了
                    odd ++;// 此时奇数向后走一位
                    int temp = odd;// 采用一个临时变量，否则odd会移动,则奇数的结尾就乱了
                    while (temp + 1 <= even) {
                        // 这里主要是防止 4 6 2  => 2 4 6,如果单纯的只跟后面一个数交换会变成6 2 4结果还是错的
                        reOrderSwap(array, temp, even);
                        temp++;
                    }
                }
                // 如果这里没遇到，表明后面都是偶数，则会结束
            }else{
                // 否则第一个就是奇数,奇偶一起走
                odd++;
                even++;
            }
        }
    }

    public void reOrderSwap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

Keep thinking, keep coding~
2020-7-15 20:44:22