题目中没有要求相对位置不变, 所以可以使用快排的思路解题
思路如下(类似快速排序, 快速排序本身就是不稳定的):
- 设置两个指针,一个指针pBegin指向数组第一个元素,一个指针pEnd指向数组的最后一个元素;
- 当pBegin < pEnd时:pBegin指针不断右移,直到遇到某个偶数为止;同样的,pEnd不断左移,直到遇到某个奇数为止。
- 若此时pBegin < pEnd:交换两个元素,因此排在前面的奇数被交换到了后面
class Solution {
public void reOrderArray(int[] array) {
int i = 0;
int j = array.length - 1;
while (i < j) {
while (array[i] % 2 == 1) i++;
while (array[j] % 2 == 0) j--;
if (i < j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
如果要求相对位置不变, 可使用类似于冒泡排序
class Solution {
public void reOrderArray(int[] array) {
for (int i = array.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (array[j] % 2 == 0 && array[j + 1] % 2 == 1) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
}
}
}