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

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

要求：

1、输入一个奇数、偶数相交叉的数组，来检测一下输出

2、输入一个数字

3、输入空指针

常规思路：

一般情况下，我们都会想到这样的方法，从头开始检测，如果发现有偶数的，则此偶数后面的数向前移动一位，然后此偶数放在最后一位，这样，光是搜索就要O（n），如果还要移位，则总的时间复杂度为O（n*n），显然，这样的复杂度根本无法满足要求。

O（n）解法：

我们知道快速排序是怎么运行的，快速排序中的partition函数给我们很深的印象，大家可以分析一下这个partition函数，我的博客前面也是有关“内部排序”的分析，大家可以参考一下，只不过这里和partition函数不同的是，partition中每次的分界值是固定的，但是我们这里每次要标记两个分界值，然后分别交换这两个分界值。

废话少说，先上代码：

#include<stdio.h>
void odd_even(int A[],int n)
{
    int i=0,j=n-1,i_index=0,j_index=n-1,i_tag=0,j_tag=1;
    int tmp=0;
    while(i<j)
    {
        while(i<j&&A[j]%2==0)--j;
        if(i<j&&A[j]%2==1)
        {
            j_tag=1;
            j_index=j;
        }
        else
            j_tag=0;
        while(i<j&&A[i]%2==1)++i;
        if(i<j&&A[i]%2==0)
        {
            i_tag=1;
            i_index=i;
        }
        else
            i_tag=0;
        if(i_tag==1&&j_tag==1)
        {
            tmp=A[j_index];
            A[j_index]=A[i_index];
            A[i_index]=tmp;
        }

    }
    for(i=0;i<n;++i)
        printf("%d\t",A[i]);
}
int main()
{
    printf("请输入数组的长度:\n");
    int n=0,i=0;
    scanf("%d",&n);
    int A[n];
    printf("请输入数组的元素:\n");
    for(;i<n;++i)
        scanf("%d",&A[i]);
    printf("\n输出的结果是:\n\n");
    odd_even(A,n);
    printf("\n");
    return 0;
}

剑指offer：调整数组顺序使奇数位于偶数前面,布布扣,bubuko.com

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

原文：http://blog.csdn.net/litianpenghaha/article/details/22191749