重排序数组

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

思路：
从前向后扫描，遇到奇数的话，就将这个奇数与在它最前面的那个偶数交换，扫到最后，所有的奇数都可以排在偶数前面。最差情况下，复杂度高达O(N*N)。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void reOrderArray(int [] array) {
    int temp = 0;
    for (int i = 1; i < array.length; i++) {
        // 遇到了一个奇数
        if (array[i] % 2 == 1) {
            // 遍历它前面的所有数，将它插入到偶数前面
            for (int j = i; j > 0; j--) {
                if (array[j - 1] % 2 == 0) {
                    temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                }
            }
        }
    }
}