21-调整数组顺序使得奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分。

第一种 使用额外数组

使用O(n)的额外空间，遍历两次。

 public void reOrderArray(int [] array) {
        if(array == null || array.length < 2){
             return;
         }
         int[] backup = Arrays.copyOf(array,array.length);
         int j = 0;
         for(int i = 0;i < array.length; i++) {
             if(backup[i] % 2 == 1){
                 array[j++] = backup[i];
             }
         }
        for(int i = 0;i < array.length; i++) {
            if(backup[i] % 2 == 0){
                array[j++] = backup[i];
            }
        }
    }

第二种 使用首尾指针

可以使用快速排序的思想，使用两个指针，分别指向数组头尾，移动头尾指针，当头指针遇到一个偶数，停下，当尾指针遇到一个奇数，停下，双方互换，直到两指针相遇。

 public void reOrderArray(int [] array) {
        if (array == null || array.length < 1) {
            return;
        }
        int i = 0;
        int j = array.length - 1;
        while (i < j) {
            while(!isEven(array[i]) && i <= array.length-1){
                i++;
            }
            while (isEven(array[j]) && j >= 0) {
                j--;
            }
            if(i < j){
                swap(array, i, j);
            }else{
                break;
            }
        }
        System.err.println(Arrays.toString(array));
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    /**
     * 判断是否是偶数
     * @param num
     * @return
     */
    private boolean isEven(int num) {
        return (num & 1) == 0;
    }

第三种 使用快慢指针

慢指针始终指向的是待交换的元素，可能是奇数也可能是偶数，但在慢指针之前的一定是奇数。

快指针用来遍历整个数组，遇到奇数就和慢指针进行交换。

这种方法也可以用在快排上。

public int[] exchange(int[] nums) {
 if (nums == null || nums.length <= 1) {
            return nums;
        }
        int slow = 0,fast =0;
        while (fast < nums.length) {
            if(nums[fast] % 2 == 1){//发现奇数就与slow交换
                swap(nums, fast, slow); 
                slow++;
            }
            fast++;
        }
        return nums;
    }
    public static void swap(int[] numbers, int i, int j) {
        int tmp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = tmp;
    }

题目变种

牛客网上的对应的题目:

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

增加了相对位置不变的要求。上面的第一种方法依然适用。还可以使用稳定的排序算法-插入算法的思想。

插入算法

发现奇数就与前面的偶数调换。

 public void reOrderArray(int [] array) {
        if (array == null || array.length < 1) {
            return;
        }
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0 ; j--) {
                if (!isEven(array[j]) && isEven(array[j-1])) {
                    swap(array, j, j-1);
                }
            }
        }
        System.err.println(Arrays.toString(array));
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    /**
     * 判断是否是偶数
     * @param num
     * @return
     */
    private boolean isEven(int num) {
        return (num & 1) == 0;
    }