设计排序典型算法(冒泡与快速排序).doc

河北理工大学 软件设计基础（C+）课程设计报告设计名称： 设计排序典型算法（冒泡与快速排序） 姓 名： 学 号： 专业班级： 学 院： 设计时间： 设计地点： 计算机控制中心 成绩：指导教师评语： 指导教师签字： 年 月 日软件设计基础（C+）课程设计报告 第 15 页，共 15 页目 录1.课程设计目的32.课程设计任务与要求33.课程设计说明书44.课程设计成果65.程序调试过程136.设计问题的不足和改进方案137.课程设计心得148.冒泡法和快速排序法对比149.参考文献14 1课程设计目的 软件设计基础（C+）课程设计是这门课程的实践性教学环节之一，本次设计结合实际应用的要求，使课程设计既覆盖C+的知识点，又接近工程实际需要。目的是通过课程设计的综合训练，培养学生实际分析问题、解决问题的能力，以及编程和动手能力，最终目标是通过课程设计这种形式，帮助学生系统掌握C+这门课程的主要内容，养成良好的编程习惯，更好的完成教学任务。 2课程设计任务与要求： 要求： 本次课程设计利用软件设计基础（C+）课程中所学到的编程知识和编程技巧，完成具有一定难度和工作量的程序设计题目，帮助学生掌握编程、调试的基本技能，独立完成所布置的任务。 要求： 1、对系统进行功能需求分析2、设计合理的数据结构和系统框架3、编程简练，程序功能齐全，能正确运行4、说明书、流程图要清楚5、课题完成后必须按要求提交课程设计报告 任务： （1）数列的赋值要求用函数实现（2）使用“冒泡法”进行排序，用函数实现并统计排序次数。（3）使用“quicksort法”进行排序，用函数实现并统计排序次数（4）比较以上两种排序方法的优劣。 3课程设计说明书概要设计 模块说明: 在我设计的程序中一共包含了五个模块，分别为输入模块，升序模块，降序模块，提示模块， 输出模块。在这五个模块中输入模块，升序模块，降序模块，提示模块，输出模块是相对独立的块。通过Main 函数将这五个模块联系起来。而while控制循环语句则实现了五个模块的多次使用。 模块结构图： Main 函数退出程序While控制循环语句降序模块函数升序模块提示模块输出模块输入模块quickdown函数quickup和upquickup函数up函数down函数quickdown和down 详细设计 总体流程图： Main 函数 退出程序X=100While控制循环语句（x!=100） 再输入xt=0quickup函数 t=1output函数 升序input函数 t=2m=1up函数 quickup和up print函数 t=0quickdown函数 t=1m=0 降序 t=2quickdown和downdown函数 各功能模块流程图： input函数提示模块print函数输入模块 t=0up函数t=1quickup和up升序模块 quickup函数 t=2 quickdown函数t=0t=1降序模块down函数quickdown和down t=2 output函数输出模块 4课程设计成果 程序源代码： #include void input(int*p,int N); /输入函数说明void quickdown(int *a,int left,int right,int k); /快速排序法的降序排列函数说明void quickup(int *a,int left,int right,int k); /快速排序法的升序排列函数说明void up(int*q,int N); /冒泡法升序函数说明void down(int*q,int N); /冒泡法降序函数说明 void output(int*p,int N); /输出函数说明void print();/选择的种类函数说明函数说明void main() int *a,n,m,*b,t,x=1;cout *排序小机器*endl; coutendl; while(x!=100) /循环coutn; a=new int n; /申请动态内存 b=new int n; /申请动态内存 cout请输入n个整数，其分别为：endl; input(a,n); for(int i=0;in;i+) bi=ai; /让a和b数组一样，a数组赋值给b print(); coutt; coutm; if(m=1) /升序的方式 if(t=2) /调用两个函数 quickup(a,0,n-1,0); cout将所有的趟数对应的次数相加即为最终的次数endl; / 快速排序法up(b,n); / 冒泡法 else if(t=0) quickup(a,0,n-1,0); cout将所有的趟数对应的次数相加即为最终的次数endl; /快速排序法 else up(a,n); / 冒泡法 else /降序的方式 if(t=2) quickdown(a,0,n-1,0); cout将所有的趟数对应的次数相加即为最终的次数endl; / 快速排序法 down(b,n); / 冒泡法 else if(t=0) quickdown(a,0,n-1,0); cout将所有的趟数对应的次数相加即为最终的次数endl; / 快速排序法 else down(a,n); / 冒泡法 cout经过排序后的顺序为endl; output(a,n); /调用输出函数cout是否要继续：不继续请输入100x; delete a,b; /删除多余内存void input(int*p,int N) /调用输入函数，为数组元素赋值for(int i=0;ipi;void up (int*q,int N) /冒泡法升序排列函数int t,k=0; for(int i=0;iN-1;i+) /走的趟数 for(int j=0;j*(q+j+1) t=*(q+j); *(q+j)=*(q+j+1);/前边的比后边的大就交换 *(q+1+j)=t; k+;/统计排列的次数 cout冒泡法共用了k次endl;void down (int*q,int N) /冒泡法降序排列函数int t,k=0; for(int i=0;iN-1;i+) /走的趟数 for(int j=0;jN-1-i;j+) /对应某趟数对应的数进行排序 if(*(q+j)*(q+j+1) t=*(q+j); *(q+j)=*(q+j+1);/前边的比后边的小就交换 *(q+1+j)=t; k+;/统计次数 cout冒泡法共用了k次endl;void quickup(int *a,int left,int right,int k)/快速排序法升序函数 int f,l,r,t;l=left;r=right;f=a(left+right)/2; /定义关键的数while(lr)while(alf) -r; /当数组a右边中的数满足比关键数小或等就跳出if(l=r)t=al; /跳出是对应的l，r所对应的数交换al=ar;ar=t;+l; /交换完后就l增一，r减一。 -r;k+;if(l=r) l+;if(leftr) quickup(a,left,r+1,0); /分成关键数的前部分，递归if(lright) quickup(a,l-1,right,0);cout这一趟用了k次endl; / 分成关键数的前部分，递归 void output(int*p,int N) /输出函数 for(int i=0;iN;i+) coutpit;coutendl; void print()/提示信息 cout -*-*-*- endl;cout | | | endl;cout | | | endl;cout 排序方法 | 快速排序 | 冒泡法 | 两者均有endl;cout t | 0 | 1 | 2 endl; cout | | | endl;cout - endl; cout | | | endl; cout | | | endl;cout 排序方式 | 降序 | 升序 | 谢谢 endl;cout m | 0 | 1 | ok endl;cout | | | endl;cout -*-*-*- endl; void quickdown(int *a,int left,int right,int k) /快速排序降序函数 int f,l,r,t;l=left;r=right;f=a(left+right)/2; /找关键数中间的while(lf) +l; / 当数组a左边中的数满足比关键数小或等就跳出while(arf) -r; /当数组a左边中的数满足比关键数大或等就跳出if(l=r)t=al;/交换al=ar;ar=t;+l; -r;k+;if(l=r) l+;if(leftr) quickdown(a,left, r+1,0); /递归if(lright) quickdown(a, l-1,right,0); cout这一趟用了k次endl; / 递归 运行结果： 5.程序调试过程 程序调试步骤：1.编译，检查是否有语法错误，如果有，则点击错处，就会在程序中指出，根据提示进行修改。没有的话进行链接，如此时出现错误很有可能是算法的错误，如若没有，则运行程序。2根据提示输入所要排序的字符串的长度。3申请动态的空间4.根据提示分别输入要排序的数字。5.然后选择要排序的方式：升序或降序。在选择要排序的方法。冒泡法选择法或两者都有，选择不同则调用不同的函数。6.接着输入是否还要排别的一组数。如果不排就输入100跳出循环。7.删除多余的空间。 遇到的问题：1.快速排序发的基本思想不清楚。总是排的不对。快速排序法很不为稳定所以每次和每次的结果都不相同。第一次编的不是快速排序法。而是选择排序法。2.在主函数中要有if和else。因为if else很多所以导致if和else不配套。3.在程序中因为我要用两种方法排序。当时只定义一个数组。所以在用下一个方法排序是。所用的次数为零。因为在使用前一种方法后已经排完了。4.在if和else if后描述条件时把等好和弄混了。5.用快速排序法排序是无法输出排序的次数。总是循环输出。6.在快速排序法中不知道如何处理让左右两边都进行和关键数进行比较。满足就一定条件就交换。曾经只用单循环和if，else做，则显示算法有错。7.在快速排序法中想输出排序的次数曾想用指针传递。在快速排序法函数中让形参变化。只要在主函数中输出实参就行。形参实参共用一块内存。形参便也相应的变化。但行不通。8.想要如果调用两个函数同时排序的话。则比较两种方法的优劣。然后提示客户选择较少次数的一种方法排序。但是次数传输不出不来。6.设计问题的不足和改进方案 设计问题的不足：(1)没有一次性输出快速排序法的次数。(2)没有建议用户在当两种方法都使用后哪种方法更变洁。(3)程序中提示信息循环出现有点繁琐。 改进方案(1)还没有找到办法。(2)也还没找到办法。 (3)将提示函数放在循环之外。7.设计心得(1) 培养我们综合利用C+语言进行程序设计的能力，掌握排序算法，使我们能够解决信息管理系统中的一些问题。(2)提高我们建立程序文档、归纳总结的能力。(3)提高我们自学能力。更好的利用图书馆资料解答问题。(4)帮助我们用对比的方法解答问题。(5)写实验报告告诉我做完事后不代表就没有事了，还要养成时候要反思。要吾日三省吾身。要总结积累经验。找到好的方面和不好的方面。对好的方面要发扬不好的要积极改正。(6)还知道要积极的去对待自己的任务。遇到困难不再是等待别人来找自己。给自己