输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
注意
本题和 lintcode 上的快排变形题有区别，快排本身无法保证排序的稳定性，题目要求偶数和奇数的相对位置不能变
代码
- 插入排序思想，空间复杂度为O（1），时间复杂度为O（N^2）
public class Solution {
public void reOrderArray(int [] array) {
if (array == null || array.length == 0) {
return;
}
for (int i = 0; i < array.length; i++){
// i 位置是奇数
if (array[i] % 2 == 1){
int temp = array[i];
int j = i - 1;
// j 的位置为偶数
// j>=0 防止 j=i-1 越界
// 把 i 位置空出来，把 i 位置前面的偶数全部后移一位，把 array[i] 位置的奇数插入到新的位置
while (j >= 0 && array[j] % 2 == 0){
array[j + 1] = array[j];
j--;
}
// 注意此处是 j+1 不是 j
array[j + 1] = temp;
}
}
}
}
- 归并排序，时间复杂度 O(nlogn)，空间复杂度 O(n)
public class Solution {
public void reOrderArray(int [] array) {
if (array == null || array.length == 0) {
return;
}
int[] des = new int[array.length];
MergeMethod(array, des, 0, array.length - 1);
}
public void MergeMethod(int[] array, int [] des, int start, int end){
if (start < end){
int mid = (start + end) / 2;
MergeMethod(array, des, start, mid);
MergeMethod(array, des, mid + 1, end);
Merge(array, des, start, mid, end);
}
}
public void Merge(int[] array, int[] des, int start, int mid, int end){
int i = start;
int j = mid + 1;
int k = start;
// 四个 while 其实是同时执行，没有先后顺序，因为 array[i] 和 array[j] 同一时刻只能满足一个 while
// 把奇数归并
while(i <= mid && array[i] % 2 == 1){
des[k++] = array[i++];
}
while(j <= end && array[j] % 2 == 1){
des[k++] = array[j++];
}
// 把偶数归并
while(i <= mid){
des[k++] = array[i++];
}
while(j <= end){
des[k++] = array[j++];
}
for(int m = start; m <= end; m++){
array[m] = des[m];
}
}
}
- 既然开辟了新的数组，完全可以从头扫描两遍，第一遍遇到奇数加入数组，第二遍遇到偶数加入数组，最后把新数组中的值逐个复制到原数组中去
public class Solution {
public void reOrderArray(int [] array) {
if (array == null || array.length == 0) {
return;
}
int[] list = new int[array.length];
int index = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] % 2 == 1) {
list[index++] = array[i];
}
}
for (int i = 0; i < array.length; i++) {
if (array[i] % 2 == 0) {
list[index++] = array[i];
}
}
for (int i = 0; i < array.length; i++) {
array[i] = list[i];
}
}
}
