【剑指Offer】（数组）调整数组顺序使奇数位于偶数前面

待我称王封你为后i 2022-03-16 12:48 96阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?tpId=13&tqId=11166&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_beb5aa231adc45b2a5dcc5b62c93f593_tpId_13_tqId_11166_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

#### 解决方法 ####

二分查找

class Solution { 
    public:
        void reOrderArray(vector<int> &array) { 
            if (array.size()<=1) return;
            //方法1：用两个队列分别存储奇数与偶数,时间复杂度O(n)
            /*queue<int> q1; queue<int> q2; for (int i=0;i<array.size();i++){ if (array[i]%2==1) q1.push(array[i]); else q2.push(array[i]); } int len=0; while(!q1.empty()){ array[len++]=q1.front(); q1.pop(); } while(!q2.empty()){ array[len++]=q2.front(); q2.pop(); }*/
            //方法2：类似冒泡算法，前偶后奇数就交换，可保证数组原有，但是时间复杂度为O(n^2)
            for (int i=0;i<array.size();i++)
                for (int j=array.size()-1;j>i;j--){ 
                    if (array[j-1]%2==0 && array[j]%2==1)
                        swap(array[j-1],array[j]);
                }
        }
    };

[https_www.nowcoder.com_practice_beb5aa231adc45b2a5dcc5b62c93f593_tpId_13_tqId_11166_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?tpId=13&tqId=11166&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking