一、题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
二、解题思路
2.1 基本解法
如果不考虑时间复杂度，最简单的思路应该是从头扫描这个数组，每碰到一个偶数时，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，这时把该偶数放入这个空位。由于每碰到一个偶数就需要移动O(n)个数字，因此总的时间复杂度是O(n2)。
2.2 高效解法
这里可以参考快速排序的思想，快速排序的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
因此，我们可以借鉴快速排序的思想，通过设置两个指针来进行交换操作，从而减少移动次数，提高效率：
Step1.第一个指针初始化时指向数组的第一个数字，它只向后移动；
Step2.第二个指针初始化时指向数组的最后一个数字，它只向前移动。
Step3.在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，我们就交换这两个数字。
下图展示了调整数组{1,2,3,4,5}使得奇数位于偶数前面的过程：
代码如下：
#include<iostream>using namespace std;void ReorderOddEven(int array[],int length){ if(array==NULL || length==0) return; int begin=0; int end=length-1; while(begin<end) { //向后移动指针begin，直到遇到偶数 while(begin<end && array[begin]%2!=0) begin++; //向前移动指针end，直到遇到奇数 while(begin<end && array[end]%2==0) end--; if(begin<end) { //交换偶数和奇数 int temp=array[begin]; array[begin]=array[end]; array[end]=temp; } }}int main(){ int N,a[100]; cin>>N; for(int i=0;i<N;i++) cin>>a[i]; ReorderOddEven(a,N); for(int i=0;i<N;i++) cout<<a[i]<<" "; cout<<endl; return 0;}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/162921.html
