剑指offer-调整数组顺序使奇数位于偶数前面

太过爱你忘了你带给我的痛 2022-02-15 05:39 163阅读 0赞

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

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

#### 实现思想 ####

这道题最简单并且想考察的思想就是利用冒泡排序一样的算法，两层for循环，外层用来确保从后向前依次是偶数，内层用来交换数组相邻顺序是偶奇的两个数，交换成奇偶顺序，这样保证了每一层外循环的最后一个都会变成偶数。

#### 代码实现 ####

class Solution {
    public:
        void reOrderArray(vector<int> &array) {
            for(int i = array.size(); i > 0; i--) {
                for(int j = 0; j < i; j++) {
                    if(array[j] % 2 == 0 && array[j+1] % 2 != 0) {
                        swap(array[j], array[j+1]);
                    }
                }
            }
        }
    };

#### 运行截图 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3doaWxlMTA_size_16_color_FFFFFF_t_70]

#### 总结 ####

除了上述方法外其实还有很多办法，上述方法最好的地方就是可以节省空间，不用另外的申请数组或者栈。  
用栈的办法实现：申请两个栈，然后从后向前遍历数组，如果为奇数压入栈1，如果为偶数压入栈2，最终将奇数栈一个一个弹出到数组，再将偶数栈一个一个弹出数组即可。  
另外申请一个数组的办法：另申请一个数组a，遍历一遍输入数组，将奇数先放入数组a中，再遍历一遍输入数组，再将偶数放入数组a中即可。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3doaWxlMTA_size_16_color_FFFFFF_t_70]: /images/20220215/bc3f153ede1b46ffaacab14de0b53eb1.png