剑指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

————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。