2020考研东南935数据结构算题

﹏ヽ暗。殇╰゛Y 2023-06-25 04:54 40阅读 0赞

# **题目描述**  #

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

# 解题思路 #

这道题有两点要求：1.把所有的奇数调整到偶数前面。2.要保持稳定性。  
像这种要求按一定规则调整顺序的题，都可以看成类似排序的题。在此题中要求奇数在前，偶数在后，我们可以把奇数看成较小的值，偶数是较大的值，相当于对一个只有两种值的数组（例如【1,2,2,1,2,1,2,2,1,2】）进行排序，且要保持稳定性。当这个问题转换成类似数组排序的问题后，就可以用一些常见的排序算法解决此类问题。常见的稳定性排序算法有，冒泡排序、插入排序、归并排序等。以冒泡排序为例分析下解决此题的过程。  
假设这个奇偶数组是这样的（为了标识各个奇数间，偶数间相对位置，加上了序号，序号不影响排序过程）：  
![图片描述][format_png]  
从左至右进行进行第一趟冒泡过程，第一个元素与第二个元素比较，如果左边是奇数右边是偶数（按照上面是思路如果把奇数偶数看成数值的话相当于左边比右边小）无需交换；如果左边是偶数，右边是奇数，则交换两个数；如果都是奇数或偶数，则无需交换。完成第一个元素与第二个元素交换后，再比较第二个元素与第三个元素，重复上面的操作。直到比较完最后两个元素，则第一趟冒泡过程结束。可以得到如下数组：

![clipboard.png][]  
通过这一趟的冒泡后，在偶数集合中原本就属于最后的元素“偶数2”被交换到了数组的最后面，而按照题目要求它最终就要处于这个位置。这就是冒泡排序的性质：每趟交换后将最大（或最小）的元素移动到最末尾。既然元素“偶数2”已经被移动到了题意中要求的位置，就不用再对它操作了，下一趟冒泡过程只需要要操作到倒数第二个元素即可。  
重复上面的思路，每次都可以确定一个元素的最终位置，最终所以的元素都可以被交换到固定的位置。最终排序的数组如下所示：

![clipboard.png][clipboard.png 1]  
可以看到，完成了冒泡排序之后的数组，所有的奇数都位于偶数前面，且奇数与奇数间，偶数与偶数间相对位置都没改变，符合题意要求。从这道题，可以得到一类题的解题思路。

/*输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
    使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分，
    并保证奇数和奇数，偶数和偶数之间的相对位置不变。*/ 
    #include <iostream>
    using namespace std;
    
    void reOrderArray (int arr[], int n) {
    	for(int i=0; i<n; i++) {
    		for(int j=0; j<n-1-i; j++) {
    			if(arr[j]%2==0 && arr[j+1]%2==1) { //如果左边是偶数，右边是奇数则交换他们 
    				int temp = arr[j];
    				 arr[j] = arr[j+1];
    				 arr[j+1] = temp;
    			} 
    		}
    	}
    }
    
    int main(){
    	int arr[10] = {1,2,3,4,5,6,7,8,9,10};
    	reOrderArray(arr, 10);
    	for(int i=0; i<10; i++) {
    		cout << arr[i];
    	} 
    	return 0;
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zZWdtZW50ZmF1bHQuY29tL2ltZy9iVmJ4bjdm?x-oss-process=image/format,png
[clipboard.png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zZWdtZW50ZmF1bHQuY29tL2ltZy9iVmJ4b293?x-oss-process=image/format,png
[clipboard.png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zZWdtZW50ZmF1bHQuY29tL2ltZy9iVmJ4b3Jh?x-oss-process=image/format,png