数据结构课程设计快速排序和归并排序

1、XX学院信息科学与工程系课程设计说明书课程名称：数据结构课程代码：题目:快速排序与归并排序年级/专业/班：学生姓名:奉XX学号:1440000000指导教师:易开题时间:2015年12 月 30日宀兀成时间：2016年1月10日目录摘 要 1一、 引 言 3、设计目的与任务 3311、课程设计目的 3.2、课程设计的任务 3.*、口、【> 4三、设计方案1、 需求分析 3.2、概要设计 4.3、详细设计 5.4、程序清单 1.3.四、调试分析与体会 19五、运行结果 20六、结 论 2424七、致 谢八、参考文献 25摘要数据结构课程设计， 列举了数据结构课程设计实例， 通过综合训练，

2、能够培养学生实际分析问题、 解决问题、编程和动手操作等多方面的能力，最终目的是帮助学生系统地掌握数据结构的基本内容， 并运用所学的数据结构知识去解决实际问题。其中内容包括数组、链接表、栈和队列、递归、树与森 林、图、堆与优先级队列、集合与搜索结构、排序、索引与散列结构等 关键字 ：数据结构；分析；掌握AbstractData structure course design, lists the datastructure course desig nas an example, throughthe comprehensive training,to cultivatestudents'

3、;practicalanalysis and solve problems inmany aspects, program ming, and han ds-on ability, the ultimate goal is to help stude nts to systematically master the basic content of data structure, and using the data structure ofknowledge to solve practical problems. Content includingarray, linked list, s

4、tack and queue,recurs ion, tree and forest, graph, heap and priorityqueue, the structure of the collect ionand search, sorting, in dex ing and hash ing structure, etcKeywords:data structure; Analysis ; master数据结构课程设计 快速排序与归并排序一、引 言二、将一组数据运用快速排序与归并排序进行排序，要求使用递归与非递归方法三、本次课程设运用到了 数组、链接表、栈、递归、排序等结构。四、在学

5、校机房进行程序设计，编写代码，实现程序的功能二、设计目的与任务1、课程设计目的1、能够更灵活地应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4. 数据结构课程设计是学习 C语言的一个重要过程，通过此次实践，学生对书本上的知识通过上机操作有了更形 象的理解，对今后的学习有很大的帮助。2、课程设计的任务问题描述 :做一个快速排序与归并排序三、设计方案1、 需求分析1) 对一组数据进行快速排序和递归排序2) 快速排序：快

6、速排序对气泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分， 其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对两部分记录继续进行排序，以达到整个序列 有序。3) 归并排序： 归并排序是又一类不同的排序方法。 “归并”的含义是将两个或两个以上的有序表组合成一个新的有序 表。无论是顺序存储结构还是链表存储结构，都可在 O(m+n)(m,m分别为有序表的长度)的时间量级上实现。利用归并的思想容易实现排序2、概要设计1) 抽象数据类型(ADT)如下：ADT SqLint数据对象：D=a|a i int, i=1,2,n,n 仝 0数据关系：R1=<ai-i,

7、 ai> | a i-i, ai D,i=2,n 基本操作：int InitSqlint(SqLint &L)/ 构造一个空的线性表 Lvoid Assignment(SqLint &L)/ 给表 L.element 赋值void Output(SqLint L)/ 输出表里的 L.ELenght 个元素Status InitStack(SqStack &S)/ 栈的初始化Status Push(SqStack &S,SElemType e)/ 入栈Status Pop(SqStack &S,SElemType &e)/ 出栈int Par

8、tition(SqLint &L,int low,int high)/ 交换顺序表 L.element 里的值，以枢轴为中心，小的在前，大的在后 int QuickSort(SqLint &L,int low,int high)/ 非递归快速排序算法int RQuickSort(SqLint &L,int low,int high)/ 递归快速排序算法void Merge(SqLint &L,int low,int mid,int high)/ 对子串进行合并排序int MergeSort(SqLint &L)/ 非递归归并排序算法int RMergeS

9、ort(SqLint &L,int low,int high)/ 递归归并排序算法2) 存储结构Typedef struct int *element; /存储空间基址int ELenght;/ 当前分配的存储容量个数 SqLint;3) 过程图快速排序初始1938659776132749一次划分之后27 38134976976549序列左继续排序13 27384976976549（结束）（结束）序列右继续排序(49657697（结束）4965（结束）有序序列1327384949657697归并排序3、详细设计本程序中的重要程序段如下，功能是分别实现快速排序与归并排序，并且分别用不同的

10、方法（递归与非递归），并且判断程序是否正确等 （简要介绍设计中的重要程序段）快速排序：通过一趟排序将待排序记录分割成独立的两个区间，其中左区间记录的关键字的值均比右 区间中记录的关键字的值小，再分别对这两个区间中的记录进行快速排序，以达到整个序列有序为止。1）重要程序段1/交换顺序表L.element里的值，以枢轴为中心，小的在前，大的在后int Partition(SqLint &L,int low,int high)int pivot=L.elementlow;/ 将第一个元素给 piovt 作为枢轴while(low!=high)/ 从表中的两端交替地向中间扫描while(low

11、<high&&L.elementhigh>=pivot) high-;/ 一路将后端的值进行 扫描，直到找到比枢轴小的值为止L.elementlow=L.elementhigh;/ 将比枢轴小的值移到低端while(low<high&&L.elementlow<=pivot) low+;/ 一路将后端的值进行 扫描，直到找到比枢轴大的值为止L.elementhigh=L.elementlow;/ 将比枢轴大的值移到高端L.elementlow=pivot;/ 枢轴记录到位return low;/ 返回枢轴位置2) 重要程序段 2 / 栈的

12、运用 typedef structSElemType *base; / 在栈构造之前和销毁之后， base 的值为 NULLSElemType *top;/ 栈顶指针int stacksize;/ 当前已分配的存储空间，以元素为单位SqStack;/ 栈的初始化Status InitStack(SqStack &S)/ 构造一个空栈 SS.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) return ERROR; / 分配存储空间失败 S.top=S.base;S.stacksize=STAC

13、K_INIT_SIZE;return OK;/InitStack/ 入栈Status Push(SqStack &S,SElemType e)/ 插入元素 e 为新的栈顶元素 if(S.top-S.base>=S.stacksize)/栈满，追加存储空间S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) return ERROR;/ 存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREME

14、NT;*S.top+=e;return OK;/Push/ 出栈Status Pop(SqStack &S,SElemType &e)/若栈不空，则删除 S的栈顶元素，用e返回其值，并返回 0K，否则返回ERRORif(S.base=S.top) return ERROR;e=*-S.top;return OK;/Top3) 重要程序段 3/ 非递归快速排序算法int QuickSort(SqLint &L,int low,int high)/ 采用快速排序的方法对 L.element 进行升序排序/ 利用栈，保存每一个待排序子串的首尾元素下标，下一次 while 循环

15、时取出这个范围，/ 对这段子序列进行 partition 操作SqStack S;/ 定义一个栈 Sint p,l,h;/p 记录枢轴的位置， l 记录子串首元素位置， h l 记录子串尾元素位置InitStack(S); /初始化栈if(low<high)p=Partition(L,low,high);if(p-1>low)Push(S,low);Push(S,p-1);if(p+1<high)Push(S,p+1);/ 进行第一次 Partition/ 取枢轴前子串的首尾位置入栈/ 取枢轴后子串的首尾位置入栈while(S.base!=S.top)/ 判断栈是否为空，Pu

16、sh(S,high);Pop(S,h); / 取一个待排序的子串首尾位置Pop(S,l);p=Partition(L,l,h); / 将待排序的子串进行 Partitionif(p-1>l) / 取枢轴前子串的首尾位置入栈Push(S,l);Push(S,p-1);if(p+1<h) / 取枢轴后子串的首尾位置入栈Push(S,p+1);Push(S,h);free(S.base); / 释放 S.bese 的空间return 1; / 排序成功返回 14) 重要程序段 4/ 递归快速排序算法int RQuickSort(SqLint &L,int low,int high

17、)/ 采用快速排序的方法对 L.element 进行升序排序/ 运用递归的方法，对串进行排序，int p; /p用来记录枢轴的位置if(low<high) / 判断长度是否大于 1p=Partition(L,low,high);/将串 L.elementlow.,high一分为二RQuickSort(L,low,p-1);/对底子表进行递归排序RQuickSort(L,p+1,high);/对底子表进行递归排序return 1;/ 排序成功返回 1归并排序： 先将前后相连的元素比较合并成有序的子序列， 然后再将前后的子序列进行比较合并成有 序的新的子序列，重复以上步骤，直到整个序列有序为

18、止1) 重要程序段 1/ 对子串进行合并排序void Merge(SqLint &L,int low,int mid,int high)/ 对子串 L.element 进行二分排序，以 mid 为分界点，将 L.element 分为底端和高端，然后底端和高 端进行比较排序，int i=low,j=mid+1,k;/i 记录底端最前位置， j 记录高端最前位置， k 用来记录 temp 元素个数int *temp;temp=(int *)malloc(L.ELenght*sizeof(int); / 给 temp 分配存储空间if(!temp) printf(" 分配空间失败

19、n"); return ; / 存储分配失败k=0; / 赋值第一个位置while(i<=mid&&jv=high) /将底端和高端进行相比，大的和放到temp,直到有一个没有元素为止if(L.elementi>L.elementj)tempk+=L.elementi+;else tempk+=L.elementj+;while(iv=mid) / 判断底端是否有值，有则赋值给 temptempk+=L.elementi+;while(jv=high)/ 判断高端是否有值，有则赋值给 temptempk+=L.elementj+;for(i=low,j=0

20、;i<=high;j+,i+) / 把 temp 里的值给 L.elementL.elementi=tempj;free(temp); / 释放 temp2) 重要程序段 2 / 非递归归并排序算法int MergeSort(SqLint &L)/ 采用归并排序的方法对 L.element 进行降序排序/ 将一个数组 对半分为两个子串，并且这两个子串是 有序的。/ 再将两个 有序的子串 合并 为 一个有序的数组。int i,j,low,mid,high;/i 记录每次子序列比较的步长， j 记录在 temp 中记录存放的个数 , low 记录/ 子串的 最前端位置， mid 记录

21、子串的中间位置， high 记录最后端位置for(i=1;i<L.ELenght;i*=2)/ 记录并控制每一步 步长记录并控制每一次步数for(low=0;low<L.ELenght-i;low=high) /mid=low+i;/ 中间位置high=mid+i;/ 最后端位置if(high>L.ELenght)/ 判断 high 是否比总元素个数大high=L.ELenght;Merge(L,low,mid-1,high-1);/ 把 结构体 L 子串最底端，中间端的前一个，最高端给Mergereturn 1; / 归并排序成功 返回 1 3) 重要程序段 3/ 递归归并

22、排序算法int RMergeSort(SqLint &L,int low,int high)/ 采用归并排序的方法对 L.element 进行降序排序/ 将一个数组 对半分为两个子串，并且这两个子串是 有序的/ 再将两个 有序的子串 合并 为 一个有序的数组。int mid; / 记录中间位置if(low<high) /判断 长度是否大于 1mid=(low+high)/2; / 将 L.elementlow ， high 分为 L.elementlow.mid 和 L.elementmid+1.highRMergeSort(L,low,mid); / 递归将 L.element

23、low.mid 归并为有序的 L.elementlow.midRMergeSort(L,mid+1,high);/ 递归将 L.elementmid+1.high 归并为有序的 L.elementmid+1.highMerge(L,low,mid,high); / 把 结构体 L 子串最底端，中间端的前一个，最高端给 Mergereturn 1;/ 归并排序成功 返回 1主函数与排序函数的调用void Sort()SqLint L; / 定义一个结构体 Lint *a,i; /a 记录输入数据 的原值 ,i 记录 a 的元素个数长度printf(" 请输入要排序的长度个数 n&quo

24、t;);scanf("%d",&L.ELenght); / 给 L.ELenght 赋值，给定要输入值的个数if(InitSqlint(L) / 判断是否开辟存储空间成功，开辟成功则执行以下步骤Assignment(L); / 给 L.element 依次赋值a=(int *)malloc(L.ELenght*sizeof(int); / 给 a 分配存储空间if(!a) printf("分配空间失败 n"); return ; / 存储分配失败for(i=0;i<L.ELenght;i+) / 将 L.element 里的值给 aai=L

25、.elementi;printf("nn 此时表里的数据顺序依次为： n");Output(L);printf("n 升序快速排序过程： (非递归) ");if(QuickSort(L,0,L.ELenght-1)/ 判断是否进行非递归快速排序成功，成功则输出表中的有序序列printf("n 经过非递归快速排序之后，表中的顺序为： n");Output(L);else printf(" 排序失败 n");for(i=0;i<L.ELenght;i+) / 将 a 里的值给 L.elementL.element

26、i=ai;printf("nn 此时表里的数据顺序依次为： n");Output(L);printf("n 升序快速排序过程： (递归) ");if(RQuickSort(L,0,L.ELenght-1)/ 判断是否进行递归快速排序成功，成功则输出表中的有序序列printf("n 经过递归快速排序之后，表中的顺序为： n");Output(L);else printf(" 排序失败 n");for(i=0;i<L.ELenght;i+) / 将 a 里的值给 L.elementL.elementi=ai;pr

27、intf("nn 此时表里的数据顺序依次为： n");Output(L);printf("n 降序归并排序过程： (非递归) ");if(MergeSort(L)/ 判断是否进行非递归归并排序成功，成功则输出表中的有序序列printf("n 经过非递归归并排序之后，表中的顺序为： n");Output(L);else printf("排序失败 n");for(i=0;i<L.ELenght;i+) / 将 a 里的值给 L.elementL.elementi=ai;printf("nn 此时表里的数

28、据顺序依次为： n");Output(L);printf("n 降序归并排序过程： (递归) ");if(RMergeSort(L,0,L.ELenght-1)/ 判断是否进行递归归并排序成功，成功则输出表中的有序序列 printf("n 经过递归归并排序之后，表中的顺序为： n"); Output(L);else printf("排序失败 n");/ 主函数int main()Sort(); return 0;4、程序清单#include<stdio.h>#include<stdlib.h>#def

29、ine ERROR 0#define TRUE 1#define OK 1#define STACK_INIT_SIZE 100 / 栈的存储空间初始分配量#define STACKINCREMENT 10 / 栈的空间分配增量typedef int SElemType;typedef int Status;/ 定义结构体进行存储数据typedef struct int *element; / 存储空间基址int ELenght; / 当前分配的存储容量个数SqLint;/ 构造一个空的线性表 Lint InitSqlint(SqLint &L)L.element=(int *)mal

30、loc(L.ELenght*sizeof(int); / 分配存储空间 if(!L.element) return 0;/ 检查分配是否成功，分配失败返回0return 1;/ 分配成功则返回 1 /InitSqlint/ 给表 L.element 赋值void Assignment(SqLint &L)int i;printf(”请输入d个整形数据作为元素n",L.ELenght);for(i=0;i<L.ELenght;i+)/ 给表 L.element 从键盘上输入进行逐个赋值scanf("%d",&L.elementi);/ 输出表里

31、的 L.ELenght 个元素void Output(SqLint L)int i;for(i=0;i<L.ELenght;i+)/ 将表 L. element 从第一个开始输出 L.Elenght 个到显示器printf("%d ",L.elementi); typedef structSElemType *base; / 在栈构造之前和销毁之后， base 的值为 NULLSElemType *top;/ 栈顶指针int stacksize;/ 当前已分配的存储空间，以元素为单位SqStack;/ 栈的初始化Status InitStack(SqStack &am

32、p;S)/ 构造一个空栈 SS.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) return ERROR;/ 分配存储空间失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack / 入栈Status Push(SqStack &S,SElemType e)/ 插入元素 e 为新的栈顶元素 if(S.top-S.base>=S.stacksize)/栈满，追加存储空间S.base=(SElemType *)reallo

33、c(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) return ERROR;/ 存储分配失败S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;*S.top+=e; return OK;/Push / 出栈Status Pop(SqStack &S,SElemType &e)/若栈不空，则删除S的栈顶元素，用e 返回其值，并返回 0K,否则返回ERROR if(S.base=S.top) return ERROR;e=*-S.top;r

34、eturn OK;/Top/ 交换顺序表 L.element 里的值，以枢轴为中心，小的在前，大的在后 int Partition(SqLint &L,int low,int high)/ 交换顺序表 L.element 里的值，以第一个( low 的位置 ) 做为枢轴值，首先往前取值与枢轴比较，/ 如大于枢轴则取它前一个继续与枢轴比较，如果还是大于枢轴，再往前取，直到取到比枢轴小，/ 当值比枢轴小时，把它放到 low 的位置，然后取 low 位置的值与枢轴比较，小于枢轴时，取下一个 / 继续比较，大于枢轴时，比它放到 high 的位置，然后再取 high 位置的值，进时比较，大于枢轴

35、时 / 取它的前一个继续比较，以些类堆，直到 low 等于 gigh 为止，/ 将第一个元素给 piovt 作为枢轴int pivot=L.elementlow; while(low!=high) while(low<high&&L.elementhigh>=pivot) high-;L.elementlow=L.elementhigh; while(low<high&&L.elementlow<=pivot) low+;L.elementhigh=L.elementlow;L.elementlow=pivot; / 枢轴记录到们 pri

36、ntf("n");Output(L);return low;/ 返回枢轴位置 / 非递归快速排序算法int QuickSort(SqLint &L,int low,int high)/ 采用快速排序的方法对 L.element 进行升序排序/ 利用栈，保存每一个待排序子串的首尾元素下标，下一次/ 从表中的两端交替地向中间扫描/ 一路将后端的值进行 扫描，直到/ 找到比枢轴小的值为止/ 将比枢轴小的值移到低端/ 一路将后端的值进行 扫描，直到/ 找到比枢轴大的值为止/ 将比枢轴大的值移到高端while 循环时取出这个范围，/ 对这段子序列进行 partition 操作

37、SqStack S;/ 定义一个栈 Sint p,l,h;/p 记录枢轴的位置， l 记录子串首元素位置， h l 记录子串尾元素位置InitStack(S); /初始化栈if(low<high)p=Partition(L,low,high);/ 进行第一次 Partitionif(p-1>low)/ 取枢轴前子串的首尾位置入栈Push(S,low);Push(S,p-1);if(p+1<high) / 取枢轴后子串的首尾位置入栈Push(S,p+1);Push(S,high);while(S.base!=S.top) / 判断栈是否为空，Pop(S,h); / 取一个待排序

38、的子串首尾位置Pop(S,l);p=Partition(L,l,h); / 将待排序的子串进行 Partition if(p-1>l) / 取枢轴前子串的首尾位置入栈 Push(S,l);Push(S,p-1);if(p+1<h) / 取枢轴后子串的首尾位置入栈Push(S,p+1);Push(S,h);free(S.base); /释放 S.bese 的空间return 1; / 排序成功返回 1 return 1;/ 递归快速排序算法int RQuickSort(SqLint &L,int low,int high)/ 采用快速排序的方法对L.element 进行升序排

39、序if(low<high) / 判断 p=Partition(L,low,high);长度是否大于 1/ 将串 L.elementlow.,high一分为二RQuickSort(L,low,p-1);/ 对底子表进行递归排序RQuickSort(L,p+1,high);/ 对底子表进行递归排序/ 运用递归的方法，对串进行排序， int p; /p用来记录枢轴的位置/ 排序成功返回 1/ 对子串进行合并排序 void Merge(SqLint &L,int low,int mid,int high)/ 对子串 L.element 进行二分排序，以 mid 为分界点，将 L.elem

40、ent 分为底端和高端，然后/ 底端和高端进行比较排序，int i=low,j=mid+1,k;/i 记录底端最前位置， j 记录高端最前位置， k 用来记录 temp 元素个数 int *temp;temp=(int *)malloc(L.ELenght*sizeof(int); / 给 temp 分配存储空间 if(!temp) printf(" 分配空间失败 n"); return ; / 存储分配失败 k=0; / 赋值第一个位置while(i<=mid&&jv=high)/将底端和高端进行相比，大的和放到temp,直到有一个没有元素为止if(

41、L.elementi>L.elementj)tempk+=L.elementi+;else tempk+=L.elementj+;while(iv=mid) / 判断底端是否有值，有则赋值给 temptempk+=L.elementi+;while(jv=high)/ 判断高端是否有值，有则赋值给 temptempk+=L.elementj+;for(i=low,j=0;iv=high;j+,i+)/ 把 temp 里的值给 L.elementL.elementi=tempj;free(temp); / 释放 tempprintf("n");Output(L);/ 非

42、递归归并排序算法int MergeSort(SqLint &L)/ 采用归并排序的方法对 L.element 进行降序排序/ 将一个数组 对半分为两个子串，并且这两个子串是 有序的。/ 再将两个 有序的子串 合并 为 一个有序的数组。int i,j,low,mid,high;/i 记录每次子序列比较的步长， j 记录在 temp 中记录存放的个数 , low 记录/ 子串的 最前端位置， mid 记录子串的中间位置， high 记录最后端位置for(i=1;ivL.ELenght;i*=2)/ 记录并控制每一步 步长for(low=0;lowvL.ELenght-i;low=high)

43、 /记录并控制每一次步数mid=low+i;/中间位置high=mid+i;/最后端位置if(high>L.ELenght)/判断 high 是否比总元素个数大high=L.ELenght;Merge(L,low,mid-1,high-1);/ 把 结构体 L 子串最底端，中间端的前一个，最高端给 Mergereturn 1; / 归并排序成功 返回 1/ 递归归并排序算法int RMergeSort(SqLint &L,int low,int high)/ 采用归并排序的方法对 L.element 进行降序排序/ 将一个数组 对半分为两个子串，并且这两个子串是 有序的。/ 再将

44、两个 有序的子串 合并 为 一个有序的数组。int mid; / 记录中间位置if(low<high) / 判断 长度是否大于 1mid=(low+high)/2; / 将 L.elementlow ， high 分为 L.elementlow.mid 和 L.elementmid+1.high RMergeSort(L,low,mid); / 递归将 L.elementlow.mid归并为有序的 L.elementlow.midRMergeSort(L,mid+1,high);/ 递归将 L.elementmid+1.high归并为有序的 L.elementmid+1.highMerg

45、e(L,low,mid,high); / 把 结构体 L 子串最底端，中间端的前一个，最高端给 Merge return 1;/ 归并排序成功 返回 1void Sort()SqLint L; / 定义一个结构体 Lint *a,i; /a 记录输入数据 的原值 ,i 记录 a 的元素个数长度printf(" 请输入要排序的长度个数 n"); scanf("%d",&L.ELenght); / 给 L.ELenght 赋值，给定要输入值的个数 if(InitSqlint(L) /判断是否开辟存储空间成功，开辟成功则执行以下步骤Assignment

46、(L); / 给 L.element 依次赋值a=(int *)malloc(L.ELenght*sizeof(int);/ 给 a 分配存储空间if(!a) printf("分配空间失败 n"); return ; / 存储分配失败for(i=0;i<L.ELenght;i+) / 将 L.element 里的值给 aai=L.elementi;printf("nn 此时表里的数据顺序依次为： n");Output(L);printf("n 升序快速排序过程： (非递归) "); if(QuickSort(L,0,L.ELen

47、ght-1)/ 判断是否进行非递归快速排序成功，成功则输出表中的有序序列 printf("n 经过非递归快速排序之后，表中的顺序为： n");Output(L);else printf(" 排序失败 n");for(i=0;i<L.ELenght;i+) / 将 a 里的值给 L.elementL.elementi=ai;printf("nn 此时表里的数据顺序依次为： n");Output(L);printf("n 升序快速排序过程： (递归) ");if(RQuickSort(L,0,L.ELenght-

48、1)/ 判断是否进行递归快速排序成功，成功则输出表中的有序序列 printf("n 经过递归快速排序之后，表中的顺序为： n");Output(L);else printf(" 排序失败 n");for(i=0;i<L.ELenght;i+)/ 将 a 里的值给 L.elementL.elementi=ai;printf("nn此时表里的数据顺序依次为：n");Output(L);printf("n 降序归并排序过程：(非递归)");if(MergeSort(L)/判断是否进行非递归归并排序成功，成功则输岀表

49、中的有序序列 printf("n经过非递归归并排序之后，表中的顺序为：n");Output(L);else printf("排序失败 n");for(i=0;i<L.ELenght;i+)/ 将 a 里的值给 L.elementL.elementi=ai;printf("nn此时表里的数据顺序依次为：n");Output(L);printf("n 降序归并排序过程：(递归)”)；if(RMergeSort(L,0,L.ELenght-1)/判断是否进行递归归并排序成功，成功则输岀表中的有序序列 printf("

50、;n经过递归归并排序之后，表中的顺序为：n");Output(L);else printf("排序失败 n");/主函数int main()Sort();return 0;四、调试分析与体会经过调试，刚开始出现输不出值，然后是有些数据排序不成功，但是经过反修改就好成功了，经过这 次课程设计，掌握了快速排序和归并排序的思路级实现方法1、问题一：非递归快速排序输不出值#匕时表里的数据顺序依次为；49 38 65 97 7S 13 2?升序快速排序过程：(非递归)27 38 13 49 7& 97 65现象：输岀框只输岀一次排序步骤的值，然后光标在那里不停闪动原

51、因：在取出栈里的值时，高低位没有分清楚，把高位给低 位，低位给了高位2、问题二：非递归归并排序得不岀正确结果现象：输岀框输岀的排序值无序原因：出现排序错误.在传送值时，中间端在传送时没五、运行结果测试数据 49 38 65 97 76 13 27运行结果如图1所示。匕时表里的数据顺序依次为t9 38 &5 97 76 13 27降序归并排序过程| （非递归）9 38 65 97 76 13 2731fi777G7 49 38 &5 7& 13 27迪非递归归井排序之后,7 49 3B 6S 76 13 27表中的顺序为1有减1，岀现合并排序值不正确图1经过排序，快速排序

52、以枢轴为中心，进行分类，大的在后，小的在前，递归与非递归调用的方式是不一致的。归 并排序以两两重点，进行两两排序使之变成一个有序的子表，递归与非递归调用的方式是不一致的。测试数据 0 -1 -654 0 1 -1 2 9854运行结果如图2所示。“ C ：Ustr5Administ ratorDocu mentsC - F reeT 倉 mp 侏需左 l.«xe*请输入$个整形数据作为元素e -1-6S401-12 9BE49B54（非递归）9昭此时表里的数据顺序依次为:0 -1 -654 01-12 Hl. -1 一65吗 0 0屏序快速排序过程：1 2-1 -1 -654 0012 9854-fi54 -1 1 0 0 1 2 9854-654 -1 -1 0 G 1 2 9854经过非递归快速排序之后，表中的顺序为'-654 -1 -1 0 0 1 2 9854时表里的数据顺序依次为;-1 f54 01-12 丹5百序快速排序过程：（递归）-1 一65増 n 0 1 2 985198S498