C language: adjust the order of odd and even numbers

输入一个整数数组,实现一个函数,来调整该数组中数字的顺序
to make all odd numbers in the array in the first half of the array.所有的偶数位于数组的后半部分.

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

思路1：The first thought of most students may be this,把数组arr遍历一遍,Find the odd number of them,放到新数组arr1中
再把arr遍历一遍,Find the even numbers among them,放到数组arr2中.
最后把arr1the sum ofarr2Put the numbers back inarr中.
But this method you have to traverse from beginning to end3次arr,The time complexity is large,Pure violence

思路2：We can define oneleft和rightMark the first element of the array and the last element of the array, respectively

leftStop on an even number,否则left++
rightStop at odd numbers,否则right–

交换left和right下标的值

left继续++,Stop on an even number
right继续–,Stop at odd numbers
然后left和right交换
…

循环一直到left>=right时结束
这样,We only need to iterate over the array oncearrYou can achieve odd numbers first,The even numbers are next

具体代码如下：

int main()
{
    
	int n = 0;
	int arr[100] = {
     0 };//This assumes that the array size does not exceed100
	printf("Please enter the size of the array you want to test:");
	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)//leftStop on an even number
		{
    
			left++;
		}
		if (left >= right)//Avoid encountering all odd cases,If all odd numbers are encountered,没有这个if,left会越界
		{
    
			break;
			//这里直接left一路走,已经比right大了,就可以直接跳出循环,No need to go any further
		}


		while (arr[right] % 2 != 1)//rightStop at odd numbers
		{
    
			right--;
		}
		if (left < right)//An additional judgment is required hereleft<right
		{
    
			//比如 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的,So you can still enter the next cycle
			//But the last loopleft指向了6,right指向了5,这时就要ifJudge it and interrupt the exchange
			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：