第十三题 调整数组顺序使奇数位于偶数前面

题目描述

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

一、方法一

一、分析

使用冒泡排序算法的思想

二、代码

class Solution {
public:
    void reOrderArray(vector<int> &array) {
      for(int i=0;i<array.size();i++)
          {
          for(int j=array.size()-1;j>0;j--)
              {
              if(array[j]%2==1&&array[j-1]%2==0)
                  {
                  swap(array[j],array[j-1]);
              }
          }
      }
    }
};

二、方法二

一、分析

思路：参考快速排序,使用两个指针来遍历数组

• i++往前走碰到偶数停下来，j = i+1
• 若 a[j]为偶数，j++前进，直到碰到奇数
  • a[j]对应的奇数插到a[i]位置，j经过的j-i个偶数依次后移
• 如果j==len-1时还没碰到奇数，证明i和j之间都为偶数了，完成整个移动
• 

  二、代码

int i = 0;
        while(i<array.length)
        {
            int j = i+1;
            if(array[i]%2==0)
            {
                while(array[j]%2==0)
                {
                    if(j==array.length-1)
                    {
                        return;
                    }
                    j++;    
                }
                int n = j-i;
                int temp = array[i];
                array[i] = array[j];
                array[i+1] = temp;
                while(n>1)
                {                                                
                    array[i+n] = array[i+n-1];                        
                    n--;                        
                }    
                array[i+1] = temp;
            }
            i++;
        }

三、方法三

采用插入排序算法,和方法二类似

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) {//j >= k+1
                    int tmp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = tmp;
                    j--;
                }
                k++;
            }
        }
    }
}