首页 > 试题广场 > 调整数组顺序使奇数位于偶数前面
[编程题]调整数组顺序使奇数位于偶数前面
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
推荐
    /**
     * 1.要想保证原有次序,则只能顺次移动或相邻交换。
     * 2.i从左向右遍历,找到第一个偶数。
     * 3.j从i+1开始向后找,直到找到第一个奇数。
     * 4.将[i,...,j-1]的元素整体后移一位,最后将找到的奇数放入i位置,然后i++。
     * 5.終止條件:j向後遍歷查找失敗。
     */
    public void reOrderArray2(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 j2 = j-1; j2 >=i; j2--) {
					a[j2+1] = a[j2];
				}
        		a[i++] = tmp;
        	}else{// 查找失敗
        		break;
        	}
        }
    }
    boolean isEven(int n){
    	if(n%2==0)
    		return true;
    	return false;
    }

编辑于 2015-08-18 23:19:51 回复(82)
// 使用两个队列 强行分离奇偶数
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
        public void reOrderArray(int [] array) {
            if(array.length == 0)
                return;
            Queue<Integer> queue1 = new LinkedList<>();
            Queue<Integer> queue2 = new LinkedList<>();
            for(int i = 0; i < array.length; i++){
                if(array[i] % 2 != 0)
                    queue1.offer(array[i]);
                else
                    queue2.offer(array[i]);
            }
            int i = 0;
            while (!queue1.isEmpty())
                array[i++] = queue1.poll();
            while (!queue2.isEmpty())
                array[i++] = queue2.poll();
        }
    }

发表于 2019-07-20 21:35:03 回复(0)
1.解法一:
按照自己的解题思路写的:😮😮😮😮 
public class Solution {
    public void reOrderArray(int [] array) {
            //新建一个数组:存放标记过的数字值(偶数)
            //原有的数组,将标记位置按顺序替换为其后的奇数
            //还需要判断奇数个数与偶数个数
            int n = array.length;
            if(n == 0) {
                System.out.println("输入错误!");
                return;
            }

            int[] newArray=new int[n];
            boolean[] isEven = new boolean[n];
            for(int i = 0;i < n; i++) {
                isEven[i] = false;
            }
            int z = 0;
            for(int i = 0;i < n; i++){
                if(array[i] % 2 == 0){
                    isEven[i] = true;
                    newArray[z] = array[i];
                    z++;
                }
            }
                int index = 0;
            for(int i = 0;i < n - 1; i++){
                if(isEven[i]){
                    for(int j = i + 1;j < n; j++){
                        if(isEven[j] != true){
                            array[i] = array[j];
                            isEven[j] = true;
                            index = i;
                            break;
                        }
                    }
                }
            }
        if(index != 0){
            int num = n - index - 1;
            for(int i = 0;i < num; i++){
                array[index + i + 1] = newArray[i];
            }
        }
    }
}
2.解法二:类似于冒泡排序😶😶
也是自己想到的第一个方法,但不知道为什么就中途放弃没用这个,现在来重写下。
public class Solution {
    public void reOrderArray(int [] array) {
           //近似于冒泡排序的解法
           //冒泡排序相关知识:n个元素比较n-1轮,每轮的次数为:n-轮数
           //冒泡排序原理:每相邻的两个数据进行比较,前者大于后者就交换位置,否则位置不变
            int n = array.length;
            if(n == 0) {
                System.out.println("输入错误!");
                return;
            }
            int temp;
                for(int i = 0;i < n; i++){
                    for(int j = n - 1;j > i; j--){
                        if(array[j] % 2 != 0 && array[j - 1] % 2 == 0){
                         //   swap(array[i],array[j]);
                            temp = array[j];
                            array[j] = array[j - 1];
                            array[j - 1] = temp;
                        }
                    }
                }
    }
}
编辑于 2019-07-13 21:37:00 回复(0)
public class Solution {
    public void reOrderArray(int [] array) {
       int len=array.length;
       int i=0,j=0;
       while(j<=i&&i<len){
           if(array[i]%2==1){
               for(int k=i;k>j;k--){
                   int tmp=array[k];
                   array[k]=array[k-1];
                   array[k-1]=tmp;
               }
               i++;
               j++;
           }
           else if(array[i]%2==0){
              i++; 
           }
       }
    }
}

发表于 2019-07-13 21:27:31 回复(0)

比较笨的思路,暂时是把问题解决了。开始之前要先找到数组的第一个偶数的位置p1,这里要注意数组越界,找到之后开始再以此位起点向后找到第一个奇数的位置,向前两两交换,偶数起点的标识p1+1指向下一位,继续直到结尾

    /**
     * 数组元素位置重排,奇数位于偶数前,并且,并且奇数或者偶数中的相对位置不能变
     * 选择排序
     * @param array
     */
    public static void reOrderArray(int[] array){
        int i = 0;
        while (i<array.length&&(array[i]&1)!=0){//防止数组索引越界
            i++;
        }
        int p1 = i;//代表第一次出现偶数的下标索引
        for (int j=i;j<array.length;j++){//j代表i之后第一次出现奇数的下标索引
            if ((array[j]&1)!=1){
                continue;
            }
            int tmp = array[j];
            for (int k=j;k>p1;k--){
                array[k] = array[k-1];
            }
            array[p1] = tmp;
            p1++;
        }
    }
发表于 2019-07-12 15:23:27 回复(0)
    //冒泡思想
    public void reOrderArray(int [] array) {
        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;
                }
            }
        }
    }

发表于 2019-07-10 21:05:19 回复(0)
//找到偶数后向后遍历找到技术的位置,然后利用arr[i+1] = arr[i]来将元素后移
public void reOrderArray(int [] array) {
int len = array.length;
int i=0,j=0,tmp = 0;
for (i=0;i<len;i++){
if(!isOdd(array[i])){
tmp = array[i];
for(j = i+1;j<len;j++){
if (isOdd(array[j])){
tmp = array[j];
break;
}
}
if (j==len)
break;
while (j>i){
array[j] = array[j-1];
j--;
}
array[i] = tmp;
}
}
}

private boolean isOdd(int num){
return (num&1)==0?false:true;
}
编辑于 2019-07-09 14:57:23 回复(0)
public class Solution {
    public void reOrderArray(int [] array) {
        for (int i = 0; i <array.length ; i++) {
            if (array[i]%2==0) //找到偶数位置
            {
                      //从当前偶数开始,找到下个奇数,进行直接插入排序
                for (int j = i; j <array.length ; j++) {
                    if (array[j]%2==1){
                        for (int l = j; l >i ; l--) {
                            int temp=array[l];
                            array[l]=array[l-1];
                            array[l-1]=temp;
                        }
                        break;
                    }
                }
            }
        }
    }
}
利用直接插入排序的思路,先遍历数组,如果出现偶数,从当前偶数开始,找到下个奇数,通过直接插入法,将这个奇数插入到偶数前面
发表于 2019-07-07 20:32:37 回复(1)
分享个递归版的吧,应该挺好理解的,只对最后一个是奇数的情况换位置,最后一个若是偶数不用做操作
public class Solution {
    public void reOrderArray(int [] array) {
        func(array, 0, array.length-1);
    }
    
    public void func(int[] array, int left, int right){
        if(left <= right){
             func(array, left, right-1);
             if(array[right]%2!=0){
                for(int i=right-1; i>= left; i--){
                if(array[i]%2==0){
                    int temp = array[i+1];
                    array[i+1] = array[i];
                    array[i] = temp;
                }
                else break;
            }
            }
        }
    }
}
发表于 2019-07-02 11:21:21 回复(0)
利用插入排序算法的稳定性,把奇数往前移动

public class Solution {
    public void reOrderArray(int [] array) {
        int insertNum;

        for (int i = 1; i < array.length; i++) {
            insertNum = array[i];

            int j = i - 1;

            while (j >= 0 && insertNum % 2 == 1 && array[j] % 2 == 0) {
                array[j + 1] = array[j];
                j--;
            }

            array[j + 1] = insertNum;
        }
    }
}
发表于 2019-06-27 10:21:17 回复(0)
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public void reOrderArray(int [] array) {

        //新建两个可变数组,各自存放奇偶数
       ArrayList<Integer>a1=new ArrayList<>();
       ArrayList<Integer>a2=new ArrayList<>();

        //遍历原数组并判断奇偶性,存放至两数组
        for (int i=0;i<array.length;i++) {
            if((array[i]&1)!=0) {
                a1.add(array[i]);
            } else {
                a2.add(array[i]);
            }
        }

        //将两数组的元素按照先奇后偶重新放入原数组
        for(int i=0;i<a1.size();i++) {
            array[i]=a1.get(i);
        }
        for(int j=0;j<a2.size();j++) {
            array[a1.size()+j]=a2.get(j);
        }    
    }    
}

发表于 2019-06-27 10:07:36 回复(0)
构造2个ArrayList用来存储奇数与偶数,简单快捷,用空间换时间
import java.util.ArrayList;
public class Solution {
public void reOrderArray(int [] array) {
if (array == null) {
return;
}
ArrayList<Integer> odd = new ArrayList<Integer>();
ArrayList<Integer> even = new ArrayList<Integer>();
for (int num : array) {
if(num % 2 == 1) {
odd.add(num);
}else {
even.add(num);
}
}
odd.addAll(even);
for(int i = 0;i < array.length;i++) {
array[i] = odd.get(i);
}
}
}
编辑于 2019-06-19 19:20:35 回复(0)


public class Solution {
    class ListNode {
        private int val;
        private ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
   //如果大家有更简便的方法,欢迎交流 
    public void reOrderArray(int [] array) {
        if(array == null || array.length == 0) return;
        ListNode eHead = new ListNode(0), oHead = new ListNode(0);
        ListNode et = eHead, ot = oHead;
        for(int i = 0; i < array.length; i++) {
            if(array[i] % 2 == 0) {
                et.next = new ListNode(array[i]);
                et = et.next;
            } else {
                ot.next = new ListNode(array[i]);
                ot = ot.next;
            }
        }
        ot.next = eHead.next;
        int j = 0;
        while((oHead = oHead.next) != null) {
            array[j++] = oHead.val;
        }
    }
}

发表于 2019-06-14 22:30:20 回复(0)
 
使用额外空间

import java.util.ArrayList;

public class Solution {
    public void reOrderArray(int [] array) {
        if(array.length == 0){
            return;
        }
        
        ArrayList<Integer> oddNum = new ArrayList();
        ArrayList<Integer> evenNum = new ArrayList();
        int i=0;
        for(; i<array.length; i++){
            if(array[i] % 2 == 1){
                oddNum.add(array[i]);
            } else {
                evenNum.add(array[i]);
            }
        }
        i = 0;
        for(; i<oddNum.size(); i++){
            array[i] = oddNum.get(i);
        }
        i = 0;
        for(; i<evenNum.size(); i++){
            array[i+oddNum.size()] = evenNum.get(i);
        }
    }
}

发表于 2019-06-12 11:05:19 回复(0)
public class Solution {
    public void reOrderArray(int [] array) {
        if (array.length == 0 || array == null) return;
        int oddCount = 0;
        for (int num: array)
            if (!isEven(num))
                oddCount++;
        int odd = 0, even = oddCount;
        int[] temp = new int[array.length];
        for (int num: array) {
            if (isEven(num))
                temp[even++] = num;
            else
                temp[odd++] = num;
        }
        for (int i = 0; i < array.length; i++)
            array[i] = temp[i];
    }
    
    public boolean isEven(int num) {
        return (num & 1) == 0;
    }
}

发表于 2019-06-06 02:36:04 回复(0)
import java.util.*;
public class Solution {
    public void reOrderArray(int [] array) {
        ArrayList<Integer> odd = new ArrayList<>();
        ArrayList<Integer> even = new ArrayList<>();
        for(int i=0; i<array.length; i++){
            if ((array[i]%2)!=0){
                odd.add(array[i]);
            }else{
                even.add(array[i]);
            }
        }
        
        odd.addAll(even);
        for(int i=0; i<odd.size();i++){
            array[i]=odd.get(i);
        }
        
            
    }
}

发表于 2019-06-02 17:14:13 回复(0)
渣渣方法:
public class Solution {
    public void reOrderArray(int [] array) {
        int i=0;
        while(i<array.length){
            if(array[i]%2 == 1)
                i++;
            else {
                int j=i+1;
                while(j<array.length && array[j]%2 == 0)
                    j++;
                if(j>=array.length)
                    break;
                int temp;
                temp = array[j];
                while(j> i){
                    array[j] =array[j-1];
                    j--;
                }
                array[i] = temp;
                i = i+1;
            }
        }
    }
}

发表于 2019-05-29 21:53:55 回复(0)
典型的冒泡排序
public class Solution {
    public void reOrderArray(int [] array) {
        //有没有原位算法,不去重新建一个临时数组
        //类似冒泡算法
        //相邻元素如果是前偶后奇,那么就交换位置,len - 1轮下来必定全部安排的明明白白
        for(int i = 0; i < array.length - 1; i++){
            for(int j = array.length - 1; j > 0; j--){
                if(array[j] % 2 != 0 && array[j - 1] % 2 == 0){
                    int temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                }
            }
        }
    }
}

发表于 2019-05-25 16:00:48 回复(0)
public class Solution {
    public void reOrderArray(int [] array) {
        for(int i=0;i<array.length;i++){
            if(array[i]%2==0){
                for(int j=i;j<array.length;j++){
                    if(array[j]%2==1){
                        int temp = array[j];
                        for(int k=j;k>i;k--){
                            array[k]=array[k-1];
                        }
                        array[i]=temp;
                        break;
                    }
                }
            }
        }
    }
}
发表于 2019-05-20 17:59:21 回复(0)
public void reOrderArray(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        int length = array.length;
        int i = 0;
        int j = length - 1;
        int[] tmp = new int[length];
        int count = 0;
        for (int value : array) {
            if ((value & 1) == 0) {
                tmp[j--] = value;
                ++count;
            } else {
                tmp[i++] = value;
            }
        }
        int end = ((count & 1) == 0) ? length - (count >> 1) : length - (count >> 1) - 1;
        j = length - 1;
        int index = length - count;
        for (int k = index; k < end; k++) {
            tmp[k] ^= tmp[j];
            tmp[j] ^= tmp[k];
            tmp[k] ^= tmp[j--];
        }
        System.arraycopy(tmp, 0, array, 0, length);
    }
发表于 2019-05-16 17:22:33 回复(0)