奇偶调序

题目描述：

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

分析和解法：

最容易想到的办法是从头扫描这个数组，每碰到一个偶数，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，然后把该偶数放入这个空位。由于每碰到一个偶数，需要移动 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