数据结构

Question

有一个数组,里边有N个数.要求写一个方法.把所有奇数放到所有偶数前.要求不要增加另外的存储空间.时间复杂度为t(o)=f(n)

Answer 1

#include<iostream>
using namespace std;void change(int &a,int &b);
void mysort(int *array,int n);
int main()
{
int N;
cin>>N;
int *array=new int[N];
for(int i=0;i<N;i++)
cin>>array[i];
mysort(array,N);
for(int j=0;j<N;j++)
cout<<array[j]<<" ";
return 0;
}
//实现所有奇数位于偶数前
void mysort(int *array,int n)
{
int left=0,right=n-1;
while(left<right)
{
while(array[left]%2!=0)
left++;
while(array[right]%2==0)
right--;
change(array[left],array[right]);
left++;
right--; }}
//两数交换
void change(int &a,int &b)
{
int temp;
temp=a;
a=b;
b=temp;
}刚才写了一下，应该还合乎要求吧

Answer 2

// 奇数在左，偶数在右
        private void OrdEven(int[] r)
        {
            int front = 0, rear = r.Length - 1;
            bool Right = true; // 往右
            while (front <= rear)
            {
                if (Right)
                {
                    if (r[front] % 2 == 0)
                    {
                        swap(r, front, rear);
                        Right = false;
                    }
                    else
                    {
                        front++;
                    }
                }
                else
                {
                    if (r[rear] % 2 == 1)
                    {
                        swap(r, front, rear);
                        Right = true;
                    }
                    else
                    {
                        rear--;
                    }
                }
            }
        }        private void swap(int[] r, int x, int y)
        {
            int temp = r[x];
            r[x] = r[y];
            r[y] = temp;
        }
以测试

Answer 3

前面那个函数改一下，加了一条if 语句，因为有的情况下不加条件可能出错//实现所有奇数位于偶数前
void mysort(int *array,int n)
{
int left=0,right=n-1;
while(left<right)
{
while(array[left]%2!=0)
left++;
while(array[right]%2==0)
right--;
if(left<right)
change(array[left],array[right]);
left++;
right--;
}
}