调整数组顺序使奇数位于偶数前面

本是古典何须时尚 2022-02-13 09:41 192阅读 0赞

题目：输入一个整数数组，实现一个函数调整数组的元素顺序，使得奇数位于偶数的前半部分，偶数位于数组的后半部分。

对于这个问题，最直接的办法就是遍历这个数组，如果是奇数就往后遍历，如果是偶数，则将后面所有的元素往前移一位，并将这个偶数插入到数组的末尾位置。

C语言实现如下：

void adjustOddEven1(int *number,int n)
    {
        int i,j,key,count=0;
        for(i=0;i<n-1-count;)
        {
            if(!isOdd(number[i]))
            {
                key=number[i];
                for(j=i+1;j<n-count;j++){number[j-1]=number[j];}
                number[n-1-count]=key;
                count++;
            }else
            {
                i++;
            }
        }
    }

如果你还想知道更加简单的接法，那么你该看看下面的方法。

我们可以使用指针来进行标记，用left标记从左到右找到的第一个偶数，right标记从右到左找到的第一个奇数，这样当我们找到奇数和偶数时，我们就进行对调，通知更新left=left+1,right=right-1;然后left继续向后遍历，right继续向前遍历，知道left>=right为止跳出循环。

下面是其思想实现：

void adjustOddEven(int *number,int n,int (*p)(int))//使用标记指针和函数指针，函数指针是为了方便扩展
    {
        if(number==NULL||n<=1) return;
        int left=0,right=n-1;
        while(left<right)
        {
            while(left<right&&p(number[left])) left++;
            while(left<right&&(!p(number[right]))) right--;
            if(left<right)
            {
                number[left]=number[left]^number[right];
                number[right]=number[left]^number[right];
                number[left]=number[left]^number[right];
                left++;
                right--;
            }
        }
    }

在上面的程序中，大家会看到函数中有个函数指针参数，这个参数是为了更好的进行拓展，比方说如果题目变成了“将负数放在前面，正数放在后面”，则我们只需修改这个判断的函数进行了。

理解了上面的两种算法之后你是不是觉得就行了呢？我觉得吧，大家既然做了这个题目，那就再往下挖深一点了，如果题目修改一下，还要求我们不仅要将奇数放在数组的前半部分，还要求奇数的相对出现次序不变，即原来一个奇数a在另一个奇数b的前面，那么这个奇数a在经过排序后还在奇数b的前面。

想一想！是否自己有了想法呢？下面是一种实现方式，大家要是有好的想法不妨也贴出来，大家共同学习一下啊。

C语言实现：

void adjustOddEven2(int *number,int n)//按奇偶分组后，各分组内相对出现次序不变
    {
        if(number==NULL||n<=1) return;
        int *lastOdd=number-1,*p;
        int i,key;
        for(i=0;i<n;i++)
        {
            if(isOdd(number[i]))
            {
                key=number[i];
                for(p=number+i-1;p>lastOdd;p--)
                {
                    *(p+1)=*p;
                }
                *(p+1)=key;
                lastOdd++;
            }
        }
    }

当然从上到下我们用到的判断奇数的程序如下所示：

int isOdd(int n)
    {
        return (n&1)!=0;
    }

经过上面的程序，我们给出一个测试用例吧。

int main()
    {
        int array[]={3,-4,-6,-6,-2,1};
        print(array,sizeof(array)/sizeof(int));
        //int (*p)(int)=isPositive;
        adjustOddEven2(array,sizeof(array)/sizeof(int));
        print(array,sizeof(array)/sizeof(int));
        return 0;
    }

运行结果如下所示：

![20130522151314947][]

[20130522151314947]: /images/20220213/71eddf65992940279ff8f11f2f2ffb13.png