劍指offer之調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

1 問題

輸入一個整數(shù)數(shù)組，實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，所有偶數(shù)位于數(shù)組的后半部分，比如數(shù)組{6、 5 、1、 4、2 、7 、3、8、9}我們調(diào)整后變成這樣{9、5、1、3、7 、2 、4 、8、6}   

2 分析

我們利用partition算法博客可以知道，這里還是利用兩個指針，一個指針指向開始，一個指針指向尾巴，分別從兩邊進(jìn)行掃描，我們先從尾巴指針向左移動，發(fā)現(xiàn)了奇數(shù)就暫停這里，然后開始移動首指針，如果發(fā)現(xiàn)是偶數(shù)了就保存當(dāng)前指針，然后和之前掃描到奇數(shù)位置進(jìn)行換位置，終止條件是首指針的值等于尾指針的值。

 
3 代碼實現(xiàn)

    #include <iostream>
    #include <vector>
     
    using namespace std;
     
    void swap(int* a, int* b)
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
     
    void printVector(vector<int> v)
    {
        for (int i = 0; i < v.size(); ++i)
        {
            std::cout << v[i] << "\t";
        }
        std::cout << std::endl;
    }
     
    /*
     *奇數(shù)在偶數(shù)前面的函數(shù)
     */
    void reorderOddEven(vector<int>& vector)
    {
        if (vector.size() <= 0)
        {
            std::cout << "vector.size is <= 0" << std::endl;
            return;
        }
        int start = 0;
        int end = vector.size() - 1;
        while (start < end)
        {
            while (start < end && (vector[end] % 2) == 0)
            {
                --end;
            }
            while (start < end &&  (vector[start] % 2) != 0)
            {
                ++start;   
            }
            swap(vector[start], vector[end]);
        }
    }
     
    int main()
    {
        vector<int> v2;
        v2.push_back(6);
        v2.push_back(5);
        v2.push_back(1);
        v2.push_back(4);
        v2.push_back(2);
        v2.push_back(7);
        v2.push_back(3);
        v2.push_back(8);
        v2.push_back(9);
        
        vector<int> v3;
        printVector(v2);
        reorderOddEven(v2);
        printVector(v2);
        
        return 0;
    }


 
4 運行結(jié)果

    6    5    1    4    2    7    3    8    9   
    9    5    1    3    7    2    4    8    6   

 
5 優(yōu)化

比如我們還有類似的問題，比如數(shù)組里面有負(fù)數(shù)和整數(shù)，我們要求負(fù)數(shù)在正數(shù)前面，我么知道reorderOddEven函數(shù)里面只要把(vector[start] % 2) != 0這個條件進(jìn)行修改就行，這里我么可以使用函數(shù)指針，根據(jù)不同的需求傳遞不同的函數(shù)指針下來，達(dá)到效果，增加部分代碼實現(xiàn)如下。

    #include <iostream>
    #include <vector>
     
    using namespace std;
     
    void swap(int* a, int* b)
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
     
    void printVector(vector<int> v)
    {
        for (int i = 0; i < v.size(); ++i)
        {
            std::cout << v[i] << "\t";
        }
        std::cout << std::endl;
    }
     
    bool isOddEvenNumber(int number)
    {
        return ((number & 0x1) == 0);
    }
     
     
    bool isNagetiveNumber(int number)
    {
        if (number > 0)
            return true;
        else
            return false;
    }
     
    void reorderOddEvenOne(vector<int>& vector, bool (*func)(int))
    {
        if (vector.size() <= 0)
        {
            std::cout << "vector.size is <= 0" << std::endl;
            return;
        }
        int start = 0;
        int end = vector.size() - 1;
        while (start < end)
        {
            while (start < end && (*func)(vector[end]))
            {
                --end;
            }
            while (start < end && !(*func)(vector[start]))
            {
                ++start;   
            }
            swap(vector[start], vector[end]);
        }
    }
     
     
    int main()
    {
        vector<int> v2;
        v2.push_back(6);
        v2.push_back(5);
        v2.push_back(1);
        v2.push_back(4);
        v2.push_back(2);
        v2.push_back(7);
        v2.push_back(3);
        v2.push_back(8);
        v2.push_back(9);
        
        vector<int> v3;
        printVector(v2);
     
        reorderOddEvenOne(v2, isOddEvenNumber);
        printVector(v2);
     
        return 0;
    }

運行結(jié)果如下

    6    5    1    4    2    7    3    8    9   
    9    5    1    3    7    2    4    8    6   

如果我們要實現(xiàn)負(fù)數(shù)在前面的數(shù)組，我們只需要調(diào)用reorderOddEvenOne函數(shù)傳遞isNagetiveNumber作為函數(shù)指針就行。



作者：chen.yu
深信服三年半工作經(jīng)驗，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)