题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，
所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
思路一：从头扫描这个数组，每碰到一个偶数时，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，这时把该偶数放入这个空位。由于碰到一个偶数，需要移动O(n)个数字，只是这种方法总的时间复杂度是O(n２)，不符合要求!
思路二：采用依次遍历数组的方式，从数组的第一个元素开始，判断元素是否是奇数，如果是则将它保存到另一个空数组中，当遍历完整个数组中的奇数时，就将原数组中的所有偶数按照原顺序依次保存到数组的末尾。空间复杂度太大，时间复杂度也不满足要求。
思路三：维护两个指针（头指针和尾指针），一个指针指向数组的第一个数字（头指针），向后移动；一个指针指向最后一个数字（尾指针），向前移动。如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字。（类似于快速排序）
本方法通过头尾指针往中间扫描，一次遍历完成所有的奇数和偶数的重新排列，时间复杂度是O(n)，符合题目要求。（使用）
思路四：还记得快速排序的过程，设置一个主元，依次遍历元素并使得它和主元进行比较，并按照要去交换元素的位置。
该问题使用两个指针i和j，一个指针指向数组的第一个元素的前一个位置，称为后指针i，向右移动；另一个指针指向数组的第一个元素，称为前指针j，向右移动。前后指针都向后移动的过程中，如果前指针j指向的元素是奇数，则令后指针i向右移动一位，然后交换i和j两个指针所各自指向的元素。我们最终的目的是让奇数排在数组的前面，偶数排在数组的后面，所以i指针指向的是奇数，j指针指向的是偶数。因此，当j指针指向的是奇数时，不正常，让i++，然后交换i，j指针所指向的数。
这种一前一后同时向右扫描的解法，也是一次遍历奇数和偶数的重新排列，时间复杂度是O(n)，符合题目要求。（使用）
总结：虽然思路三和四都实现了，但是它们的输出却有点差别。
//奇偶数排序
//思路三
#include <iostream>
using namespace std;
//判断是否为奇数
bool IsOddNumber(int data)
{
if (data % 2 == 1)//
return true;
else
return false;
//return (data & 1) == 1;
}
//奇数和偶数的互换
void OddEvenSort(int *pData, unsigned int length)
{
if (pData == NULL || length == 0)
{
return;
}
int *first = pData;
int *second = pData + length - 1;
while (first < second)
{
//如果头指针指向奇数，正常
if (IsOddNumber(*first) == 1)
{
first++;
}
else if (IsOddNumber(*second) == 0) // 如果尾指针指向偶数，正常
{
second--;
}
else//如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字
{
int temp = *second;
*second = *first;
*first = temp;
}
}
}
int main()
{
int a[8] = { 1, 6, 3, 10, 4, 7, 2, 5 };
OddEvenSort(a, 8);
for (int i = 0; i < 8; i++)
{
cout << a[i] << " ";
}
cout << endl;
return 0;
}
//输出：1 5 3 7 4 10 2 6
//思路四
#include <iostream>
using namespace std;
//判断是否为奇数
bool IsOddNumber(int data)
{
if (data % 2 == 1)//奇数
return true;
else
return false;
//return (data & 1) == 1;
}
//奇数和偶数互换
void CddEvenSort2(int data[], int low, int high)
{
int i = low - 1;
for (int j = low; j < high; j++)
{
if (IsOddNumber(data[j]) == 1)//偶数
{
i++;
swap(data[i], data[j]);
}
}
swap(data[i + 1], data[high]);
}
int main()
{
int a[8] = { 1, 6, 3, 10, 4, 7, 2, 5 };
CddEvenSort2(a, 0, 7);
for (int i = 0; i < 8; i++)
{
cout << a[i] << " ";
}
cout << endl;
return 0;
}
//输出：1 3 7 5 4 6 2 10
