【剑指offer-13】调整数组顺序使奇数位于偶数前面

• 考点：数组
• 时间限制：1秒
• 空间限制：32768K
• 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

---

思路：

我的愚蠢的做法决定放在其他思路1里面。

从题目得出的信息：
相对位置不变—>保持稳定性；
奇数位于前面，偶数位于后面 —>存在判断，挪动元素位置；

这些都和内部排序算法相似，考虑到具有稳定性的排序算法不多，例如插入排序，归并排序。
下面这个算法好像是快速排序？

1. 从第一个元素开始找起，找奇数。
   找到奇数之后，把前面所有的数往后移。pos-1就是他相邻的数如果是偶数，就交换，就是不断和前面的偶数进行交换，直到我遇上了我要的奇数。

代码：

public class Solution {
    public void reOrderArray(int [] array) {
        for (int i = 1; i < array.length; i++) {
            if (array[i] % 2 == 1) {
                // 奇数
                int pos = i;
                while ((pos >= 1) && (array[pos - 1] % 2 == 0)) {
                    int temp = array[pos];
                    array[pos] = array[pos - 1];
                    array[pos - 1] = temp;
                    pos--;
                }
            }
        }
    }
}

我的问题：

---

其他思路：

其实我的做法真的有点差，我借助了java的库ArrayList。并且用了很多次的迭代循环对数组进行复制。
不过总体思路是简单而又暴力。

1. 复制原有数组到一个ArrayList中。
2. 逐个遍历这个数组，从后往前遍历，如果他是奇数，那么我就插入到另一个数组的第0个位置。并且把这个数从我当前数组里删除。
3. 将当前数组剩下的值，逐个复制到新的copy数组当中。
4. 返回copy数组的int[]形式。

import java.util.ArrayList;
public class Solution {
    public void reOrderArray(int [] array) {
        ArrayList<Integer> array1 = new ArrayList<Integer>();
        for (int i = 0; i < array.length; i++) {
            array1.add(array[i]);
        }
        ArrayList<Integer> copy = new ArrayList<Integer>();
        int length = array.length;
        for (int i = length - 1; i >= 0; i--) {
            if ((array1.get(i) & 1) == 1) {
                copy.add(0, array1.get(i));
                array1.remove(i);
            }
        }
        for (int i = 0; i < array1.size(); i++) {
            copy.add(array1.get(i));
        }
        for (int i = 0; i < array.length; i++){
            array[i] = copy.get(i);
        }
    }
}

有点搞笑，为什么我要写的这么复杂，三个循环就搞定了的事情。
下面这个会比较简单，时间复杂度O(3n)，因为java不能直接赋值给原来的数组，值不会变，所以不得已又用了一个新的数组进行复制。

大家都是这么说的，如果采用另开辟一个数组的话，相当于拿空间换时间。

public class Solution {
    public void reOrderArray(int [] array) {
        int[] array1 = new int [array.length];
        int k = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 1) {
                array1[k++] = array[i];
            }
        }
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 0) {
                array1[k++] = array[i];
            }
        }
        for (int i = 0; i < array.length; i++) {
            array[i] = array1[i];
        }
    }
}

---

其他思路2：

冒泡排序的思想。
如果前一个数是偶数，后一个数是奇数，那么就交换，把奇数换到前面。

public class Solution {
    public void reOrderArray(int [] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if ((array[j] % 2 == 0) && (array[j + 1] % 2 == 1)) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }
}