题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，（偶数之间和奇数之间要保持相对顺序）
思路分析
- 如果题目没有要求保持相对顺序，则可以利用快速排序中的“二分”的思想，设置两个指针分别指向数组的头和尾，要将奇数排在偶数的前面，就要头指针扫描到偶数时停止，尾指针要扫描到奇数时停止
- 如果题目中要求保持相对顺序，可以用直接插入法的思想，如果遇到奇数，就将该奇数排在它最前面的偶数之前。
测试用例
- 功能测试：输入数组中的奇数、偶数交替出现;输入的数组中所有偶数都出现在奇数的前面;输入的数组中所有奇数都出现在偶数的前面。
- 特殊输入测试：输入nullptr指针;输入的数组只包含一个数字。
Java代码
public class Offer21 {
public static void main(String[] args) {
test1();
test2();
test3();
test4();
}
public static void reOrderArray(int[] array) {
Solution2(array);
}
/**
* 这种方法会打乱偶数之间 奇数之间的相对顺序(题目中并没有要求)
* 思路，利用快速排序中思想
* @param array
*/
private static void Solution1(int[] array) {
if(array == null) {
throw new IllegalArgumentException("参数非法!");
}
int i = 0;
int j = array.length - 1;
while (i < j) {
while (i < j && !isEven(array[i])) {//如果是奇数i下标后移，直到指向偶数
i++;
}
while (i < j && isEven(array[j])) {//如果是偶数j 下标前移，直到指向奇数
j--;
}
if (i < j) {
int tmp = array[j];
array[j] = array[i];
array[i] = tmp;
}
}
}
/**
* 当题目中要求要保持偶数之间 奇数之间的相对顺序时，
* 就需要用到这种方法
* 思路：插入排序的思想
* @param array
*/
private static void Solution2(int[] array) {
if(array==null || array.length<=0) {
throw new IllegalArgumentException("参数非法!");
}
int j,tmp;
for(int i=1;i<array.length;i++) {
if(!isEven(array[i])) {
tmp = array[i];
//此处j>=0的条件要放在前面
for(j=i-1; j>=0 && isEven(array[j]);j--) {
array[j+1] = array[j];
}
array[j+1] = tmp;
// 这种方式 也行
// j=i;
// while(j>0 && isEven(array[j-1])) {
// array[j] = array[j-1];
// j--;
// }
// array[j] = tmp;
}
}
}
private static boolean isEven(int number) {
return (number & 1) == 0;
}
private static void test1() {
int[] array = { -1, 9, 5, 2, 10, 6 };
System.out.println("原始数组：" + Arrays.toString(array));
reOrderArray(array);
System.out.println("调整结果：" + Arrays.toString(array));
System.out.println();
}
private static void test2() {
int[] array = { 2,10,8, 9,-7,17};
System.out.println("原始数组：" + Arrays.toString(array));
reOrderArray(array);
System.out.println("调整结果：" + Arrays.toString(array));
System.out.println();
}
private static void test3() {
int[] array = { 2};
System.out.println("原始数组：" + Arrays.toString(array));
reOrderArray(array);
System.out.println("调整结果：" + Arrays.toString(array));
System.out.println();
}
private static void test4() {
int[] array = null;
reOrderArray(array);
}
}