【数据结构周周练】034 奇偶排序算法原理详解（上海大学832计算机组成原理与数据结构原题）

迈不过友情╰ 2021-06-11 15:13 390阅读 1赞

## 一、冒泡排序 ##

### 1、奇偶排序简介 ###

奇偶排序算法不是严蔚敏老师书上的算法，是今年上海大学计算机考研（832计算机组成原理与数据结构）的一道考试题，听朋友说了之后感觉很不错，给大家分享一下。

题目大致含义如下：

已知奇偶交换排序如下所述：
    
    1.第一趟对序列中所有奇数项i扫描，将a[i]和a[i+1]进行比较；
    2.第二趟对序列中所有偶数项i扫描，将a[i]和a[i+1]进行比较。
    3.每次比较时若 a[i]>a[i+1]，则将两者交换。
    4.第三趟对所有奇数项，第四趟对所有偶数项……，如此重复，直至整个序列有序。
    5.写出奇偶交换排序算法

### 2、算法思想及流程 ###

这个算法原理是也是比较简单的，接下来就给大家分享一下我的做法。以下面这几个数据来模拟方便大家理解：

**给定一组数据如下：1，3，5，2，8，6，4，7**

**第一趟排序，对所有奇数项扫描，如果比后一项大，交换：**

**\[1，3\]，\[5，2\]，\[8，6\]，\[4，7\]   => ** **\[1，3\]，\[2，5\]，\[6，8\]，\[4，7\]**

**第二趟排序，对所有偶数项扫描，如果比后一项大，交换：**

**1，\[3，2\]，\[5，6\]，\[8，4\]，7  =>  1，\[2，3\]，\[5，6\]，\[4，8\]，7**

**第三趟排序，对所有奇数项扫描，如果比后一项大，交换：**

**\[1，2\]，\[3，5\]，\[6，4\]，\[8，7\]   =>  \[1，2\]，\[3，5\]，\[4，6\]，\[7，8\]**

**第四趟排序，对所有偶数项扫描，如果比后一项大，交换：**

**1，\[2，3\]，\[5，4\]，\[6，7\]，8  =>  1，\[2，3\]，\[4，5\]，\[6，7\]，8 **

通过这个分析，我想大家对这个；排序过程应该有比较深刻的了解了，我们会注意到两个问题：

**1，一串数据可能有奇数个，可能有偶数个，怎么保证它不访问最后一个，导致出错呢？**

**答：我们可以通过设置循范围，当循环变量到总个数-1时，停止循环。**

**2，我们人眼能分辨到第四趟停止，计算机怎么实现呢？**

**答：我们设置两个中间变量m，n来控制，如果奇排序过程中有元素交换，m为1，否则为0；如果偶排序过程中有元素交换，n为1，否则为0。当mn同时为0时，说明奇偶都没有交换，这个时候说明数据有序。**

接下来分享我的全部代码。

## 二、全部代码 ##

刚才上面是分析，接下来我将所有的代码分享一下。为了更好的看效果，我找了奇数个数字（因为示例是偶数个数字），并且换了一组数字来测试。

#include<iostream>
    using namespace std;
    
    void Sort(int Arr[], int length) {
    	int temp;
    	int m = 1;
    	int n = 1;
    	while (m||n)
    	{
    		for (int i = 0; i < length - 1; i = i + 2)
    		{
    			if (Arr[i] > Arr[i + 1])
    			{
    				temp = Arr[i];
    				Arr[i] = Arr[i + 1];
    				Arr[i + 1] = temp;
    				m = 1;
    			}
    			else
    				m = 0;
    		}
    		for (int j = 1; j < length - 1; j = j + 2)
    		{
    			if (Arr[j] > Arr[j + 1])
    			{
    				temp = Arr[j];
    				Arr[j] = Arr[j + 1];
    				Arr[j + 1] = temp;
    				n = 1;
    			}
    			else
    				n = 0;
    		}
    	}
    }
    
    void OutputArr(int Arr[], int length) {
    	for (int i = 0; i < length; i++)
    	{
    		cout << Arr[i] << ", ";
    
    	}
    	cout << endl;
    }
    
    void main() {
    	int Arr[] = { 45,57,12,31,1,60,92,71,87 };
    	Sort(Arr, 9);
    	OutputArr(Arr, 9);
    }

## 三、运行结果 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_25_color_9F5790_t_70][]

这个算法并不唯一，如果大家有更好的算法，可以在下面分享，大家有什么问题也可以在下面留言哦！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_25_color_9F5790_t_70]: /images/20210516/c87c0a9d0be345b9a5f643d7b977add9.png