• 奇偶调序
    • 题目描述
      • 分析与解法
        • 解法一
        • 解法二
      • 举一反三

    奇偶调序

    题目描述

    输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

    分析与解法

    最容易想到的办法是从头扫描这个数组，每碰到一个偶数，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，然后把该偶数放入这个空位。由于每碰到一个偶数，需要移动O(n)个数字，所以这种方法总的时间复杂度是O(n^2)，不符合题目要求。

    事实上，若把奇数看做是小的数，偶数看做是大的数，那么按照题目所要求的奇数放在前面偶数放在后面，就相当于小数放在前面大数放在后面，联想到快速排序中的partition过程，不就是通过一个主元把整个数组分成大小两个部分么，小于主元的小数放在前面，大于主元的大数放在后面。

    而partition过程有以下两种实现：

    • 一头一尾两个指针往中间扫描，如果头指针遇到的数比主元大且尾指针遇到的数比主元小，则交换头尾指针所分别指向的数字；
    • 一前一后两个指针同时从左往右扫，如果前指针遇到的数比主元小，则后指针右移一位，然后交换各自所指向的数字。

    类似这个partition过程，奇偶排序问题也可以分别借鉴partition的两种实现解决。

    为何？比如partition的实现一中，如果最终是为了让整个序列元素从小到大排序，那么头指针理应指向的就是小数，而尾指针理应指向的就是大数，故当头指针指的是大数且尾指针指的是小数的时候就不正常，此时就当交换。

    解法一

    借鉴partition的实现一，我们可以考虑维护两个指针，一个指针指向数组的第一个数字，我们称之为头指针，向右移动；一个指针指向最后一个数字，称之为尾指针，向左移动。

    这样，两个指针分别从数组的头部和尾部向数组的中间移动，如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字。

    因为按照题目要求，最终是为了让奇数排在数组的前面，偶数排在数组的后面，所以头指针理应指向的就是奇数，尾指针理应指向的就是偶数，故当头指针指向的是偶数且尾指针指向的是奇数时，我们就当立即交换它们所指向的数字。

    思路有了，接下来，写代码实现：

    1. //判断是否为奇数
    2. bool IsOddNumber(int data)
    3. {
    4.     return data & 1 == 1;
    5. }
    7. //奇偶互换
    8. void OddEvenSort(int *pData, unsigned int length)
    9. {
    10.     if (pData == NULL || length == 0)
    11.         return;
    13.     int *pBegin = pData;
    14.     int *pEnd = pData + length - 1;
    16.     while (pBegin < pEnd)
    17.     {
    18.         //如果pBegin指针指向的是奇数，正常，向右移
    19.         if (IsOddNumber(*pBegin))  
    20.         {
    21.             pBegin++;
    22.         }
    23.         //如果pEnd指针指向的是偶数，正常，向左移
    24.         else if (!IsOddNumber(*pEnd))
    25.         {
    26.             pEnd--;
    27.         }
    28.         else
    29.         {
    30.             //否则都不正常，交换
    31.             //swap是STL库函数，声明为void swap(int& a, int& b);
    32.             swap(*pBegin, *pEnd);
    33.         }
    34.     }
    35. }

    本方法通过头尾两个指针往中间扫描，一次遍历完成所有奇数偶数的重新排列，时间复杂度为O(n)。

    解法二

    我们先来看看快速排序partition过程的第二种实现是具体怎样的一个原理。

    partition分治过程，每一趟排序的过程中，选取的主元都会把整个数组排列成一大一小的序列，继而递归排序完整个数组。如下伪代码所示：

    1. PARTITION(A, p, r)
    2. 1  x ← A[r]
    3. 2  i ← p - 1
    4. 3  for j ← p to r - 1
    5. 4       do if A[j] ≤ x
    6. 5             then i ← i + 1
    7. 6                  exchange A[i] <-> A[j]
    8. 7  exchange A[i + 1] <-> A[r]
    9. 8  return i + 1

    举个例子如下：现要对数组data = {2, 8,7, 1, 3, 5, 6, 4}进行快速排序，为了表述方便，令i指向数组头部前一个位置，j指向数组头部元素，j在前，i在后，双双从左向右移动。

    ① j 指向元素2时，i 也指向元素2，2与2互换不变

    1. i  p/j
    3.       2   8   7   1   3   5   6   4(主元)

    ② 于是j 继续后移，直到指向了1，1 <= 4，于是i++，i 指向8，故j 所指元素1 与 i 所指元素8 位置互换：

    1.      i       j
    3.   2   1   7   8   3   5   6   4

    ③ j 继续后移，指到了元素3,3 <= 4，于是同样i++，i 指向7，故j 所指元素3 与 i 所指元素7 位置互换：

    1.         i       j
    3.   2   1   3   8   7   5   6   4

    ④ j 一路后移，没有再碰到比主元4小的元素：

    1.           i               j
    3.   2   1   3   8   7   5   6   4

    ⑤ 最后，A[i + 1] <-> A[r]，即8与4交换，所以，数组最终变成了如下形式：

    1.     2   1   3   4   7   5   6   8

    这样，快速排序第一趟完成。就这样，4把整个数组分成了俩部分，2 1 3,7 5 6 8，再递归对这两部分分别进行排序。

    借鉴partition的上述实现，我们也可以维护两个指针i和j，一个指针指向数组的第一个数的前一个位置，我们称之为后指针i，向右移动；一个指针指向数组第一个数，称之为前指针j，也向右移动，且前指针j先向右移动。如果前指针j指向的数字是奇数，则令i指针向右移动一位，然后交换i和j指针所各自指向的数字。

    因为按照题目要求，最终是为了让奇数排在数组的前面，偶数排在数组的后面，所以i指针理应指向的就是奇数，j指针理应指向的就是偶数，所以，当j指针指向的是奇数时，不正常，我们就当让i++，然后交换i和j指针所各自指向的数字。

    参考代码如下：

    1. //奇偶互换
    2. void OddEvenSort2(int data[], int lo, int hi)
    3. {
    4.     int i = lo - 1;
    5.     for (int j = lo; j < hi; j++)
    6.     {
    7.         //data[j]指向奇数，交换
    8.         if ( IsOddNumber(data[j]) )
    9.         {
    10.             i = i + 1;
    11.             swap(data[i], data[j]);
    12.         }
    13.     }
    14.     swap(data[i + 1], data[hi]);
    15. }

    此解法一前一后两个指针同时向右扫描的过程中，也是一次遍历完成奇数偶数的重新排列，故时间复杂度也为O(n)。

    举一反三

    一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来的正负数之间相对顺序，比如： input: 1,7,-5,9,-12,15 ans: -5,-12,1,7,9,15 要求时间复杂度O(n),空间O(1)。

    分析：如果本题没有这个要求“并且要求不改变原来的正负数之间相对顺序”，那么同奇偶数排序是一道题，但加上这个不能改变正负数之间的相对顺序后，便使得问题变得比较艰难了，若有兴趣，读者可以参考这篇论文《STABLE MINIMUM SPACE PARTITIONING IN LINEAR TIME》。