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

Reply Share

问题描述：输入一个整数数组，实现一个函数调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

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

一种基础的思路：先不考虑时间复杂度，从开开始遍历数组，当当前位置为偶数时，将位于该元素后面的数字整体向前移动一位，同时将该节点的数字放在数组的最后位置，每遇到一个偶数需要移动O(n)个数字，时间复杂度为O(n2).

现给出另一种思路，在扫描的过程中，如果发现有偶数在奇数的前面，则交换他们的位置，交换之后就符合要求了。基于上述分析，给出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void ReorderOddEven(int *pData,int length){
    if(pData==NULL ||length==0)
        return;
    int *pBegin=pData;
    int *pEnd=pData+length-1;

    while(pBegin<pEnd){
        while(pBegin<pEnd && (*pBegin & ox1)!=0){  //找到第一个偶数
                 pBegin++;
        }
        while(pBegin<pEnd && (*pEnd & ox1)==0){     //找到第一个奇数
            eEnd--;
        }

     if(pBegin<pEnd){       //交换奇数和偶数的位置
        int temp=*pBegin;
        *pBegin=*pEnd;
        *pEnd=temp;
     }
    }
}

现在如果要对上述算法进行扩展，比如：将题目简单的修改一下，将数组按大小分成两部分？将负数放在前面，正数放在后面？为了将代码进一步抽象，可以给出一个模式，修改函数ReorderOddEven中的判断标准，其他的逻辑框架不需要改动。有以下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void ReorderOddEven(int *pData,int length,bool (*func)(int)){
    if(pData==NULL ||length==0)
        return;
    int *pBegin=pData;
    int *pEnd=pData+length-1;

    while(pBegin<pEnd){
        while(pBegin<pEnd && !func(*pBegin)){  
                 pBegin++;
        }
        while(pBegin<pEnd && func(*pEnd)){     
            eEnd--;
        }

     if(pBegin<pEnd){       
        int temp=*pBegin;
        *pBegin=*pEnd;
        *pEnd=temp;
     }
    }
}

bool isEven(int n){
    return (n & 1)==0;
}

另外对给出的第一个算法，这里在实现题目要求时，奇偶数的相对顺序发生了变化，如果要使得在重排后奇偶数的相对顺序不变。可以借用栈或队列等容器来实现，当然，这意味着额外的内存开销，最差的情况为O(n),其代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void reOrderOddEven(vector<int> &array) {
      
      if(array.size()<=0)            //异常处理
          return;
      
      vector<int> odds,evens;
      unsigned int i;
      
      for(i=0;i<array.size();i++){   //分别将奇数和偶数存入一个vector容器中
          if((array[i]&0x1)!=0)
             odds.push_back(array[i]);
          if((array[i]&0x1)==0)
             evens.push_back(array[i]);
      }
      
      for(i=0;i<odds.size();i++)   //将奇数和偶数分别存入array中
          array[i]=odds[i];
      int k=i;
      for(i=0;i<evens.size();i++)
          array[k++]=evens[i];        
  }

1