本文共 2210 字，大约阅读时间需要 7 分钟。

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

思路：这是一个数组的问题，在数据结构与算法的题目中，数组是很常见的题目，数组里面的元素通常都是数字，数组题目虽然用到了数组，但数组仅仅是一个载体，关键还是考察算法的理解和使用。123456à135246,本题与剑指offer中的题目不同，剑指offer中只要求奇数在偶数的前面，而不要求保持奇数、偶数的相对位置，因此只需要使用p1,p2两个指针分别从前面和后面开始遍历数组，当p1是偶数，p2是奇数时进行交换即可，直到p2<=p1，于是时间复杂度为O(n)。但是这里要求分类后奇数、偶数之间保持相对位置不变，于是需要采取不同的方法。

方法1：使用额外的空间复杂度，先遍历得到奇数和偶数的数目，然后建立数组，将奇数和偶数分别放入到两个数组中去，然后将两个奇数数组连接到偶数数组的前面即可。空间复杂度为O(n)，时间复杂度为O(n)

public class Solution {    public voidreOrderArray(int [] array) {        int[] odd = newint[array.length];        int[] even =new int[array.length];        intevenCount=0;        int oddCount=0;        for(inti=0;i

方法2：以空间换时间，从后往前扫描，遇到奇数就保存到temp，遇到偶数就赋值到temp的末尾所在位置（就相当于移动了），直到到达数组开头，最后把temp反序写在开头。public class Solution {    public static void reOrderArray(int[] array) { if (array == null || array.length == 0) return; int tmp = 0; for (int i = 0, j = 0; i < array.length && j < array.length; i++) { if (array[i] % 2 != 0) { tmp = array[i]; for (int k = i; k > j; k--) { array[k] = array[k - 1]; } array[j] = tmp; j++; } } }}

方法3：类似于插入排序，不用借助其他的数据结构，所以空间复杂度为O（1），时间复杂度为O（N^2）虽然时间复杂度较大，但是原理很简单，而且没有额外的空间复杂度，可以作为面试时写代码时的解决方案。从第2个数开始，向下遍历，只关注奇数的数字，如果某个数是奇数，那么就希望将它调整到前面去，即跳过前面的偶数，移动和奇数放在一起，即本奇数array[j]要插入到前面合适的位置(所有偶数的前面)，于是从本位置i开始向前遍历，j=i；j--,判断array[j]是否是偶数，如果是偶数就向后移动一位，直到前面的数是奇数时就是target=array[i]应该放的位置。如此对整个数组进行遍历，每遍历一个元素都可能移动n个元素，因此总的时间复杂度是O(n^2);public void reOrderArray(int [] array) {        for(int i=1;i
   
    = 1 && array[j-1] % 2 == 0){                    array[j] = array[j-1];                    j--;                }                array[j] = target;            }        }    }
   

方法4：使用归并排序法。要将数组分成两部分，可以使用快速排序的思想，但是快排是不稳定的，不能保证元素相对位置不变，堆排序也是不稳定的，稳定高效的排序算法只有归并排序，归并排序的时间复杂度也较低。时间复杂度O(nlogn)，空间复杂度O(1)public class Solution {    public voidreOrderArray(int [] array) {        //注释的部分使用快速排序的算法，很明显快速排序是不稳定的，这里需要用归并排序        /*        if(array.length== 0){            return;        }        int high =array.length - 1;        int low = 0;        while(low