題目

輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，所有偶數(shù)位于數(shù)組的后半部分

分析

• 思路1

如果不考慮時(shí)間復(fù)雜度，則最簡(jiǎn)單的思路應(yīng)該是從頭掃描這個(gè)數(shù)組，每碰到一個(gè)偶數(shù)，拿出這個(gè)數(shù)，并把位于這個(gè)數(shù)字后面的所有數(shù)字往前挪動(dòng)一位。挪動(dòng)之后在數(shù)組的末尾有一個(gè)空位，這時(shí)把該偶數(shù)放入這個(gè)空位。由于每碰到一個(gè)偶數(shù)就需要移動(dòng)O(n)個(gè)數(shù)字，因此總的時(shí)間復(fù)雜度是O(n²)

• 思路2

其實(shí)掃描這個(gè)數(shù)組的時(shí)候，如果發(fā)現(xiàn)有偶數(shù)出現(xiàn)在奇數(shù)的前面，則交換奇偶數(shù)的位置即可

因此，我們可以維護(hù)兩個(gè)指針：

• 第一個(gè)指針初始化時(shí)指向數(shù)組的第一個(gè)數(shù)字，它只向后移動(dòng)；
• 第二個(gè)指針初始化時(shí)指向數(shù)組的最后一個(gè)數(shù)字，它只向前移動(dòng)。

在兩個(gè)指針相遇之前，第一個(gè)指針總是位于第二個(gè)指針的前面。如果第一個(gè)指針指向的數(shù)字是偶數(shù)，并且第二個(gè)指針指向的數(shù)字是奇數(shù)，則交換兩個(gè)數(shù)字

分析具體例子

如：輸入數(shù)組{1，2，3，4，5}來(lái)分析這種思路

• 在初始化時(shí)，把第一個(gè)指針指向數(shù)組的第一個(gè)數(shù)字1，而把第二個(gè)指針指向最后一個(gè)數(shù)字5，如圖（a）所示。

• 第一個(gè)指針指向的數(shù)字1是奇數(shù)，不需要處理，我們把第一個(gè)指針向后移動(dòng)，直到碰到一個(gè)偶數(shù)2。此時(shí)第二個(gè)指針已經(jīng)指向了奇數(shù)，因此不需要移動(dòng)。此時(shí)兩個(gè)指針指向的位置如圖（b）所示。這時(shí)候我們發(fā)現(xiàn)偶數(shù)2位于奇數(shù)5的前面，符合交換條件，也是交換這兩個(gè)指針指向的數(shù)字，如圖（c）

• 接下來(lái)我們繼續(xù)向后移動(dòng)第一個(gè)指針，直到碰到下一個(gè)偶數(shù)4，并向前移動(dòng)第二個(gè)指針，直到碰到第一個(gè)奇數(shù)3，如圖（d）所示。

這時(shí)我們發(fā)現(xiàn)第二個(gè)指針已經(jīng)在第一個(gè)指針的前面了，表示所有的奇數(shù)都已經(jīng)在偶數(shù)的前面了。此時(shí)的數(shù)組是{1，5，3，4，2}，的確是奇數(shù)位于數(shù)字的前半部分而偶數(shù)位于數(shù)組的后半部分

download.png

算法實(shí)現(xiàn)

void RecorderOddEven(int *pData, unsigned int length)
{
    if (pData == nullptr || length == 0)
        return;

    int *pBegin = pData;
    int *pEnd = pData + length - 1;

    while (pBegin < pEnd) {
        // 向后移動(dòng)pBegin，直到塔指向偶數(shù)
        while (pBegin < pEnd && (*pBegin & 0x1) != 0) {
            pBegin++;
        }

        // 向前移動(dòng)pEnd，直到它指向奇數(shù)
        while (pBegin < pEnd && (*pEnd & 0x1) == 0) {
            pEnd--;
        }

        if (pBegin < pEnd) {
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
        }
    }
}

可擴(kuò)展的解法

Reorder函數(shù)把pData為數(shù)組分為兩部分

void Reorder(int *pData, unsigned int length, bool(*func)(int))
{
    if (pData == nullptr || length == 0)
        return;

    int *pBegin = pData;
    int *pEnd = pData + length - 1;

    while (pBegin < pEnd) {
        while (pBegin < pEnd && !func(*pBegin)) {
            pBegin++;
        }

        while (pBegin < pEnd && func(*pEnd)) {
            pEnd--;
        }

        if (pBegin<pEnd)
        {
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
        }
    }
}

// 判斷是不是偶數(shù)
bool isEven(int n)
{
    return (n & 1) == 0;
}

有了上面兩個(gè)函數(shù)，我們可以很方便的把數(shù)組中的所有奇數(shù)移到偶數(shù)的前面

void RecoderOddEven(int *pData, unsigned int length)
{
    Reorder(pData, length, isEven);
}

如果把問(wèn)題改成將數(shù)組中的負(fù)數(shù)移到非負(fù)數(shù)的前面，或者把能被3整除的數(shù)移到不能被3整除的數(shù)的前面，都只需定義新的函數(shù)來(lái)確定分組的標(biāo)準(zhǔn)，而函數(shù)Reorder不需要進(jìn)行任何改動(dòng)。也就是說(shuō)，解耦的好處就是提高了代碼的重用性，為功能的擴(kuò)展提供了便利

參考

《劍指offer》