本文主要是介绍剑指offer 题21—调整数组顺序是奇书位于偶数前面，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
调整数组顺序是奇书位于偶数前面
题目
输入一个整数数组，实现一个函数来调整该数组中的数字的顺序，使得所有计数位于数组的前半部分，所有偶数位于数组的后半部分
初步分析
最简单的办法当然是从头扫描这个数组，每碰到一个偶数，就该数放到最后面，也就是这个数后面的数都要向前移动。
由于每碰到一个偶数就要移动O(n)个数字，总的时间复杂度为O(n^2)。
更好的办法
既然数组中只有两类数字——非奇即偶。那么每当发现有偶数出现在奇数前面时，就交换它们的顺序，这样岂不是可以了？
因此，需要维护两个指针：
第一个指针，初始化时指向第一个数字，只能向后移动。
第二个指针，初始化时指向最后一个数字，只能向前移动。
两指针相遇之前，如果第一个指针是偶数，而第二个指针是奇数，那么就将它们的位置交换
举例
输入数组：{1，2，3，4，5}
过程:
1、开始，第一个指针指向1，第二个指针指向5
2、由于1是奇数，因此第一个指针向后移动，直到指向偶数2。
3、此时，因为第二个指针指向5，因此交换，并且两者都进行移动。
4、然后继续直到两者相遇
图解：
因此可以得到以下代码：
void ReorderOddEven(int* pData,unsigned int length)
{if(pData==nullptr || length==0)return;int* pBegin=pData;int* pEnd=pData+length+1;while(pBegin<pEnd){//向后移动pBegin 直到它指向偶数while(pBegin<pEnd && (*pBegin & 0x1)!=0)pBegin++;//向前移动pEnd 直到指向奇数while(pBegin<pEnd && (*pEnd & 0x1)==0)pEnd--;if(pBegin<pEnd){int temp=*pBegin;*pBegin=*pEnd;*pEnd=tmp;}}
}
拓展——模块化的处理
上面的问题解决了，似乎也很完美，但是如果又有类似得问题如何？
问：如果改成数组分为正负两部分，负数在非负数前面，怎么处理?
答：重新定义一个新函数，只需要更改第二个和第三个while循环得判断条件就好了再问：那如果又是分成两部分，一部分能被3整除，放前面，一部分不能被3整除，放后面，又怎么办呢？
再答：还是重新定义一个新函数，再更改… 打断：停停停，就没有更好得办法了？
我们看上面得问题，其实回答并没有错，因此就是只需要改一下条件就好了。
但上面错就错在这个只需要上面了
既然只是判断条件有需要改，那么我何必要每次都重复写其它一样的代码呢？
为何不将需要判断的条件封装起来，这样剩下的代码不就可以重用了？
没错，这正式提问者所想得到的答案！
因此我们只需要引入一个函数指针，将上面代码拆分成逻辑和运算两部分就好了。这样每次只需要重写逻辑函数，而不必重复一大段运算了，重用性提高了很多
void ReorderOddEven(int* pData,unsigned int length,bool (*func)(int))
{if(pData==nullptr || length==0)return;int* pBegin=pData;int* pEnd=pData+length+1;while(pBegin<pEnd){//向后移动pBegin 直到它指向偶数while(pBegin<pEnd && !func(*pBegin))pBegin++;//向前移动pEnd 直到指向奇数while(pBegin<pEnd && func(*pEnd) )pEnd--;if(pBegin<pEnd){int temp=*pBegin;*pBegin=*pEnd;*pEnd=tmp;}}
}bool IsEven(int n)
{return (n&0x1)==0;
}
————————————————————————————————————————————————————————
参考书籍:《剑指offer》
这篇关于剑指offer 题21—调整数组顺序是奇书位于偶数前面的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
