剑指Offer面试题：16.调整数组顺序使奇数位于偶数前面
一、题目
————————————————
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
————————————————
二、思路
————————————————
方法一：创建一个新数组，时间复杂度 O(N)，空间复杂度 O(N)。
方法二：使用冒泡思想，每次都当前偶数上浮到当前最右边。时间复杂度 O(N2)，空间复杂度 O(1)，时间换空间。
————————————————
三、解决问题
————————————————
测试算例
1.功能测试（数组中奇偶数交替出现；数组中先奇数后偶数；数组中先偶数后奇数）
2.特殊测试（null，空数组，一个数据的数组）
————————————————
package swordoffer;
/**
* @author LQ
* @version 1.0
* @date 2020-03-20 15:18
*/
import java.util.Arrays;
/**
* 题目描述
* 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
* 使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
* 并保证奇数和奇数，偶数和偶数之间的相对位置不变。
*/
public class Solution16 {
public static void main(String[] args) {
Solution16 demo = new Solution16();
System.out.println("==============================");
System.out.println("test1");
demo.test1();
System.out.println("==============================");
System.out.println("test2");
demo.test2();
System.out.println("==============================");
System.out.println("test3");
demo.test3();
System.out.println("==============================");
System.out.println("test4");
demo.test4();
System.out.println("==============================");
System.out.println("test5");
demo.test5();
System.out.println("==============================");
System.out.println("test6");
demo.test6();
System.out.println("==============================");
System.out.println("test7");
demo.test7();
System.out.println("==============================");
}
//方法一：创建一个新数组，时间复杂度 O(N)，空间复杂度 O(N)。
public void reOrderArray01(int [] array) {
if(null == array || array.length == 0){
System.out.println("数组为空");
return;
}
//奇数个数
int oddCount = 0;
for (int x : array){
//计算数组中奇数个数
if(!isEven(x)){
oddCount++;
}
}
//创建并返回此对象的一个副本。“副本”的准确含义可能依赖于对象的类
int[] copyArray = array.clone();
int i = 0,j = oddCount;
for (int num : copyArray) {
if((num & 1) == 1){
//奇数位于数组的前半部分
array[i++] = num;
}else{
//偶数位于数组的后半部分
array[j++] = num;
}
}
}
//判断是否为偶数
private boolean isEven(int x) {
//为负数的时候，对于负数的取模将会成为一个负数
//return x % 2 == 0;
return (x & 1) == 0;
}
//方法二：使用冒泡思想，每次都将当前偶数上浮到当前最右边。
//时间复杂度 O(N2)，空间复杂度 O(1)，时间换空间。
public void reOrderArray02(int[] array) {
if(null == array || array.length == 0){
System.out.println("数组为空");
return;
}
int nums = array.length;
for (int i = nums - 1; i > 0; i--) {
for (int j = 0; j < i; j++){
if(isEven(array[j]) && ! isEven(array[j+1])){
swap(array,j,j+1);
}
}
}
}
private void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
//===============测试代码===================
void test1() {
int[] array = null;
int[] copyArray = array;
System.out.println("原始数组："+ Arrays.toString(array));
reOrderArray01(array);
System.out.println("调整结果："+Arrays.toString(array));
System.out.println("===========方法二：使用冒泡思想============");
System.out.println("原始数组："+ Arrays.toString(copyArray));
reOrderArray02(copyArray);
System.out.println("调整结果："+Arrays.toString(copyArray));
}
void test2() {
int[] array = {};
int[] copyArray = {};
System.out.println("原始数组："+Arrays.toString(array));
reOrderArray01(array);
System.out.println("调整结果："+Arrays.toString(array));
System.out.println("===========方法二：使用冒泡思想============");
System.out.println("原始数组："+ Arrays.toString(copyArray));
reOrderArray02(copyArray);
System.out.println("调整结果："+Arrays.toString(copyArray));
}
void test3() {
int[] array = {-2,4,-6,1,-3,5};
int[] copyArray = {-2,4,-6,1,-3,5};
System.out.println("原始数组："+Arrays.toString(array));
reOrderArray01(array);
System.out.println("调整结果："+Arrays.toString(array));
System.out.println("===========方法二：使用冒泡思想============");
System.out.println("原始数组："+ Arrays.toString(copyArray));
reOrderArray02(copyArray);
System.out.println("调整结果："+Arrays.toString(copyArray));
}
void test4() {
int[] array = {-1,3,-5,2,-4,6};
int[] copyArray = {-1,3,-5,2,-4,6};
System.out.println("原始数组："+Arrays.toString(array));
reOrderArray01(array);
System.out.println("调整结果："+Arrays.toString(array));
System.out.println("===========方法二：使用冒泡思想============");
System.out.println("原始数组："+ Arrays.toString(copyArray));
reOrderArray02(copyArray);
System.out.println("调整结果："+Arrays.toString(copyArray));
}
void test5() {
int[] array = {-1,2,-3,4,-5,6};
int[] copyArray = {-1,2,-3,4,-5,6};
System.out.println("原始数组："+Arrays.toString(array));
reOrderArray01(array);
System.out.println("调整结果："+Arrays.toString(array));
System.out.println("===========方法二：使用冒泡思想============");
System.out.println("原始数组："+ Arrays.toString(copyArray));
reOrderArray02(copyArray);
System.out.println("调整结果："+Arrays.toString(copyArray));
}
void test6() {
int[] array = {2,2,1,3,4,1};
int[] copyArray = {2,2,1,3,4,1};
System.out.println("原始数组："+Arrays.toString(array));
reOrderArray01(array);
System.out.println("调整结果："+Arrays.toString(array));
System.out.println("===========方法二：使用冒泡思想============");
System.out.println("原始数组："+ Arrays.toString(copyArray));
reOrderArray02(copyArray);
System.out.println("调整结果："+Arrays.toString(copyArray));
}
void test7() {
int[] array = {1};
int[] copyArray = {1};
System.out.println("原始数组："+Arrays.toString(array));
reOrderArray01(array);
System.out.println("调整结果："+Arrays.toString(array));
System.out.println("===========方法二：使用冒泡思想============");
System.out.println("原始数组："+ Arrays.toString(copyArray));
reOrderArray02(copyArray);
System.out.println("调整结果："+Arrays.toString(copyArray));
}
}
输出：
============================== test1 原始数组：null 数组为空 调整结果：null ===========方法二：使用冒泡思想============ 原始数组：null 数组为空 调整结果：null ============================== test2 原始数组：[] 数组为空 调整结果：[] ===========方法二：使用冒泡思想============ 原始数组：[] 数组为空 调整结果：[] ============================== test3 原始数组：[-2, 4, -6, 1, -3, 5] 调整结果：[1, -3, 5, -2, 4, -6] ===========方法二：使用冒泡思想============ 原始数组：[-2, 4, -6, 1, -3, 5] 调整结果：[1, -3, 5, -2, 4, -6] ============================== test4 原始数组：[-1, 3, -5, 2, -4, 6] 调整结果：[-1, 3, -5, 2, -4, 6] ===========方法二：使用冒泡思想============ 原始数组：[-1, 3, -5, 2, -4, 6] 调整结果：[-1, 3, -5, 2, -4, 6] ============================== test5 原始数组：[-1, 2, -3, 4, -5, 6] 调整结果：[-1, -3, -5, 2, 4, 6] ===========方法二：使用冒泡思想============ 原始数组：[-1, 2, -3, 4, -5, 6] 调整结果：[-1, -3, -5, 2, 4, 6] ============================== test6 原始数组：[2, 2, 1, 3, 4, 1] 调整结果：[1, 3, 1, 2, 2, 4] ===========方法二：使用冒泡思想============ 原始数组：[2, 2, 1, 3, 4, 1] 调整结果：[1, 3, 1, 2, 2, 4] ============================== test7 原始数组：[1] 调整结果：[1] ===========方法二：使用冒泡思想============ 原始数组：[1] 调整结果：[1] ============================== Process finished with exit code 0
————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。
Java基础 文章被收录于专栏
建立本人的Java基础技术栈积累库
查看6道真题和解析
同程旅行工作强度 19人发布
