奇偶交换排序

数据结构上机实验报告题目：奇偶交换排序学生姓名学生学号学院名称计算机学院专业计算机科学与技术时间2015.01.13I目录第一章需求分析..................................11.1原题表述.....................................11.2问题解决方案.................................1第二章概要设计..................................22.1抽象数据类型.................................22.2主要算法描述.................................22.3主要算法分析.................................3第三章详细设计..................................43.1程序代码.....................................4第四章调试分析..................................64.1出现的问题及解决方法.........................6第五章测试分析..................................75.1测试样例.....................................7计算机学院2013级数据结构上机实验报告1第一章需求分析1.1原题表述奇偶交换排序是另一种交换排序。算法的基本思想如下：排序过程通过对文件x[i]（l≤i≤n）的若干次扫描来完成，第奇数次扫描，对所有下标为奇数的记录x[i]与其后面的记录x[i+1]（l≤i≤n–1）相比较，若x[i].KEY（记录x[i]的key值）＞x[i+1].KEY，则交换x[i]和x[i+1]的内容；第偶数次扫描，对所有下标为偶数的记录x[i]与其后面的记录x[i+1]（2≤i≤n–1）相比较，若x[i].KEY＞x[i+1].KEY，则交换x[i]和x[i+1]之内容。一趟奇数次扫描和一趟偶数次扫描被称为一趟奇偶扫描。重复上述过程直到排序完成为止。设计奇偶排序函数，对于任意输入元素，输出排序过程。1.2问题解决方案题目需要建立建立一种新的排序方式，奇数趟对数组中的所有奇数项扫描，偶数趟对序列中的所有偶数项扫描。若A[i]A[i+1]，则交换它们。如此反复，最后得出排好的序列为止，最后的终止条件是进行一趟排序对比时，不在出现A[i]A[i+1]的情况计算机学院2013级数据结构上机实验报告2第二章概要设计2.1抽象数据类型无2.2主要算法描述intOddEvenSort(ints[],intn){inti,exchange=1,temp,num=0;while(exchange!=0)//;do{exchange=0;//扫描所有奇数项for(i=1;in-1;i+=2){//相邻两相比较，发生逆序if(s[i]s[i+1]){exchange=1;//做交换标记//交换temp=s[i];s[i]=s[i+1];s[i+1]=temp;}}if(exchange){num++;exchange=0;for(intw=0;wn;w++)printf(%d,s[w]);printf(\n);}for(i=0;in-1;i+=2){//相邻两相比较，发生逆序if(s[i]s[i+1]){exchange=1;//做交换标记//交换temp=s[i];s[i]=s[i+1];计算机学院2013级数据结构上机实验报告3s[i+1]=temp;}}if(exchange){num++;for(intt=0;tn;t++)printf(%d,s[t]);printf(\n);}}//while(exchange!=0);returnnum;}2.3主要算法分析OddEvenSort(ints[],intn)的时间复杂度为O（n2）;计算机学院2013级数据结构上机实验报告4第三章详细设计3.1程序代码#includestdio.hintOddEvenSort(ints[],intn){inti,exchange=1,temp,num=0;while(exchange!=0)//;do{exchange=0;//扫描所有奇数项for(i=1;in-1;i+=2){//相邻两相比较，发生逆序if(s[i]s[i+1]){exchange=1;//做交换标记//交换temp=s[i];s[i]=s[i+1];s[i+1]=temp;}}if(exchange){num++;exchange=0;for(intw=0;wn;w++)printf(%d,s[w]);printf(\n);}for(i=0;in-1;i+=2){//相邻两相比较，发生逆序if(s[i]s[i+1]){exchange=1;//做交换标记//交换temp=s[i];s[i]=s[i+1];s[i+1]=temp;计算机学院2013级数据结构上机实验报告5}}if(exchange){num++;for(intt=0;tn;t++)printf(%d,s[t]);printf(\n);}}//while(exchange!=0);returnnum;}intmain(){intn;printf(请输入数组位数：);scanf(%d,&n);ints[n];printf(请依次输入数组数据：\n);for(inti=0;in;i++){intnumber;scanf(%d,&number);s[i]=number;}printf(未排序前数组数据为：\n);for(inti=0;in;i++)printf(%d,s[i]);printf(\n);printf(排序过程：\n);intsum=OddEvenSort(s,n);printf(排序后数组数据为：\n);for(inti=0;in;i++)printf(%d,s[i]);printf(\n);printf(总排序趟数为：%d\n,sum);}计算机学院2013级数据结构上机实验报告6第四章调试分析4.1出现的问题及解决方法对程序加入查看未排序数组、排序后数组以及数组排序趟数的代码，然后根据结果，进行人工校验。根据编译器的提醒，修正代码错误，然后输入数据进行调试。最终校验输出结果，检查正误。计算机学院2013级数据结构上机实验报告7第五章测试分析5.1测试样例图5-1