Adjust the array order so that odd numbers precede even numbers (C language)

Let's take a look at this problem .

subject ： Enter an array of integers , Implement a function to adjust the order of the Numbers in the array , Make all odd numbers in the first half of the array , All even numbers are in the second half of the array .

Title source （ Power button ）： Adjust the array order so that the odd Numbers precede the even Numbers

First of all, our idea must be to use pointers , But how to use , It will produce different solutions .

Method 1 ： Regardless of relative order

Let's look at the first solution ：

The basic idea ：
Define two pointers left and right （ One in the head , One at the end ）, send left Move right , Skip odd , Until the value pointed to is even . send right Move left , Skip the even , Until the value pointed to is an odd number . When they all stop , Exchange the values pointed to by two pointers respectively , Repeat the above operation , Until two pointers complete the task .

void exchange(int* nums, int numsSize)
{
    
	int left = 0;               // Give Way left Point to the head 
	int right = numsSize - 1;  // Give Way right Pointing tail 
	while (left < right)   // The loop condition 
	{
    

		while ((nums[left] & 1) == 1 && left < right)  //left Skip odd , Until it stops at an even number 
		{
    
			left++;
		}

		while ((nums[right] & 1) == 0 && left < right)  //right Skip the even , Until it stops at an odd number 
		{
    
			right--;
		}

		if (left < right)  // Exchange terms , Prevent the exchange result from not meeting the requirements 
		{
    
			int tmp = nums[left];
			nums[left] = nums[right];
			nums[right] = tmp;
		}

	}
}

Here's another detail , Just the two inside while In cyclic conditions left < right All of them have to be written .
If you don't write , When an array of odd or even numbers is passed in , That would cause Out of bounds access to arrays （ Not necessarily wrong ）. That tells us , Be as thoughtful as possible , Especially some special test cases .

But the above method also has some disadvantages , That is, it will disturb the original relative order between odd numbers or even numbers , Is there any other way to make up for this defect ？
The answer is yes .

Method 2 ： Consider the relative order

For example, the following method ：

void exchange(int* nums, int numsSize)
{
    
	int i = 0;     // First of all, will i Initialize to 0
	for (int j = 0; j < numsSize; j++) 
	{
    
		if (nums[j] & 1 == 1)   /*  Conditions for entry ：nums[j] Is odd  */
		{
    
			int tmp = nums[j];    /*  use tmp Save it nums[j] */
			for (int k = j - 1; k >= i; k--)  /*  take i and j Even numbers between move back one position  */
			{
    
				nums[k + 1] = nums[k];  
			}
			nums[i++] = tmp; /* take  tmp  The value of is put into an extra space in front due to movement , Let the pointer  i  Point to the latter position  */
		}
	}
}

The basic idea ：
Let the pointer j Traverse backwards from the beginning , Stop at odd numbers , And then use temporary variables tmp Save the odd number , Put the pointer i （ The pointer i The preceding ones are all odd numbers ） To pointer j Even numbers between move back one position , And then tmp The value of is put into an extra space in front due to movement , Let the pointer i Point to the latter position . Repeat the above , until j Traverse the entire array .

There may be other ways , If you are interested , You can continue to think about other solutions .

More articles ：
Let you understand the sorting of choices （C Language ）
Let you understand bubble sort （C Language ）