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

绝地灬酷狼 2022-11-26 09:56 81阅读 0赞

## 题目描述 ##

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

## 过程 ##

我想到的还是比较基础的办法，用栈暂存，存完了再输出。

import java.util.Stack;
    
    public class Solution {
        public void reOrderArray(int [] array) {
            Stack<Integer> s1 = new Stack<Integer>(); //奇数栈
            Stack<Integer> s2 = new Stack<Integer>(); //偶数栈
            for(int i=0;i<array.length;i++){
                if(array[i]%2==1) s1.push(array[i]);
                else s2.push(array[i]);
            }
            for(int i=array.length-1;i>=0;i--){
                if (!s2.isEmpty()) {array[i]=s2.pop();continue;}
                if (!s1.isEmpty()) {array[i]=s1.pop();continue;}
            }
        }
    }

时间复杂度与空间复杂度都是O（n） 。

即为题解的

## 方法一：使用辅助数组 ##

函数的类型为void func\_name(array&)，想让我们不开辟额外数组来解决，使用in-place就地算法。但是如果空间要求不高的话，我们还是可以开挂的。也就是开辟个额外数组，接下来的做法就非常简单了，遍历一次数组，遇到奇数直接放入新开的数组中，再遍历一次数组，遇到偶数就继续放入新开的数组。最后再进行一次copy。

--------------------

## 方法二：in-place算法 ##

如果不开辟额外数组该怎么做呢？  
初始化操作：记录一个变量i表示已经将奇数放好的下一个位置，显然最开始i=0,表示还没有一个奇数放好。  
j 表示数组的下标，初始值为0， 表示从下标0开始遍历。

1.  如果遇到偶数，j++
2.  如果遇到奇数,假设位置为j，就将此奇数插入到i所指的位置，然后i往后移动一个位置，在插入之前，显然会涉及到数据的移动，也就是将\[i,j-1\]整体往后移动。
3.  直到整个数组遍历完毕，结束

public class Solution {
      public void reOrderArray(int[] array) {
          int len = array.length;
            if(len <= 1){ // 数组空或长度为1
                return;
            }
     
            int i = 0;
            while(i < len){
                int j = i + 1;
                if(array[i]%2 == 0){ // a[i]为偶数，j前进，直到替换
                    while(array[j]%2 == 0){ // j为偶数，前进
                        if(j==len-1)// i为偶数，j也为偶数，一直后移到了末尾，证明后面都是偶数
                             return;
                        j++;
                    }
                    // 此时j为奇数
                    int count = j-i;
                    int temp = array[i];
                    array[i] = array[j];
                    while(count>1){
                        array[i+count] = array[i+count-1];//数组后移
                        count--;
                    }
                    array[i+1] = temp;
                }
                i++;
            }
      }
    }

时间复杂度：O(n^2),假设数组中一般偶数在前，一半奇数在后，每次都要移动n/2个元素,是n^2/4  
空间复杂度：O(1)

--------------------

## 方法三：冒泡思想&插排思想&归并排序思想 ##

[https://blog.nowcoder.net/n/3c33d1b137d445089e779b1816f78c6c?f=comment][https_blog.nowcoder.net_n_3c33d1b137d445089e779b1816f78c6c_f_comment]

[https_blog.nowcoder.net_n_3c33d1b137d445089e779b1816f78c6c_f_comment]: https://blog.nowcoder.net/n/3c33d1b137d445089e779b1816f78c6c?f=comment