【剑指offer】调整数组顺序使奇数位于偶数前面

素颜马尾好姑娘i 2022-04-08 14:19 122阅读 0赞

# 调整数组顺序使奇数位于偶数前面 #

## 题目描述 ##

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

## 解题思路 ##

### 方法一：相邻交换 ###

public class Solution {
        
        public void reOrderArray(int[] array) {
        
           for(int i = 0;i < array.length-1; i++){
        
                for(int j = 0;j < array.length-1-i; j++){
        
                    if(array[j] % 2 == 0 && array[j+1] % 2 ==1 ){
        
                        int tmp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = tmp;
                    }
                }
            }
        }
    }

### 方法二： ###

*  i从左向右遍历，找到第一个偶数。
 *  j从i+1开始向后找，直到找到第一个奇数。
 *  将\[i,…,j-1\]的元素整体后移一位，最后将找到的奇数放入i位置，然后i++。
 *  终止条件：j向后遍历查找失败。

public class Solution {
        
        public void reOrderArray(int[] a) {
        
            if(a == null || a.length == 0)
                return;
            int i = 0,j;
            while(i < a.length){
        
                while(i < a.length && !isEven(a[i]))
                    i++;
                j = i+1;
                while(j < a.length && isEven(a[j]))
                    j++;
                if(j < a.length){
        
                    int tmp = a[j];
                    for (int k = j-1; k >= i; k--) {
        
                        a[k+1] = a[k];
                    }
                    a[i++] = tmp;
                }else{
        // 查找失敗
                    break;
                }
            }
        }
        
        public boolean isEven(int n){
        
            if(n%2==0)
                return true;
            return false;
        }
    }