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

本文主要是介绍剑指Offer14 调整数组顺序使奇数位于偶数前面，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

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

分析：

这个题最简单也是最暴力的方法就是从前往后遍历，遇到偶数就将其后面的数往前移动一个位置，然后把当前的这个放入数组的最后。当然他的时间复杂度就很大了，首先是遍历了整个数组，其次移动每一个数字，所以他的时间复杂度是O(n2)。

那么接下来我就想怎么能优化一下，前面的都是奇数，后面的都是偶数。那是不是就可以定义两个指针，一个p1指向头结点，一个p2指向最后一个结点，如果p1是偶数，p2是奇数的话，那么就让他们交换。

这么一分析是不是就挺简单了。

下面看我写的代码：

void ReorderOddEven(int *num,int length)
{if(num == NULL || length <0)return ;int *p1 = num;int *p2 = num+length-1;while(p1 < p2){if(*p1 & 0x1 == 1)p1++;else{while(*p2 & 0x1 == 0 && p1 < p2)p2--;Swap(p1,p2);p1++;p2--;}}
}

这是剑指Offer上的优化之后的代码：

void ReorderOddEvenYouHua(int *num,int length)
{if(num == NULL || length < 0)return ;int *p1 = num;int *p2 = num + length -1;while(p1 < p2){while(p1 < p2 && (*p1 & 0x1 == 1))p1++;while(p1 < p2 && (*p2 & 0x1 == 0))p2--;if(p1 < p2){Swap(p1,p2);p1++;p2--;}}
}

这篇关于剑指Offer14 调整数组顺序使奇数位于偶数前面的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---