题目描述

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

代码实现

public class Solution {
    public void reOrderArray(int [] array) {
        //第一种思路：新建一个数组 先放奇数 再放偶数 复杂度O（2n）
        int[] a = new int[array.length];
        int i = 0,j = 0;
        for(i = 0;i < array.length;i++){
            if(array[i] % 2 == 1)
                a[j++] = array[i];
        }
        for(i = 0;i < array.length;i++){
            if(array[i] % 2 == 0)
                a[j++] = array[i];
        }
        for(i = 0;i < array.length;i++){
            array[i] = a[i];
        }
        
/*      //第二种思路：类似冒泡算法 前偶后奇数就交换 复杂度O（n²）
        for(int i = 0;i < array.length;i++){
            for(int j = array.length-1;j > i;j--){
                if(array[j] % 2 == 1 && array[j-1] % 2 == 0){
                    int temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                }
            }
        }
        
        //第三种思路：类似插入排序 当前数是奇数就往前找 遇到偶数就往它前面插 复杂度O（n²）
        //插入有两种写法。一种是基于交换的，看起来很像冒泡，琢磨一下就会发现区别的
        for (int i = 1; i < array.length; i++){
            if (array[i] % 2 == 1){
                for (int j = i; j > 0; j--){
                    if (array[j - 1] % 2 == 0){
                        int temp = array[j];
                        array[j] = array[j - 1];
                        array[j - 1] = temp;
                    }
                }
            }
        }
        
        //第四种思路：快速排序变种 不稳定 不能通过所有的测试用例
        int low = 0,high = array.length - 1;
        while(low < high){
            while(low < high && array[low] % 2 == 1){
                low ++;
            }
            while(low < high && array[high] % 2 == 0){
                high --;
            }
            int temp = array[low];
            array[low] = array[high];
            array[high] = temp;
        }
*/
    }
}

主要思路

主要熟悉几种排序写法（冒泡，插入，快排等）