首页 > 试题广场 > 调整数组顺序使奇数位于偶数前面
[编程题]调整数组顺序使奇数位于偶数前面
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

236个回答

添加回答
推荐
    /**
     * 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 回复(77)
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)
public class Solution {
    public void reOrderArray(int [] array) {
        int[] a = new int[array.length];
        //两个StringBuffer
        StringBuffer ji = new StringBuffer();
        StringBuffer ou = new StringBuffer();
        for (int i = 0; i < array.length; i++) {
            int val = array[i];
            if (val % 2 == 0) {
                ou.append(val);
            } else {
                ji.append(val);
            }
        }
        //拼接
        ji.append(ou);
        char[] chars = ji.toString().toCharArray();
        //重新赋值
        for (int i = 0; i < chars.length; i++) {
            array[i] = (int) Integer.parseInt(String.valueOf(chars[i]));
        }
    }
}
发表于 2019-05-12 21:53:14 回复(0)
//考虑到时间复杂度的问题,因此直接可以新建两个数组分别用于保存奇数和偶数,最后赋值给原数组
public class Solution {
    public void reOrderArray(int [] array) {
        int[] arr_odd=new int[array.length];
        int[] arr_even=new int[array.length];
        int odd=0,even=0;
        for(int i=0;i<array.length;i++){
            if(array[i]%2!=0){
                arr_odd[odd]=array[i];
                odd++;
            }
            else{
                arr_even[even]=array[i];
                even++;
            }
        }
        for(int j=0;j<array.length;j++){
            if(j<odd) array[j]=arr_odd[j];
            else array[j]=arr_even[j-odd];
        }
    }
}

//同样可以时间换空间,使用插入排序的思想

发表于 2019-05-08 15:56:13 回复(0)
两种思路:较简单一种:空间换时间,多创建几个Arraylist,分别存储奇数,偶数。然后在将两个合并。
我提供了两种方式:
法1:
//分别用odd,even来存储奇数与偶数,通过模2运算的结果为0还是1来决定是否的奇数还是偶数。
//调用ArrayList的add方法,存储数据。最后将even的值通过get函数填充到odd的中,
//具体代码见下:
ArrayList odd = new ArrayList(array.length); ArrayList even = new ArrayList(array.length);   for (int i = 0;i<array.length;i++){ boolean odd_f = array[i]%2==1;  if (odd_f){
            odd.add(array[i]);  }else {
        even.add(array[i]);  }
} for (int i = 0;i<even.size();i++){
    odd.add(even.get(i)); }  }

法2:对奇数偶数进行识别,并将它们的索引值记录在数组中,此时传递传输的值填充到新创建的数组中,然后在倒回去。挺傻的这个方法,不过有意思的地方在于,将索引值存储在数据内,个人的一个突破。
代码见下:
int length = array.length; boolean[] flag = new boolean[length]; int[] index = new int[length];  //对奇数还是偶数进行标记 //创建一个数组存储它们的索引值。 int j =0; for (int i = 0;i<length;i++){ if (array[i]%2==1){
        flag[i] = true;  index[i] = j++;  }
} for (int i = 0;i<length;i++){ if (array[i]%2==0){
        flag[i] = false;  index[i] = j++;  }
} int[] array1 = new int[length]; //将奇数先存储在index中, for (int i = 0;i<length;i++){
    array1[index[i]] = array[i]; } for (int i = 0;i<length;i++){
    array[i] = array1[i]; }



法三:互换位置,借鉴了插入排序(插入一个新值,与前方比较,然后决定插在那儿,互换位置)
应用在此题:1,何时插呢:当前值为偶数=》肯定要更改位置,所以需要找到下一个奇数如(2467),此时需要将7放置在2的位置,但246要整体后移,我通过一步一步交换位置来实现。觉得时间复杂度还是很高的。代码见下:

public void reOrderArray3(int[] array){ for (int i = 0;i<array.length;i++){ for (int j = i+1;j<array.length;j++){ if (!isOdd(array[i])&&isOdd(array[j])){ for (;j>i;j--){
                        exch(array,j,j-1);  } break;  }
        }
    }
} public boolean isOdd(int value){ return value%2==1; } public void exch(int[] array,int i,int j){ int t = array[i];  array[i] = array[j];  array[j] = t; }


发表于 2019-05-04 11:39:45 回复(1)
    // 奇数个数
    int oddCount = 0;
    for (int odd : array) {
        if (odd % 2 == 1)
            oddCount++;
    }

    int[] nums = array.clone();

    int i = 0;
    int j = oddCount;
    for (int num : nums) {
        if (num % 2 == 1) {
            array[i++] = num;
        } else {
            array[j++] = num;
        }
    }
发表于 2019-05-02 23:15:54 回复(0)
 public void reOrderArray(int [] array) {
  int temp=0;
        for(int i=1;i<array.length;i++) {
             if(array[i]%2!=0) {
                  temp=array[i];
                  for(int j=i-1;j>=0;j--) {
                       if((array[j]%2==0&&i==1)||(array[j]%2==0&&j==0)) {
                        array[j+1]=array[j];
                        array[j]=temp;
                        break;
                  }else if(array[j]%2==0) {
                        array[j+1]=array[j]; 
                   }else {
                        array[j+1]=temp;
                        break;
                   }
              }
          }
     }
}
发表于 2019-04-30 13:10:06 回复(1)
public class Solution {
    public void reOrderArray(int [] array) {
        if(array.length==1){
            return ;
        }
        for(int i=0;i<array.length;i++){
            if(array[i]%2==1){
                int temp = array[i];
                int j = i-1;
                while(j>=0&&array[j]%2==0)
                {
                    array[j+1] = array[j];
                    j--;
                }
                array[j+1] = temp;
            }
        }
    }
}
上面的也并不需要判断数组长度是否为0或1,for循环中会涉及到。其中注意相对位置不变,只需要向后移动位置即可,不可直接交换。自己举例子,例如【2,1,5,4,6,9,8,7,3】。
发表于 2019-04-23 22:09:52 回复(0)
/**
   遍历原数组,奇数存一个数组,偶数存一个数组 最后放回
*/
public class Solution {
    public void reOrderArray(int [] array) {
        if(array==null || array.length<2) return;
        int[] temp1 = new int[array.length]; // 奇数数组
        int[] temp2 = new int[array.length]; // 偶数数组
        int j = 0,k=0; // j 奇数当前位置  k 偶数当前位置
        for(int i =0;i<array.length;i++){
            if((array[i]&1)==1) temp1[j++] = array[i];
            else temp2[k++] = array[i];
        }
        for(int i=0;i<j;i++){  // 奇数数组中的数放回
            array[i] = temp1[i];
        }
        for(int i=0;i<k;i++){  // 偶数数组中的数放回
            array[i+j] = temp2[i];
        }
    }
}
发表于 2019-04-20 20:25:25 回复(0)

一开始想法是双指针法,但是这个会改变相对顺序,遂放弃。

其实想想还是很简单的,考虑这样写:

1. 遍历一遍数组,第一个出现的奇数在第一个位置,第二个在第二个位置,依次类推,遍历完之后,我们也就知道了奇数个数和奇数放置的位置。

2. 再遍历一遍数组,第一个出现的偶数在(奇数个数+0)这个位置,第二在在(奇数个数+1)这个位置,这次遍历完之后,偶数位置也确定。

3. 更新数组即可。。。

代码如下:

public void reOrderArray1(int [] array) {
        if (array.length < 2) return;
        //
        int[] t = new int[array.length];
        int index = 0;
        int index1 = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2==1){
                t[index++] = array[i];
            }
        }
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2==0){
                t[index+index1++] =  array[i];
            }
        }
        for (int i = 0; i < array.length; i++) {
                array[i] = t[i];
        }
    }
发表于 2019-04-20 17:38:49 回复(0)
//插入排序用法的延伸
public class Solution {
    public void reOrderArray(int [] array) {
        for (int index = 1; index < array.length; index++) {
            int subIndex = index;
            if((array[index]&1) == 1){
               int currentData = array[index]; // 是奇数就设置为等待插入的数据
                                                            //换到第一个偶数为止
                while ((subIndex > 0) && ((array[subIndex - 1] &1) ==0)) {

                array[subIndex] = array[subIndex - 1];

                subIndex--;

                }

                array[subIndex] = currentData; // 插入到合适的位置


            } 
        }
        
    }
}
发表于 2019-04-17 01:00:33 回复(0)
public class Solution {
    public void reOrderArray(int [] array) {
        int length = array.length;

        for (int i = 1; i < length; ++i) {
            if (array[i] % 2 == 1 && array[i - 1] % 2 == 0) {
                for (int j = i; j > 0; --j) {
                    if (array[j - 1] % 2 == 1)
                        break;
                    swap(array, j - 1, j);
                }
            }
        }
    }

    public void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
遍历,遇到奇数且前一位为偶数,则前移直到前面为奇数为止
发表于 2019-04-12 15:59:40 回复(0)
完全按照简单插入排序思想:
public class Solution {
    public void reOrderArray(int [] array) {
        for(int i = 0; i < array.length; i++){
            if(array[i] % 2 == 1){
                int temp = array[i];
                int j = i;
                while(j>0 && array[j-1]%2 == 0){
                    array[j] = array[j-1];
                    j--;
                }
                if(i != j)
                    array[j] = temp;
            }
        }
    }
}

发表于 2019-04-11 20:10:59 回复(2)
public void reOrderArray(int [] array) {
        for(int i=0;i<array.length;i++){
            if(array[i]%2==0){ //找到第一个偶数所在的位置 i
                int j;
                for(j=i;j<array.length;j++){
                    if(array[j]%2==1){ //找到偶数后第一个为奇数所在的位置 j
                        int temp=array[j];
                        for(int k=j;k>i;k--){  //在i<=pos<j之间的都为偶数,将区间内元素全部后移一位
                            array[k]=array[k-1];
                        }
                        array[i]=temp;  //将奇数置于i所在的位置
                        break;
                    }
                }
                if(j==array.length) break; //判断当未找到奇数时自动退出循环
            }
        }
    }

发表于 2019-04-10 21:35:08 回复(0)
//从头遍历,新开一个数组用来存偶数,然后再把偶数填入原数组: 
public void reOrderArray(int [] array) {  
    int[] temp=new int[array.length];  
    int c1=0;//偶数个数  
    int c2=0;//奇数个数 
     for(int i=0;iarray.length;i++){  
        if(array[i]%2==0){
                temp[c1++]=array[i]; //存偶数 
        }else{
                array[c2++]=array[i];//奇数直接挨个填 
        }
     }
     c1=0;  
     for(;c2array.length;c2++){//把偶数填入原数组 
        array[c2]=temp[c1++];
        }
}
编辑于 2019-04-10 13:07:46 回复(0)
1///////通过空间换时间,用两个数组分别接受奇数和偶数,然后将其连接到一块
import java.util.ArrayList;
public class Solution {
public void reOrderArray(int [] array) {
ArrayList<Integer> odd=new ArrayList<Integer>();   ///odd表示是奇数
ArrayList<Integer> even=new ArrayList<Integer>();  ///even表示是偶数

int j=0;

for(int i=0;i<array.length;i++){

if(array[i]%2==1){
odd.add(array[i]);
}else if(array[i]%2==0){
even.add(array[i]);
}
}

for(;j<odd.size();j++){
array[j]=odd.get(j);
}

for(int k=0;k<even.size();k++){
array[j+k]=even.get(k);
}


}
}
2///////////插入排序的思想
public class Solution {
    public void reOrderArray(int [] array) {
        ///相对位置不变,稳定性
        ///插入排序的思想
        int m=array.length;
        int k=0;     ////记录已经摆好位置的奇数的个数
        
        for(int i=0;i<m;i++){   ////等于说现在是比遍历
            if(array[i]%2==1){
                int j=i;
                while(j>k){
                    int temp=array[j];
                    array[j]=array[j-1];
                    array[j-1]=temp;
                    j--;
                }
                k++;
            }
            
        }
    }
}

编辑于 2019-03-30 10:42:33 回复(0)

int first = 0; //第一个偶数的位置 for(int i=0;i<array.length;i++){ if(array[i]%2==0){
        first = i; break;
    }
} //将第一个偶数与它之后的第一个奇数  整体后移移位  此时first后移一位 for(int i=first+1;i<array.length;i++){ if(array[i]%2==1){ int temp = array[i]; for(int j=i-1;j>first-1;j--){
            array[j+1] = array[j];
        }
        array[first] = temp;
        first++;
    }
}

发表于 2019-03-29 10:08:04 回复(0)

Java实现。空间复杂度O(1)

class Solution {
    public void reOrderArray(int [] array) { //插入排序思想
        int n = array.length;
        if (n <= 1) {
            return;
        }
        for (int i = 1; i < n; i++) {
            if (array[i]%2 == 1) {
                int j = i - 1;
                int value = array[i];
                while (j >= 0) {
                    if (array[j]%2 == 0) {
                        array[j+1] = array[j];
                        j--;
                    }else {
                        break;
                    }
                }
                array[j+1] = value;
            }
        }
    }
}
发表于 2019-03-28 13:41:09 回复(0)
类似插入排序

public class Solution {
    public void reOrderArray(int [] array) {
        if(array==null) return;
        
        int lastOddIndex = -1,    //已调整部分最后一个奇数的索引
            firstEvenIndex =-1;    //待调整部分第一个偶数的索引
        int cur = 0;
        
        //遍历数组array
        while(cur<array.length){
            //cur指向的数为奇数
            if(array[cur]%2==1){
                //前一个数刚好是已调整好的最后一个奇数
                if(cur-1==lastOddIndex){
                    lastOddIndex = cur;
                }
                else{
                     int odd = array[cur];
                    //将此奇数移到已调整部分的尾部
                     for(int i=cur;i>firstEvenIndex;i--)
                         array[i] = array[i-1];
                    firstEvenIndex++;
                    array[lastOddIndex+1] = odd;
                    lastOddIndex++;
                    
                }
            }
            
            else{
                if(firstEvenIndex==-1)
                    firstEvenIndex = cur;
            }
            cur++;
        }
        
        
        
    }
}
发表于 2019-03-25 11:50:28 回复(0)
public void reOrderArray(int [] array) {
        for(int i=1;i<array.length;i++) {
            int temp=array[i];
            //为奇数,往偶数前面插
            if(array[i]%2==1) {
                int j=i;
                while(j-1>=0&&array[j-1]%2==0) {
                    array[j]=array[j-1];
                    j--;
                }
                array[j]=temp;
            }
        }
    }
发表于 2019-03-24 17:07:02 回复(0)