C语言：调整奇数偶数顺序

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

比如现在有数组arr： 1 2 3 4 5 6

思路1：大部分同学第一想法可能就是，把数组arr遍历一遍，找出其中奇数，放到新数组arr1中
再把arr遍历一遍，找出其中偶数，放到数组arr2中。
最后把arr1里的数和arr2里的数再放回arr中。
但是这种方法你从头到尾要遍历3次arr，时间复杂度大了，纯纯的暴力求解

思路2：我们可以把定义一个left和right分别标记数组首元素和数组末尾元素

left遇到偶数停下，否则left++
right遇到奇数停下，否则right–

交换left和right下标的值

left继续++,遇到偶数停下
right继续–，遇到奇数停下
然后left和right交换
…

循环一直到left>=right时结束
这样，我们就只需要遍历一次数组arr就可以实现奇数在前，偶数在后了

具体代码如下：

int main()
{
	int n = 0;
	int arr[100] = { 0 };//这里假设数组大小不超过100
	printf("请输入你要测试的数组大小:");
	scanf("%d", &n);
	printf("请输入数组元素：");
	for (int i = 0;i < n;i++)
	{
		scanf("%d", &arr[i]);
	}
	
	int left = 0;
	int right = n-1;

	while (left < right)
	{
		while (arr[left] % 2 != 0)//left遇到偶数停下
		{
			left++;
		}
		if (left >= right)//防止遇到全奇数的情况，如果遇到全奇数，没有这个if，left会越界
		{
			break;
			//这里直接left一路走，已经比right大了，就可以直接跳出循环，下面就不用再走了
		}


		while (arr[right] % 2 != 1)//right遇到奇数停下
		{
			right--;
		}
		if (left < right)//这里需要额外判断一下是否left
			//比如      1 2 3 4 5 6 7 8 9 10
			//已经变成了1 9 3 4 5 6 7 8 2 10
			//left指向4,right指向了7，两者交换
			//得到      1 9 3 7 5 6 4 8 2 10
			//此时的left还是小于right的，所以还是可以进入下一次循环
			//但是最后一次循环left指向了6，right指向了5，这时就要if判断一下来中断交换
			int tmp = arr[left];
			arr[left] = arr[right];
			arr[right] = tmp;
		}
	}
	
	printf("n");
	for (int i = 0;i < n;i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

测试1：

测试2：