笔试题3——给定一个整形数组，使得奇数在偶数前面

这道题是厦门大学某一年的考研题，也是一道笔试时经常考的题目

这道题类似于快速排序 第一趟排玩的结果，将数组分成前后两部分；我们用这种相似的方法解这道算法题

要求：时间复杂度在O(n)内完成，且只能遍历一次，不能重新分配数组

void OddBeforeEven(int a[], int iLength)
{
    if (a == NULL || iLength <= 1)
        return;
    int iStart = 0;
    int iEnd = iLength - 1;
    while (iStart < iEnd)
    {
        while (iStart < iEnd)
        {
            if ((a[iStart] & 1) == 0)  //从前开始依次判断是否为奇数，直到找到偶数
                break;
            iStart++;
        }
        while (iStart < iEnd)
        {
            if ((a[iStart] & 1) == 1)  //从前开始依次判断是否为偶数，直到找到奇数
                break;
            iEnd--;
        }
        if (iStart < iEnd)             //交换两个数，位操作效率高些，当然可以定义临时变量
        {
            a[iStart] ^= a[iEnd];      //按位异或
            a[iEnd]   ^= a[iStart];
            a[iStart] ^= a[iEnd];
        }
    }
}

代码是不是很舒服
注意：交换两个数，当然可以定义一个临时变量，从而交换两个数，
那如果有面试官问你交换两个数不能定义临时变量或者有没有更高效的方法，
那你可以使用上述的按位异或的方法交换两个数，从而获得面试官的青睐。