04-将奇数移动到偶数的左边

5.1.2　将奇数移动到偶数的左边

问题描述

将数组c[1:n]中所有奇数移动到偶数之前，要求时间复杂度为O(n)。

【分析】

该题是西北大学某年的考研试题。设置两个指示器i和j，分别从第一个元素开始向右和从最后一个元素开始向左扫描，i遇到奇数略过，遇到偶数暂停；j遇到偶数略过，遇到奇数暂停；如果i<j，则交换i和j指向的元素，直到i j结束。这样左边的元素就为奇数，右边的元素就为偶数。

/********************************************
*实例说明：将奇数移动到偶数的左边
*********************************************/
#include<iostream.h>
#include<iomanip.h>    
#define MAX 100                            
void SplitArray(int c[],int n);    
void PrintArray(int a[],int n);    
void main()
{
    int n;            
    int c[]={29,54,68,32,49,21,396,207,181};
    n=sizeof(c)/sizeof(c[0]);
    cout<<"数组c中的元素:"<<endl;
    PrintArray(c,n);
    cout<<"数组c调整后(左边元素为奇数,右边元素为偶数):"<<endl;
    SplitArray(c,n);            /*调整数组中的元素*/
    PrintArray(c,n);
}
void SplitArray(int c[],int n)
/*将数组a分成两个部分：左边是奇数，右边是偶数*/
{
    int i,j,t;                   /*定义两个指示器i和j*/
    i=0,j=n-1;                   /*指示器i和j分别指示数组的左边和右边元素*/
    while(i<j)        
    {
        while(c[i]%2!=0)       
            i++;               
        while(c[j]%2==0)       
            j--;               
        if(i<j)                
        {
            t=c[i];
            c[i]=c[j];
            c[j]=t;
        }    
    }
}
void PrintArray(int a[],int n)
//输出数组a中的元素
{
    int i;
    for(i=0;i<n;i++)
        cout<<setw(4)<<a[i];
    cout<<endl;
}

运行结果如图5.4所示。