排序算法实现3.docx

《排序算法实现3.docx》由会员分享，可在线阅读，更多相关《排序算法实现3.docx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、河南工程学院数据结构与算法课程设计成果报告排序算法实现2014年12月29日2.4程序流程图开始开始显示菜单直接插入排序输入序号V折半插入排序简单项选择择排序按输入序号输出结果结束图1-2程序执行流程图开始执行后，会出现提示语句，提示6分别代表6种排序方法，对于生成 的数组，点击1-6任意数字，调用相应的排序方法进行排序。输出结果后，按任 意键结束。2. 5程序测试说明主函数会调用rand()方法，随机产生指定数目数值。并将数值赋予指定数 组，通过提示语句输入16数值，16分别代表不同的排序方式，当输入数字 1时，通过switch语句，将执行直接插入排序函数，然后通过输出函数，输出 所需结构。

2、3程序清单#include#include#includettdefine MAXE 20000typedef int KeyType;typedef struct/*记录类型*/(KeyType key;/*关键字项*/InfoType data;/*其他数据项，类型为 InfoTypeV RecType;void InsertSort(RecType R, int length);直接插入排序void BlnsertSort (RecType R, int low, int high, int length);折半插入排序 void ShellSort (RecType R, int n)

3、;希尔排序 void bubble_sort(RecType R, int length);起泡排序 int FindPos(RecType R, int low, int high);void Quicksort(RecType R,int low, int high);int SelectMinKey(RecType R, int i, int length);void SelectSort (RecType R, int length);简单项选择择排序void showSort (RecType R);快速排序void showSort F(RecType R);int main(vo

4、id) int val;int i;RecType RMAXE;srand (unsigned)time(NULL);for(i=0;i=10;i+)Ri. key= (rand()%100+l);printf(产生的随机数序列为：)； for(i=0;i=10;i+)printf(%3d，Ri. key);printf (n);printf (随机输入1到6数字：)； scanf(%d,&val);switch(val)case 1: InsertSort (R,10);printf(随机数经直接插入排序后：)； showSort(R);break;case 2:BlnsertSort(R,

5、 1, 10, 10);printf (随机数经折半插入排序后：)； showSort(R);break：case 3:ShellSort(R, 10);printf(随机数经希尔插入排序后：)； showSort_F(R);break;case 4:bubble_sort(R, 10);printf (随机数经起泡排序后：)； showSort_F(R);break;case 5:Quicksort(R, 0, 9);printf(随机数经快速排序后：)； showSortF(R);case 6:SelectSort(R, 10);printf (随机数经简单项选择择排序后：)； showS

6、ort_F(R);)return 0;void InsertSort(RecType R, int length) /对数组a作直接插入排序int i, j;for(i=2;i=length;+i)if (Ri. keyRi-l. key) / 需将 ai插入有序子表(R0. key=Ri. key; / 复制为哨兵Ri. key=RiT. key;for(j=i-2;R0. keyRj. key：j)Rj+1. key=Rj. key; / 记录后移Rj+1. key=R0. key; / 插入到正确位置void BlnsertSort (RecType R, int low, int hi

7、gh, int length) (int m;for ( int i=2; i=length; +i )(R0.key = REiLkey; / 将 Ri暂存到 R0low = 1;high = i-1;while ( low = high) 在Rlow. high中折半查找插入的位置m = (low+high)/2;/ 折半if (R0.key =high+l; j )Rj+1. key = Rj. key; / 记录后移REhigh+1. key = R0. key; / 插入 / BlnsertSort void ShellSort (RecType R, int n) /*希尔排序算法

8、*/ (int i, j, d, k;RecType temp;d=n/2;/*d 取初值 n/2*/while (d0) (for (i=d; i=0 & Rj. keyRj+d. key) (temp=Rj ;与 Rj+d交换*/Rj= Rj+d;Rj+d=temp;j二j-d;printf (，zd=%d: , d) ; /*输出每一趟的排序结果*/for (k=0;kn;k+)printf(3d，Rk.key);printf (n);d=d/2;/*递减增量d*/)void bubble_sort (RecType R, int length) /将a中整数序列重新排列成自小至大有序的

9、整数序歹U (起泡排序) int i, j, t;for(i=0;ilength-l;i+)(for(j=i+l；jRj. key)t=Ri. key;10Ri.key=Rj. key;Rj. key=t;)void Quicksort (RecType R, int low, int high)(int pos;if(lowhigh)pos=FindPos(R, low, high);Quicksort(R, low, pos-l);Quicksort(R, pos+1, high);)int FindPos (RecType R, int low, int high)(int val=Rl

10、ow. key;while(lowhigh)while(low=val)high;Rlow. key=Rhigh.key;while(1owhigh&R1ow. key=val) +low;Rhigh. key=Rlow, key;)Rlow, key=val;return high;)int SelectMinKey(RecType R, int i, int length) /返回在ai.length中key最小的记录的序号 int min;int j,k;k=i; /设第i个为最小 min=Ri. key;for(j=i+l;jlength;j+)if (Rj. keymin) / 找到

11、更小的(k二 j;min=Rj. key;return k;11void SelectSort (RecType R, int length) /对数组a作简单项选择择排序int i, j;int t;for(i=0;ilength-l;+i) /选择第i小的记录，并交换到位j=SelectMinKey (R, i, length) ; / 在 ai. . length中选择最小的记录 if(i!=j)与第i个记录交换t=Ri.key;Ri. key=Rj. key;Rjkey=t;void showSort(RecType R)(int i;for(i=l;i=10;i+) printf (

12、，z%d，z, RiL key);)printf (n);void showSort_F(RecType R)(int i;for(i=0;i10;i+) printf (z，%d z，, Ri. key);)printf (n);124测试4.1测试数据由函数rand()产生的随机数进行测试。4. 2测试结果分析79 52 24 21 54 9 4 46 39 83 28陋圳输入1期数字：1型机数经直接插入排序后：4 9 21 24 28 39 46 52 54 83Press any key to continue图-3直接插入排序当输入数字1时，主函数通过switch语句调用直接插入排序

13、，对数组进行 从小到大的排序。产生的随机数序列为:50 65 90 28 95 47 94 26 45 13 52 遁物颉人工到6数多4遁机数经起泡排序后：13 26 28 45 47 50 65 90 94 95Press any key to continue图1-4冒泡排序当输入数字4时，主函数通过switch语句调用冒泡排序，对数组进行从小 到大的排序。135总结通过这次课程设计的学习让我学会了许多，让我对专业知识有了初步的了 解。在这次课程设计中，首先实现随机数的生成，将生成的指定数目的随机数一 一对应的赋予定义的空数组,经选择语句分别执行直接插入排序,折半插入排序, 希尔排序，起泡

14、排序，快速排序，简单项选择择排序等6种排序对数组中的数值进行 排序。这次课程设计还有许多缺乏，如局部排序方法编程代码过于复杂，此外， 由于编程各种排序方法的区别较大，使用了不同的输出函数，增加了程序的复杂 性。此外，由于能力有限，还有无法实现的2种排序。但我也学到了很多东西， 如，掌握一些排序方法的实现，熟悉了编写代码的一般步骤：思考问题，写出解 决方案，写出伪代码，完成代码，调试程序。我从编写过程中，发现自己更多的 缺乏，如对C语言的掌握不够牢靠，对于C语言各种函数的调用也不够灵活等。希望在以后的编程过程中，能更加耐心和细心，不熟悉也不要慌张，不慌不 忙的进行程序编写和调试。14参考文献1数

15、据结构（C语言版）严蔚敏清华大学出版社20022数据结构-C语言描述王路群中国水利水电出版社2007数据结构实验教程（C语言版）王国钧清华大学出版社20094数据结构题集严蔚敏，吴伟民编 清华大学出版社2002C语言程序设计谭浩强清华大学出版社6C语言入门经典霍顿（美）清华大学出版社15题目排序算法实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要

16、求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语：日期：年 月日1课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 课程设计基本要求12分析与设计22.1题目需求分析22. 2存储结构设计31.1 3算法描述32.4 程序流程图72.5 程序测试说明73程序清单84.测试错误!未定义书签。1 .1测试数据134 . 2测试结果分析135总结14参考文献151课程设计目标与任务1.1课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学 是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计 基

17、本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作 方法学生通过数据结构课程设计各方面得到锻炼。1. 2课程设计任务设计排序相关函数库，以便在程序设计中调用，要求设计程序，产生20000 个随机数，完成下面功能：（1）对这些数分别进行直接插入排序、折半插入排序、希尔排序、起泡排 序、快速排序、简单项选择择排序，堆排序，2路-归并排序等排序，并把排序结果 进行保存。（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出假设干例程，演示通过调用自己所写程序来实现相关问题的要求。1 . 3课程设计基本要求严

18、格按照题意要求，独立进行设计，不能随意更改。假设确因条件所限，必须 要改变课题要求时，应在征得指导教师同意的前提下进行。学生应制定实习工作 计划，认真完成实习的各个环节，并在老师的指导下认真组织实习工作，撰写实 习报告，做好实习总结。2分析与设计2 . 1题目需求分析1,直接插入排序思路：设有一组关键字Kl,K2-.Kn）,排序开始便认为K1是一个有序的 序列，让K2插入到表长为1的有序序列，使之成为一个表长为2的有序序列， 让K3插入到表长为2的有序序列，使之成为表长为3的有序序列，依次类推， 最后Kn插入到上述表长为n-1的有序序列，得到一个表长为n的有序序列。3 .折半插入排序思路：在将

19、一个新元素插入已排好序的数组的过程中，寻找插入点时，将待 插入区域的首元素设置为allow,末元素设置为ahigh,那么轮比拟时将待插入 元素与am,其中m=（low+high）/2相比拟,如果比参考元素小，那么选择a low 到amT为新的插入区域（即high=m-l）,否那么选择am+l到ahigh为新的插 入区域（即low=m+l）,如此直至lowChigh不成立，即将此位置之后所有元素 后移一位，并将新元素插入ahigh+l。4 .希尔排序思路：先取一个小于n的整数dl作为第一个增量，把文件的全部记录分组。 所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序； 然后，

20、取第二个增量d2,d2dl,再将到d2作为增量继续分组，再进行直接插入 排序，依次向下取值，直到完成排序。5 .起泡排序思路：比拟相邻的元素。如果第一个比第二个大，就交换他们两个。对每一 对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的 元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续 每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比拟。6 .快速排序思路：快速排序的实现基于分治法，具体分为三个步骤。假设待排序的序列 为序列Lm. n被划分成两个可能为空的子序列Lm . pivot-1 和Lpivot+1 . n,使Lm. pivotT

21、的每个元素均小于或等于Lpivot, 同时Lpivot+1. n的每个元素均大于Lpivot。其中Lpivot称为这一趟分 割中的主元(也称为枢轴、支点)。通过递归调用快速排序，对子序列Lm . pivotT和Lpivot+1 . r排序。由于两个子序列是就地排序的，所以对它 们的合并不需要操作，整个序列Lm. n已排好序。7 .简单项选择择排序思路：序序列的记录个数为n o i取1, 2,n-1,从所有n-i+l个记录(R, Ri+1,Rn中找出排序码最小的记录，与第i个记录交换。执行n-1趟 后 就完成了记录序列的排序。2. 2存储结构设计此程序采用的是线性表的动态顺序存储结构：ftdef

22、ine LIST_INIT_SIZE 100线性表存储空间的初始分配量ftdefine LISTINCREMENT 10线性表存储空间的分配增量Typedef struct ElemType *elem;存储空间基址Int length;当前长度Int listsize;当前分配的存储容量(以sizeof (ElemType)为单位) SqList;上述定义中，数组指针elem指示存储空间基址，length表示线性表的当前长度, 对线性表的初始化操作就是为顺序表预定义大小的数组空间，并将线性表的当前 长度设为“0，listsize指示当前分配的存储空间大小，一旦元素插入而空间 缺乏，可进行再分

23、配。1. 3算法描述1 .直接插入排序设置R0为哨兵，将剩下的数值逐个进行插入，直至完成一趟排序： void InsertSort ( elem R , int n) 对记录序列RL.n作直接插入排序。for ( i=2; i=n; +i ) R0 = Ri;/复制为监视哨3for ( j=i-l; R0 Rj; j )Rj+1= Rj;/ 记录后移Rj+1=R0;/插入到正确位置) / InsertSort2 .折半插入排序因为是一个按关键字有序的序列，那么可以利用折半查找实现“在中查找Ri的插入位置: void BlnsertSort (elem R , int n) /对记录序列REI.

24、 n作折半插入排序。for ( i=2; i=n; +i ) |R0 = Ri;/ 将 Ri暂存到 R0low = 1; high = i-l;while ( low 二 high)在Rlow. . high中折半查找插入的位置m = (low+high) /2;/ 折半if (R0 =high+l; -j )Rj+1 = Rj; / 记录后移Rhigh+1= R0 : / 插入 / BlnsertSort3 .希尔排序先取一个正整数dKn,把所有相隔&的记录放一组，组内进行直接插入排序，然后取d2d”重复上述分组和排序操作；直至即所有记录放进一个 组中排序为止：void Shelllnser

25、t ( elem R , int dk ) /对待排序列R作一趟希尔插入排序 for ( i=dk+l; i=n; +i )if ( Ri Ri-dk) void ShellSort (elem R , int d , int t) 按增量序列d 0. t-l对顺序表L作希尔排序。 for ( k=0; k0 & R01)(for ( j = 1; j i; j+ )if (R j+1 R j )(Swap(R j , R j+1 )； /if / while / BubbleSort5 .快速排序选定一个中间数作为参考，所有元素与之比拟，小的调到其左边，大的调到 其右边：int Partit

26、ion (Elem R, int low, int high)(/交换记录子序列Rlow.high中的记录，使枢轴记录到位，并返回其所/在位置，此时，在它之前(后)的记录均不大(小)于它R0=Rlow;/用子表的第一个记录作枢轴记录pivotkey=Rlow ; /枢轴记录关键字while (lowhigh) /从表的两端交替地向中间扫描while(low=pivotkey)-high;Rlow=Rhigh : /将比枢轴记录小的记录移到低端while (lowhigh & Rlow=pivotkey)+low;Rhigh = Rlow : /将比枢轴记录大的记录移到高端)Rlow = R0

27、; /枢轴记录到位return low; /返回枢轴位置 / Partitionvoid QSort (Elem R, int low, int high)(/对记录序列Rlow. . high进行快速排序if (low high)/长度大于1pivotloc = Partition(L, low, high);/ 将 L. r low. . high 一分为二QSort (L, 1ow, pivotloc-1);/对低子表递归排序，pivotloc是枢轴位置QSort (L, pivotloc+1, high);/对高子表递归排序) / Qsort6 .简单项选择择排序在待排序的数据中选出最大(小)的元素放在其最终的位置：Void SelectSort (SqList &L)对顺序表做简单项选择择排序for (i=l; iL. length;+i) 选择第i小的记录，交换到位 j=SelectMinKey (L, i) ;/在 L. r iL. length中选择 key 最小记录 if(i!=j)L.riL.;与第i个记录交换)/ SelectSort