如何重新排列数组使得数组左边为奇数，右边为偶数，并使得空间复杂度为O(1)，时间复杂度为O(n)

思路分析：

类似快速排序的处理。可以用两个指针分别指向数组的头和尾，头指针正向遍历数组，找到第一个偶数，尾指针逆向遍历数组，找到第一个奇数，使用引用参数传值交换两个指针指向的数字，然后两指针沿着相应的方向继续向前移动，重复上述步骤，直到头指针大于等于尾指针为止。

代码如下：

#include "stdafx.h"

#include <iostream>

using namespace std;

void Swap(int& a, int& b)

{

	int temp = a;

	a = b;

	b = temp;

}

void ReverseArray(int arr[], int len)

{

	if (arr == NULL || len <= 0)

		printf("数组中无元素，变换毛线啊。");

	else

	{

		int begin = 0;

		int end = len - 1;

		while (begin < end)

		{

			while (arr[begin] % 2 == 1 && end>begin)

				begin++;

			while (arr[end] % 2 == 0 && end > begin)

				end--;

			Swap(arr[begin], arr[end]);

		}

	}

}

int main()

{

	int array[] = { 1, 23, 2, 34, 21, 45, 26, 22, 41, 66, 74, 91, 17, 64 };

	int len = sizeof(array) / sizeof(array[0]);

	int i;

	printf("原数组为：");

	for (i = 0; i < len; i++)

		printf("%d ", array[i]);

	printf("\n");

	ReverseArray(array, len);

	printf("经过变换后的数组为：");

	for (i = 0; i < len; i++)

		printf("%d ", array[i]);

	printf("\n");

	getchar();

	return 0;

}

　　效果如图：

巴特西

如何重新排列数组使得数组左边为奇数，右边为偶数，并使得空间复杂度为O(1)，时间复杂度为O(n)

最新文章

热门文章