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

超、凢脫俗 2022-03-15 06:38 107阅读 0赞

## 目录 ##

*  题目
 *  分析
 *  解法一
 *  解法二
 *  解法三
 *  运行效率比较
 *  扩展
 *  总结

## 题目 ##

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

## 分析 ##

事实上，这个题比较简单，很多种方式都可以实现，但是其时间复杂度或空间复杂度不尽相同。

## 解法一 ##

书中作者提到一种初始的做法是，从头扫描整个数组，如果遇到偶数，则拿出这个数，并且把整个数组的数据都向前挪动一位，再把拿出的数放到末尾。每碰到一个偶数就需要移动O(N)次，这样总的**时间复杂度为O(n^2),空间复杂度为O(1)**。

这种方式很简单，如果已经很清楚是怎么回事，可以跳过例子说明，继续阅读下一个解法。但是**可以尝试自己写一下代码，发现有些细节部分并不是那么容易写出来**。

举个例子，假设有数据1,2,3,4,5,6：

从左往右扫描，找到第一个偶数2，并临时保存：

将2后面的所有数往前移动一个位置，并将2放到最后一个位置：

继续扫描**当前位置**，发现3为奇数，继续，发现4为偶数，将从3之后位置的数开始，到倒数第二个位置，所有数往前移动一个位置，并将4放到最后：

继续扫描当前位置数5，6，至此，偶数有2两个，当前指向位置为,所在下标为4，总数 - 位置 <= 偶数 ,结束。

根据该思路，C语言代码实现如下：

//reorder.c
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <string.h>
    void reorder(int arr[],int len)
    {
        if(NULL == arr || 0 == len)
            return;
        /*统计偶数数量，减少移动次数*/
        int evenNum = 0;
        int loop = 0;
        int temp;
        int inLoop = 0;
        while(loop < len)
        {
            /*如果是偶数，则需要开始移动*/
            temp = arr[loop];
            /*如果已经达到了*/
            if(0 == (temp & 1) && (len - loop  > evenNum))
            {
    
                /*从当前位置开始移动，直到遇到剩下的数量是偶数的个数*/
                for(inLoop = loop + 1;inLoop < len - evenNum;inLoop++)
                {
                    arr[inLoop-1] = arr[inLoop];
                }
                /*把空出来的位填充上*/
                arr[len  - evenNum - 1] = temp;
                evenNum++;
    
                /*交换后继续*/
                continue;
            }
            /*继续循环下一个*/
            else        
            {        
                loop++;
            }
    
    
        }
    }

## 解法二 ##

很多人其实最先想到的解法可能是，创建一个新的数组，从头扫描，遇到偶数放后边，遇到奇数放前边。扫描结束后，再将数组内容拷贝到原数组，这样整个**时间复杂度为(n）,而空间复杂度也为O(n)**，这样的方法实现简单，也不容易出错。C语言代码实现如下：

//reorder1.c
    void reorder(int arr[],int len)
    {
        if(NULL == arr || 0 == len)
            return;
        /*记录奇偶的数量*/
        int oddNum = 0;
        int evenNum = 0;
        int loop = 0;
        /*创建一个新的数组*/
        int *temp = malloc(len * sizeof(int));
        if(NULL == temp)
        {
            printf("malloc memory failed\n");
            return;
        }
        /*拷贝数组，并遍历*/
        memcpy(temp,arr,sizeof(int)*len);
        for(;loop < len;loop++)
        {
            /*偶数放到数组末尾*/
            if(0 == (temp[loop] & 1))
            {
                arr[len-1-evenNum] = temp[loop];
                evenNum++;
            }
            /*奇数放到数组末尾*/
            else
            {
                arr[oddNum] = temp[loop];
                oddNum++;
            }
        }
        free(temp);
    }

## 解法三 ##

还记得我们之前介绍过的《[快速排序优化详解][Link 1]》吗？快速排序中，有一个分区操作，是将整个数组大于等于基准的部分放右边，而小于等于基准的部分放左边，即根据基准，将数组一分为二。其实在这里，同样可以参考这个思路，只不过跟基准比大小，变成了判断是奇还是偶。  
这里简单描述一下该思路，更多细节可以参考《[快速排序优化详解][Link 1]》中如何将元素移动到基准两侧一节：

*  定义下标i和j，分别从开头和结尾开始扫描
 *  当i遇到偶数时，停止扫描
 *  当j遇到奇数时，停止扫描
 *  此时交换i和j位置的值
 *  继续前面的操作，直到i和j交错或相等

举个例子，假设有数据1,2,3,4,5,6,7,8：

![640?wx\_fmt=png][640_wx_fmt_png]

i和j继续扫描，i遇到2停止，j遇到5停止，交换两处的值：

![640?wx\_fmt=png][640_wx_fmt_png 1]

i和j继续扫描，i遇到4停止，j遇到5停止，交换两处的值：

![640?wx\_fmt=png][640_wx_fmt_png 2]

继续扫描，此时，i和j交错，扫描结束：

![640?wx\_fmt=png][640_wx_fmt_png 3]

基于该思路的算法**时间复杂度为O(n)，空间复杂度为O(1)**，C语言代码实现如下：

//reorder2.c
    void reorder(int arr[],int len)
    {
        if(NULL == arr || 0 == len)
            return;
        int i = 0;
        int j = len - 1;
        int temp;
        for(;;)
        {
            /*i j分别向右和向左移动，i遇到偶数停止，j遇到奇数停止？*/
            while(1 == (arr[i] & 1))
            {
                i++;
            }
            while(0 == (arr[j] & 1))
            {
                j--;
            }
            if(i < j)
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            /*交错时停止*/
            else
            {
                break;
            }
    
        }
    }

## 运行效率比较 ##

编译后，对一百万数据进行操作，运行时间结果如下。  
解法一：

$ time ./reorder 1000000

并没有耐心等到结果出来。  
解法二：

$ time ./reorder1 100000000
    reorder for 100000000 numbers
    before reorder:too much，will not print
    after  reorder:too much，will not print
    
    real    0m2.425s
    user    0m2.141s
    sys    0m0.284s

对1亿数据进行操作，耗时很短，只是内存占用较多。  
解法三：

$ time ./reorder2 100000000
    reorder for 100000000 numbers
    before reorder:too much，will not print
    after  reorder:too much，will not print
    
    real    0m2.146s
    user    0m2.018s
    sys    0m0.128s

耗时很短，内存占用少。

## 扩展 ##

在本题中，只是对整数是奇还是偶进行分开，那么如果是别的条件呢？例如是否为素数，是否为正数等等。我们可以让调用者传入一个条件函数，让它决定到底是放在后半部分，还是前半部分。这是不是很向库函数qsort需要传入一个比较函数的做法？这部分内容可以参考《[函数指针][Link 2]》，根据这个思路，我们修改解法三的代码：

左下角阅读原文获取完整代码

这个时候通过传入函数指针，可以对任意条件进行处理了。

## 总结 ##

我们发现，一些基本算法的思想，通常可以用到其他问题上，而不同的思路，带来的效率可能天差地别。

## 练习 ##

尝试自己实现上面的算法并扩展实现。

## 备注 ##

完整代码以及模拟一亿数据处理请访问[剑指offer：调整数组顺序使奇数位于偶数前面][offer]

关注公众号【编程珠玑】，获取更多Linux/C/C++/Python/Go/算法/工具等原创技术文章。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

[Link 1]: http://mp.weixin.qq.com/s?__biz=MzI2OTA3NTk3Ng==&mid=2649284453&idx=1&sn=4174d0a2452b0790d54b1641740593da&chksm=f2f9ac02c58e25142fc92ff97ac8d47c37e7fa3c4a156822e9ed6d4968f4716f92de055772eb&scene=21#wechat_redirect
[640_wx_fmt_png]: /images/20220315/05231fdb68304f39b146e3957922b5b0.png
[640_wx_fmt_png 1]: /images/20220315/b41185cff67a44a1b2c3f98d8f69270c.png
[640_wx_fmt_png 2]: /images/20220315/9db0324232a44cc29b53a59c22aacc2c.png
[640_wx_fmt_png 3]: /images/20220315/b03875e23e8c40dba0ff7b499c6ea23b.png
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzI2OTA3NTk3Ng==&mid=2649284302&idx=1&sn=ff641fe387304221983823cecf98d05c&chksm=f2f9ada9c58e24bfb3b7de4bebfb3b4c87809f10a8633ad4daa09a6ed7f9450c3a3448fd3312&scene=21#wechat_redirect
[offer]: https://www.yanbinghu.com/2019/02/28/31098.html
[640_wx_fmt_jpeg]: /images/20220315/73286b469ebc44d1ae895b0c88acd381.png