OJ题库：奇偶数排序（使奇数全部都位于偶数前面）

痛定思痛。 2023-10-14 19:37 32阅读 0赞

**前言：**在部分大厂笔试时经常会使用[OJ][]题目，这里对《奇偶数排序》进行思路分析和讲解，在这里主要使用俩种方法进行讲解，希望对各位读者有所帮助。

**目录**

一.方法一（简单但是费空间）

设计思路：

实现细节：

完整代码实现：

运行结果示例：

二.方法二（高效但稍微难想）

设计思路：

实现细节：

完整代码实现：

运行结果示例：

--------------------

## 一.方法一（简单但是费空间） ##

### 设计思路： ###

第一种方法很简单，既然我们的目的是将奇数放在一块，偶数放在一块的话，那我们只需要分别拿到俩部分数据，然后分别放在俩个不同的数组中，最后再将俩个数组拼接在一起，放在最初始的数组中， 就完成了我们的目标

**如图所示：**

![cf5801a0c8ba4ed684de7f9d99129bb8.png][]![9f412390d92942cb9beeb258fdd89b98.png][]![142dd2d893d94038913ee6bbb41ece44.png][]

### 实现细节： ###

**放入：**为了完成上述的算法，我们需要初始化三个数组，一个原始数组用来记录从键盘输入的数，剩下俩个分别用来记录奇数和偶数。我们要拿到原始数组中的奇数和偶数，就先得遍历整个数组，从第一个开始，对其进行判断，如果是奇数，那就使用指针放入奇数数组中，然后奇数数组中的指针加一，同时原始数组中的指针也加一，遍历偶数也是同理，这里就不再继续赘述。

**放回：** 这个算法中，稍微有点难度的就是放回的步骤，首先，我们输入的数组不一定奇数和偶数一样多，那么在放入的时候就得使用个临时变量来记录有多少个奇数或者偶数，每放一次，这个临时变量就减一，当减为零的时候就停止放入奇数，然后从这个位置开始再放入偶数。

### 完整代码实现： ###

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    #include<windows.h>
    
    void myarr(int* p,int len)
    {
    	int* arr = p;//保存首地址
    	int odd[10] = { 0 };//记录奇数
    	int even[10] = { 0 };//记录偶数
    	int n = 0;//记录奇数的个数
    	int i = 0;
    	int j = 0;
    	while(len)
    	{
    		//判断是奇数
    		if (*arr % 2 == 1)
    		{
    			odd[i] = *arr;
    			i++;
    			n++;
    		}
    		//判断是偶数
    		else
    		{
    			even[j] = *arr;
    			j++;
    		}
    		arr++;
    		len--;
    	}
    	arr = p;
    	//先将数组的前半部分放入奇数
    	for (int i = 0; i < n; i++)
    	{
    		*(arr + i) = odd[i];
    	}
    	//剩下的部分放偶数
    	for (int i = n; i < 10; i++)
    	{
    		*(arr + i) = even[i-n];
    	}
    }
    
    int main()
    {
    	int arr[10] = {0};
    	for (int i = 0; i < 10; i++)
    	{
    		scanf("%d", &arr[i]);
    	}
    
    	int len = sizeof(arr) / sizeof(arr[0]);
    	myarr(arr,len);
    
    	for (int i = 0; i < 10; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    
    	system("pause");
    
    	return 0;
    }

### 运行结果示例： ###

> **我们可以观察到，数据确实是按照前面是奇数后面是偶数的方式排列的，并且数据之间的相对顺序也没有变**
> 
> ![5dbcdc6e27af40018bd331c99af417bf.png][]![e91c9b1d03854c3cbfc9a0cc0d2e493b.png][]

## 二.方法二（高效但稍微难想） ##

### 设计思路： ###

方法二是基于反复交换的思路的，前后俩个数字无非就俩种状态——奇数和偶数，那假如前面是偶数，后面是奇数，将他们交换我们就达到了前面放奇数后面放偶数的目的，交换成功后，我们进行下一次交换，使用指针来达到这种类似于移动的操作，反正不进行操作，寻找下一个前偶数后奇数的组合进行交换，多次循环之后，我们就可以完成我们想要的排序

**如图所示：**

![ab2907f59dce495099f88892b854a913.png][]

###  实现细节： ###

**为了实现“移动”操作，我们需要俩个指针，分别指向数组的首部和尾部，执行以下操作步骤：**

> 1.  给定两个下标 **left** 和 **right** ， **left** 放在数组的起始位置， **right** 放在数组中最后一个元素的位置
> 2.  循环进行一下操作
> 
>  *   a. 如果 **left** 和 **right** 表示的区间 **\[ left, right \]** 有效，进行 **b** ，否则结束循环
>  *   b. **left** 从前往后找，找到一个偶数后停止
>  *   c. **right** 从后往前找，找到一个奇数后停止
>  *   d. 如果 **left** 和 **right**都找到了对应的数据，则交换，继续a，

###  完整代码实现： ###

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    #include<windows.h>
    
    void swap_arr(int arr[], int sz)
    {
    	int left = 0;
    	int right = sz - 1;
    	int tmp = 0;
    
    
    	while (left < right)
    	{
    		// 从前往后，找到一个偶数，找到后停止
    		while ((left < right) && (arr[left] % 2 == 1))
    		{
    			left++;
    		}
    
    		// 从后往前找，找一个奇数，找到后停止
    		while ((left < right) && (arr[right] % 2 == 0))
    		{
    			right--;
    		}
    
    		// 如果偶数和奇数都找到，交换这两个数据的位置
    		// 然后继续找，直到两个指针相遇
    		if (left < right)
    		{
    			tmp = arr[left];
    			arr[left] = arr[right];
    			arr[right] = tmp;
    		}
    	}
    }
    
    int main()
    {
    	int arr[10] = {0};
    	for (int i = 0; i < 10; i++)
    	{
    		scanf("%d", &arr[i]);
    	}
    
    	int len = sizeof(arr) / sizeof(arr[0]);
    	swap_arr(arr,len);
    
    	for (int i = 0; i < 10; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    
    	system("pause");
    
    	return 0;
    }

### 运行结果示例： ###

> **我们可以观察到，数据确实是按照前面是奇数后面是偶数的方式排列的，但是数据之间的相对顺序是发生变化了的**
> 
> ![cc2fe7c5043e40c28f556fd96448f275.png][]![a0ba77a534ba4bbb98a7ee21e93e2860.png][]

**综上，俩个方法对于空间的利用效率并不相同，但都能完成我们的期望目标，但是值得注意的是，第二种方法并不能保证排序后数字之间的相对顺序保持不变，本次分享就到此结束了，希望我的分享对您有所帮助**

[OJ]: https://so.csdn.net/so/search?q=OJ&spm=1001.2101.3001.7020
[cf5801a0c8ba4ed684de7f9d99129bb8.png]: https://img-blog.csdnimg.cn/cf5801a0c8ba4ed684de7f9d99129bb8.png
[9f412390d92942cb9beeb258fdd89b98.png]: https://img-blog.csdnimg.cn/9f412390d92942cb9beeb258fdd89b98.png
[142dd2d893d94038913ee6bbb41ece44.png]: https://img-blog.csdnimg.cn/142dd2d893d94038913ee6bbb41ece44.png
[5dbcdc6e27af40018bd331c99af417bf.png]: https://img-blog.csdnimg.cn/5dbcdc6e27af40018bd331c99af417bf.png
[e91c9b1d03854c3cbfc9a0cc0d2e493b.png]: https://img-blog.csdnimg.cn/e91c9b1d03854c3cbfc9a0cc0d2e493b.png
[ab2907f59dce495099f88892b854a913.png]: https://img-blog.csdnimg.cn/ab2907f59dce495099f88892b854a913.png
[cc2fe7c5043e40c28f556fd96448f275.png]: https://img-blog.csdnimg.cn/cc2fe7c5043e40c28f556fd96448f275.png
[a0ba77a534ba4bbb98a7ee21e93e2860.png]: https://img-blog.csdnimg.cn/a0ba77a534ba4bbb98a7ee21e93e2860.png