面試題12：調整數組順序使奇數位於偶數前

思路：

1. 設置兩個指針，初始狀態第一指針指向數組的第一個數，第二個指針指向數組的最後一個數；

2. 若第一個指針指向的數是奇數，則指針向右移動一位，第二個指針指向的數是偶數，則指針向左移動；

3. 若第一個指針和第二個指針指向的數恰好分別為偶數和奇數，則交換數字。

代碼：

#include "stdafx.h"   
#include <iostream>   
using namespace std;  
  
void ReorderOddEven(int *nArr, int nLength)  
{  
    if (nArr != NULL && nLength > 0)  
    {  
        int low = 0;  
        int high = nLength -1;  
  
        while (low < high)  
        {  
            while ((low<high) && (nArr[low]&1) == 1)//奇數   
            {  
                low++;  
            }  
  
            while ((low<high) &&(nArr[high]&1) == 0)//偶數   
            {  
                high--;  
            }  
  
            if (low < high)  
            {  
                int temp = nArr[low];  
                nArr[low] = nArr[high];  
                nArr[high] = temp;  
            }  
        }          
    }  
}  
  
void PrintArr(int *nArr, int nLength)  
{  
    for (int i=0; i<nLength; i++)  
    {  
        cout << nArr[i] << " ";  
    }  
    cout << endl;  
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    int nArr1[5] = {1, 2, 3, 4, 5};  
    ReorderOddEven(nArr1, 5);  
    PrintArr(nArr1, 5);  
  
    int nArr2[5] = {1, 1, 1, 1, 1};  
    ReorderOddEven(nArr2, 5);  
    PrintArr(nArr2, 5);  
  
    int nArr3[5] = {2, 2, 2, 2, 2};  
    ReorderOddEven(nArr3, 5);  
    PrintArr(nArr3, 5);  
  
    int nArr4[5] = {-1, -2, -1, -1, -1};  
    ReorderOddEven(nArr4, 5);  
    PrintArr(nArr4, 5);  
    return 0;  
}  
#include "stdafx.h"
#include <iostream>
using namespace std;

void ReorderOddEven(int *nArr, int nLength)
{
	if (nArr != NULL && nLength > 0)
	{
		int low = 0;
		int high = nLength -1;

		while (low < high)
		{
			while ((low<high) && (nArr[low]&1) == 1)//奇數
			{
				low++;
			}

			while ((low<high) &&(nArr[high]&1) == 0)//偶數
			{
				high--;
			}

			if (low < high)
			{
				int temp = nArr[low];
				nArr[low] = nArr[high];
				nArr[high] = temp;
			}
		}        
	}
}

void PrintArr(int *nArr, int nLength)
{
	for (int i=0; i<nLength; i++)
	{
		cout << nArr[i] << " ";
	}
	cout << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int nArr1[5] = {1, 2, 3, 4, 5};
	ReorderOddEven(nArr1, 5);
    PrintArr(nArr1, 5);

	int nArr2[5] = {1, 1, 1, 1, 1};
	ReorderOddEven(nArr2, 5);
	PrintArr(nArr2, 5);

	int nArr3[5] = {2, 2, 2, 2, 2};
	ReorderOddEven(nArr3, 5);
	PrintArr(nArr3, 5);

	int nArr4[5] = {-1, -2, -1, -1, -1};
	ReorderOddEven(nArr4, 5);
	PrintArr(nArr4, 5);
	return 0;
}