调整数组顺序使奇数位于偶数前面（C语言）

调整数组顺序使奇数位于偶数前面（C语言）

文章目录

• 方法一：不考虑相对顺序
• 方法二：考虑相对顺序

让我们来看一看这道题。

首先我们的想法肯定是用指针，但是怎么用，又会产生出不同的解法。

方法一：不考虑相对顺序

先看第一种解法：

基本思路：
定义两个指针 left 和 right （一个在头，一个在尾），使 left 往右移，跳过奇数，直到指向的值为偶数。使right 往左移，跳过偶数， 直到指向的值为奇数。当它们都停下时，交换两个指针分别指向的值，重复上述 *** 作，直至两个指针完成任务。

void exchange(int* nums, int numsSize)
{
	int left = 0;               //让left指向头
	int right = numsSize - 1;  //让right指向尾
	while (left < right)   //循环条件
	{

		while ((nums[left] & 1) == 1 && left < right)  //left跳过奇数，直至停在偶数
		{
			left++;
		}

		while ((nums[right] & 1) == 0 && left < right)  //right跳过偶数，直至停在奇数
		{
			right--;
		}

		if (left < right)  //交换条件，防止交换结果不满足要求
		{
			int tmp = nums[left];
			nums[left] = nums[right];
			nums[right] = tmp;
		}

	}
}

这里还有一个细节，就是里面的两个while循环条件中的 left < right 都是不能不写的。
如果都不写的话，当传进去的是一个全是奇数或者全是偶数的数组时，那么会造成数组的越界访问（不一定报错）。这就告诉我们，要尽可能的考虑周全，尤其是某些特殊的测试用例。

但是上面的这种方法也有不好的地方，那就是它会把奇数间或者偶数间原有的相对顺序给打乱，那么有没有别的方法能补足这个缺陷呢？
答案是有的。

方法二：考虑相对顺序

比如下面的这种方法：

void exchange(int* nums, int numsSize)
{
	int i = 0;     //首先将i初始化为0
	for (int j = 0; j < numsSize; j++) 
	{
		if (nums[j] & 1 == 1)   
		{
			int tmp = nums[j];    
			for (int k = j - 1; k >= i; k--)  
			{
				nums[k + 1] = nums[k];  
			}
			nums[i++] = tmp; 
		}
	}
}

基本思路：
让指针 j 从头开始向后遍历，遇到奇数就停下，然后用临时变量 tmp 存一下该奇数，将指针 i （指针i前面的都是奇数）到指针 j 之间的偶数都向后移动一个位置，然后将 tmp 的值放进前面因移动而多出的一个空位上，再让指针 i 指向后一个位置。重复上面的 *** 作，直至 j 遍历完整个数组。

可能还有别的方法，如果有兴趣，可以继续思考别的解法。

更多文章：
让你理解选择排序（C语言）
让你搞懂冒泡排序（C语言）