两道百度笔试题

　　看到一位园友写了一篇关于百度的面试题的博客，成了评论头条，再下看了一下，非常感兴趣，那位博主的算法能力跟我一样需要提高，估计他的功力还在我之下，所以再下不才，在这里把自己的源码贴出来。

　　百度面试题（一）：假设一整型数组存在若干正数和负数，现在通过某种算法使得该数组的所有负数在正数的左边，且保证负数和正数间元素相对位置不变。时空复杂度要求分别为：o（n）和o（1）。

　　其实开始的时候我也是一头雾水，在纸上画画之后发现，其实是一道变形的插入排序。幸运的是这里不需要比较大小，要比较大小的话时间复杂度是O（n2），只用判断正负，那时间复杂度只要O（n）了。

　　如：-3，1，2，-1，-3，4。其实是把正数后面的第一个负数（如-1）插到第一个正数（1）的前面，负数之间的每个正数（1，2）后移一位，这么简单。时间复杂度刚好为O（n），控件复杂度为O（1）。

//算法分开正负数
void Sort（int *A ，int size）
{
    int minus=-1，plus=-1;
    int tmp=0;
    for（int i=0;i<size;i++）
    {
        if（minus==-1）
        {
            if（A[i]<0 && plus>=0）
            {
                minus=i;
            }
          
            if（A[i]>0 && plus<0）
            {
                plus=i;
            }
        }

        if（minus>=0 && plus>=0）
        {
            tmp=A[plus];
            A[plus++] = A[minus];
            for （int k = minus; k> plus; k--）
            {
                 A[k] = A[k - 1];
            }
            A[plus]=tmp;
            minus=-1;
        }
    }
}

　　百度面试题（二），给定一个存放正数的数组，重新排列数组使得数组左边为奇数，右边为偶数，且保证奇数和偶数之间元素相对位置不变。时空复杂度要求分别为：o（n）和o（1）。

　　其实这两道笔试题没有什么区别，要说有区别是看你是否理解。

//算法分开奇偶数
void Sort1（int *A ，int size）
{
    int minus=-1，plus=-1;
    int tmp=0;
    for（int i=0;i<size;i++）
    {
        if（minus==-1）
        {
            if（A[i]％2!=0 && plus>=0）
            {
                minus=i;
            }
          
            if（A[i]％2==0 && plus<0）
            {
                plus=i;
            }
        }

        if（minus>=0 && plus>=0）
        {
            tmp=A[plus];
            A[plus++] = A[minus];
            for （int k = minus; k> plus; k--）
            {
                 A[k] = A[k - 1];
            }
            A[plus]=tmp;
            minus=-1;
        }
    }
}