面试题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;
}

补充：软件开发 , C++ ,

上一个：面试题13：链表中倒数第k个结点
下一个：面试题11：在O(1)时间删除链表结点