面试题21:调整数组顺序使奇数位于偶数前面 C++

题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有
奇数位于数组的前半部分，所有偶数位于数组的后半部分。

分析：
1.直接法
2.前后指针交替法 , 类似快速排序

#include <iostream>      
using namespace std;

void reorder(int *pData, int length)
{
    if (pData == nullptr || length == 0)
        return;
    int *pBegin = pData;
    int *pEnd = pData + length-1;

    while (pBegin < pEnd)
    {
        while (pBegin < pEnd && (*pBegin & 0x1) == 0)
            pBegin++;
        
        while (pBegin < pEnd && (*pEnd & 0x1) != 0)
            pEnd--;

        if (pBegin < pEnd)
        {
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
        }

    }
}
 
void print_array(int *pData, int length)
{
    for (int i = 0; i < length; i++)
    {
        cout << pData[i] << ' ';
        if (i == length - 1)
            cout << endl;
    }
}

int main() {
     
    int length;
    cin >> length;
    int *pData=new int[length];
    memset(pData, 0, length*sizeof(pData));
    for (int i = 0; i < length; i++)
         cin >> pData[i];
    cout << "origin : ";
    print_array(pData, length);
    
    reorder(pData, length);

    cout << "reorder : ";
    print_array(pData, length);


    return 0;
}

test

扩展：注意func作为函数形参bool (*func)(int)

#include <iostream>      
using namespace std;

void reorder(int *pData, int length,bool (*func)(int))
{
    if (pData == nullptr || length == 0)
        return;
    int *pBegin = pData;
    int *pEnd = pData + length-1;

    while (pBegin < pEnd)
    {
        while (pBegin < pEnd && !func(*pBegin))
            pBegin++;
        
        while (pBegin < pEnd &&  func(*pEnd))
            pEnd--;

        if (pBegin < pEnd)
        {
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
        }

    }
}
bool isEven(int n)
{
    return ((n & 0x1) == 0);
}
void print_array(int *pData, int length)
{
    for (int i = 0; i < length; i++)
    {
        cout << pData[i] << ' ';
        if (i == length - 1)
            cout << endl;
    }
}

int main() {
     
    int length;
    cin >> length;
    int *pData=new int[length];
    memset(pData, 0, length*sizeof(pData));
    for (int i = 0; i < length; i++)
         cin >> pData[i];
    cout << "origin : ";
    print_array(pData, length);
    
    reorder(pData, length,isEven);

    cout << "reorder : ";
    print_array(pData, length);


    return 0;
}