给一段用sort的代码，奇数偶数相对位置不变

bool cmp(const int &a,const int &b){
    return (a&1)==(b&1)?0:(a&1);
}
class Solution {
public:
    void reOrderArray(vector<int> &array) {
         sort(array.begin(),array.end(),cmp);
    }
};

• 请问下，为什么我这么写会超时呢？

class Solution {
public:
    static bool cmp(const int &a,const int &b){
        return (a&1);
        //return (a&1)==(b&1)?1:(a&1);
    }
    void reOrderArray(vector<int> &array) {
         sort(array.begin(),array.end(),cmp);
    }
};

而且我如果写成return (a&1)==(b&1)?1:(a&1);，直接se了
* 我认为当ab奇偶性一样的时候，ab谁先谁后都无所谓，返回01都行，为啥会报错呢

别开static，static声明是静态的

我把cmp写在class外面，去掉static，该超时还是超时，该se还是se

你把你的代码发一下，我这里没问题。。。

bool cmp(const int &a,const int &b){
        //return (a&1);//超时
        return (a&1)==(b&1)?1:(a&1);//报se
    }
class Solution {
public:
    void reOrderArray(vector<int> &array) {
         sort(array.begin(),array.end(),cmp);
    }
};

$emmm…$
建议你了解一下$sort$的具体方法再想想看，说不定就知道为啥了

对比了一下你俩的代码：
你的报se:：return (a&1)==(b&1)?1:(a&1);
正确的： return (a&1)==(b&1)?0:(a&1);
如果二者皆为奇数或皆为偶数则：
应当return 0
而你的return 1
return 0时sort函数不会排序

return 1时会进行没必要的排序（将奇偶性相同的也排了一次），数据量大的时候会超时，数据小时能通过

好像快排啊

是啊，是啊，太像了，只不过把交换条件给变了

这两种差别在哪里呢？代码一可以通过，代码二不能通过

// 代码一
class Solution {
public:
    void reOrderArray(vector<int> &array) {
         if (array.size() == 0) return;
         int left = 0, right = array.size()-1;
         while (left < right) {
             if (array[left] % 2 == 0 && array[right] % 2 == 1) swap(array[left], array[right]);
             if (array[left] % 2) left++;
             if (array[right] % 2 == 0) right--;
         }
    }
}; 

class Solution {
public:
    void reOrderArray(vector<int> &array) {
         if (array.size() == 0) return;
         int left = 0, right = array.size()-1;
         while (left < right) {
             if (array[left] % 2) left++;
             if (array[right] % 2 == 0) right--;
             if (array[left] % 2 == 0 && array[right] % 2 == 1) swap(array[left], array[right]);
         }
    }
}; 

明白了，代码二的第三个if中会有left >= right的可能，加一个left < right 即可通过

问一下 如果这个函数在主函数中调用应该怎么样调用
？？？

int main(int argc, char** argv) {
    Solution s;
    vector<int> v;
    // Do something...
    s.reOrderArray(v);
    // Do something...
    return 0;
}

谢大哥！祝大哥一路长红

也可以采用类似unique库函数的实现方式，保证奇数与奇数，偶数与偶数的相对位置关系不发生改变，缺点是需要额外的空间开销

/**
 * 其实这道题目的关键思路和双指针算法中的unique库函数的实现方式可以说是完全相同的，
 * 无论是把0全部移到后面还是这道把奇数移到前面都差不多
 */
class Solution {
public:
    void reOrderArray(vector<int> &array) {
         vector<int> tmp;
         int j =  0;
         for (int i = 0; i < array.size(); ++ i)
        {
            if (array[i] & 1) array[j ++] = array[i];
            else tmp.push_back(array[i]);
        }
        for (int i = j, k = 0; i < array.size(); ++ i) array[i] = tmp[k ++];
    }
};

/**
 * 上面的做法可以保证奇数于奇数，偶数与偶数之间的相对位置关系不发生改变
 * 当我们不再考虑这个限制条件之后，也可以换一种写法，类似快排
 * 快排中每一次我们会把序列分成两部分，左半部分是<=数据n的，右半部分是>=n的
 * 这里我们只需要让左半部分是奇数，右半部分是偶数即可
 */
class Solution {
    public:
        void  reOrderArray(vector<int> &array) {
            int l = 0, r = array.size() - 1;
            while (l < r)
            {
                while (l < r && array[l] & 1) ++ l;
                while (l < r && (array[r] & 1) == 0) -- r; // 注意&的优先级小于=，所以一定要加小括号
                if (l < r) swap(array[l], array[r]);
            }
        }
};

快排的一种变种，代码量少点，但是理解起来不如Y总的

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int mi = 0;
        for(int k = 0; k < array.size(); ++k){
            if(array[k] & 1) swap(array[mi++], array[k]);
        }
    }
};

上述代码中，k指针在移动过程中检测奇数，并将奇数放到mi指针的前方，保证mi前面都为奇数，mi和mi后面的数都为偶数，缺点是在移动过程中，偶数之间的相对顺序变化了（奇数没有）

很棒。

快排划分区间的前后指针法，好思路

int len=array.size();

     for(int i=0;i<len-1;i++)
     {
         for(int j=0;j<len-i-1;j++)
         {
             if(array[j]%2==0) swap(array[j],array[j+1]);
         }
     }说实话，冒泡排序这个笨办法很好用，2ms

请问要不要保证奇数数字和偶数数字的相对稳定序，即不改变原数组中奇数的相对顺序或者偶数的相对顺序？
双指针这个就保证不了稳定顺序？

大老。

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        if(array.empty()) return;
        int i=0,j=0;
        for(i;i<array.size()-1;i++)
        {
            if(array[i]%2 == 0)
            {
                for(j=i+1;j<array.size()-1 && array[j]%2 == 0;j++);
                swap(array[i],array[j]);
            }
        }
    }
};

y总的那个我之前写了但是忘记if(l<r)了 自己想了这么一个代码

aaaaaaaaaaaaaaaaa,没想到快排

bool cmp(const int& a, const int& b){
return (a&1) > (b&1);
}
class Solution {
public:
void reOrderArray(vector[HTML_REMOVED] &array) {
sort(array.begin(), array.end(), cmp);
}
};

冒泡：
void reOrderArray(int *array, int length) {
if(length!=0)
{
int low=0;
int high=length-1;
while(low!=high)
{
for(int i=high;i>low;i–)
{
if(array[i]%2)
{
int temp=array[i-1];
array[i-1]=array[i];
array[i]=temp;
}
}
low++;
}
}
}

少了个排序吧，偶数部分和参考样例不同

不用sort 奇数偶数相对位置不变

class Solution {
public:
    void reOrderArray(vector<int> &array) {
         int n = array.size();
         int a,b;

         for(int i=0;i<n;i++) {
            if(array[i] % 2 == 0) {
                // [a, b-1] 为偶数 b位置为奇数
                a = i;
                b = i + 1;
                while(b < n && array[b] % 2 == 0) b++;
                // b 超出范围则完成调整
                if(b >= n) return;
                // 将 b 位置的奇数插入到最前面
                int bVal = array[b];
                for(int j=b;j>=a+1;j--) array[j] = array[j - 1];
                array[a] = bVal;
            }
         }
    }
};

太牛逼了

但是这个是不是还有排序过，题目的答案

真的很像二分和快排

二分快排！

为啥这种写法会 sf 呀？

class Solution {
public:
    void reOrderArray(vector<int> &array) {
    vector<int> ::iterator p=array.begin();
    vector<int> ::iterator q=array.end()-1;
    while(p<q)
    {
        if(*p%2==0)
        {


        if( *q%2!=0)
        {
            int t=*p;
            *p=*q;
            *q=t;
        }
        else 
        q--;
        }
        else
        p++;



    }



    }
};

我照着Y总的做法写了一遍，为啥输出的是[1, 5, 3, 4, 2] 而不是[1,3,5,2,4]呢？

可能是题目说把偶数全放后面，奇数全放前面，没有说按顺序放吧

那我就放心了

while (l < r && array[l] % 2 == 1) l ++ ;这个while循环岂不是一直跳不出来

碰上偶数不就跳出来了吗

最差的情况数组中全是奇数，i会一直加到j然后退出