奇偶调序
奇偶调序
题目描述：
输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
分析和解法：
最容易想到的办法是从头扫描这个数组，每碰到一个偶数，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，然后把该偶数放入这个空位。由于每碰到一个偶数，需要移动 O(n) 个数字，所以这种方法总的时间复杂度是 O(n^2) 。
事实上，若把奇数看做是小的数，偶数看做是大的数，那么按照题目所要求的奇数放在前面偶数放在后面，就相当于小数放在前面大数放在后面，联想到快速排序中的 partition 过程，不就是通过一个主元把整个数组分成大小两个部分么，小于主元的小数放在前面，大于主元的大数放在后面。
而 partition 过程有以下两种实现：
- 一头一尾两个指针往中间扫描，如果头指针遇到的数比主元大且尾指针遇到的数比主元小，则交换头尾指针所分别指向的数字；
- 一前一后两个指针同时从左往右扫，如果前指针遇到的数比主元小，则后指针右移一位，然后交换各自所指向的数字。
类似这个 partition 过程，奇偶排序问题也可以分别借鉴 partition 的两种实现解决。
解法一：暴力挪移
最容易想到的办法是从头扫描这个数组，每碰到一个偶数，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，然后把该偶数放入这个空位。由于每碰到一个偶数，需要移动 O(n) 个数字，所以这种方法总的时间复杂度是 O(n ^ 2) 。
源代码如下：
#include <iostream>
using namespace std;
void Move(int a[], int n, int i)
{
int temp;
temp = a[i];
int j;
for (j = i; j < n - 1; j++)
a[j] = a[j + 1];
a[j] = temp;
}
int main()
{
int a[100];
int n = 0;
while(cin.peek() != '\n') cin >> a[n++];
for (int i = 0, m = n; i < n && m >= 0; i++)
{
if (a[i] % 2 == 0)
Move(a, m--, i--);
else
continue;
}
for (int j = 0; j < n; j++)
cout << a[j] << " " ;
cout << endl;
return 0;
}
分析：时间复杂度为 O（n ^ 2）。
解法二：首尾指针
维护两个指针（头指针和尾指针），一个指针指向数组的第一个数字（头指针），向后移动；一个指针指向最后一个数字（尾指针），向前移动。如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字。（类似于快速排序）
源代码如下：
#include <iostream>
using namespace std;
void Move(int a[], int n)
{
int *left, *right;
left = &a[0];
right = &a[n - 1];
while(left < right)
{
if (*left % 2 == 1)
left++;
else if (*right % 2 == 0)
right--;
else
{
int temp = *left;
*left = *right;
*right =temp;
}
}
}
int main()
{
int a[100];
int n = 0;
while(cin.peek() != '\n') cin >> a[n++];
Move(a, n);
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
return 0;
}
分析：时间复杂度为 O（n）。
解法三：前后指针
还记得快速排序的过程，设置一个主元，依次遍历元素并使得它和主元进行比较，并按照要去交换元素的位置。
该问题使用两个指针 i 和 j ，一个指针指向数组的第一个元素的前一个位置，称为后指针 i，向右移动；另一个指针指向数组的第一个元素，称为前指针 j，向右移动。前后指针都向后移动的过程中，如果前指针 j 指向的元素是奇数，则令后指针 i 向右移动一位，然后交换 i 和 j 两个指针所各自指向的元素。我们最终的目的是让奇数排在数组的前面，偶数排在数组的后面，所以 i 指针指向的是奇数， j 指针指向的是偶数。因此，当 j 指针指向的是奇数时，不正常，让 i++，然后交换 i ， j 指针所指向的数。
源代码如下：
#include <iostream>
using namespace std;
//判断是否为奇数
bool IsOddNumber(int data)
{
if (data % 2 == 1) //奇数
return true;
else
return false;
}
//奇数和偶数互换
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[100];
int n = 0;
while(cin.peek() != '\n') cin >> a[n++];
CddEvenSort2(a, 0, n - 1);
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
分析：时间复杂度为 O（n）。
特别注意：
虽然解法二和解法三都实现了，但是它们的输出却有点差别。
参考资料：《编程之法》The Art of Programming By July
