2022年多种排序算法 .pdf

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

1、用 C+实现多种排序算法学生姓名：指导老师：摘要本课程设计是基于屏幕的简单应用程序。整数数列的排序源远流长，如何高效地排序一直困扰着我们，本程序就很好地解决了这个问题。把待排序数列存入数组中， 通过对数组的操作实现排序。在课程设计中， 系统开发平台为 Windows 2000，程序设计设计语言采用Visual C+6.0，程序运行平台为Windows 98/2000/XP/Vista。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以解决数学中的一些常见问题。关键词Visual C+；程序设计；排序函数；数组；1 引言1.1 课程背 景排序问题源远流长，一直是数学地重要组成部分。

2、随着各种信息的快速更新， 排序问题也走进了其他领域以及我们地日常生活。如何高效地排序一直困扰着我们1.2： 课程设计目的排序是数学的重要组成部分， 工作量大是其存在的问题。如何高效地排序？本程序就是解决这个问题而设计。程序中，把数列储存在数组中， 采用插入排序等十种排序方法对数组元素进行排序，高效地解决了排序问题。本软件开发的平台为最新的微软公司出版的市面最新系统Windows 2000，而且可以作为自身的运行平台非常广泛，包括Windows 98/2000/XP/Vista 等等。1.3课程设计内容本程序把对数列的排序转化为对数组元素的排序，用户可以根据自己的实际问题选择系统提供的十种排序方

3、法的任意一种进行排序。程序通过自身的判断以及处理实现排序。最后用户选择排序方式 （从小到大或从大到小），程序最后输出结果。如下图：输入数据存入数组选 择 排序方法排序选 择 排序方式输出结果名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 22 页 - - - - - - - - - 2 需求分析3: 系统总框图：4：模块的详细设计分析1 功能模块划分：（1） ：获取数列，存入数组，选择排序方法（即主函数）；（2） ：调用排序函数，对数组元素进行排序；（3） ：调用打印函数

4、，输出排序结果；再输入数列以及输出提示开始先 输 入 数列个数插入排序SHELL 排序二分法插入排序优化冒泡排序直接选择优化的快速排序基数排序两路归并排序输入排序方法桶式排序优化插入排序输出提示以及用户选择排序方式输出结果结束名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 22 页 - - - - - - - - - 2.模块的详细设计分析：（ 1） ：获取数列，存入数组和选择排序方法的模块设计分析：（控制流图）开始系 统 输出提示用户输入数据个数用 户 输 入数列输出提

5、示和用户选择排序方法程序进入下一个模块名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 22 页 - - - - - - - - - （数据流图）注：（2） ：调用排序函数和对数组元素进行排序的模块设计分析：输入待排序数据个数，存入变量 n 中输入数列系统输出提示信息用户输入排序方法对应的数字，其存入变量 sign 中把数列存入数组array20 程序进入下一个模块名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

6、- 名师精心整理 - - - - - - - 第 4 页，共 22 页 - - - - - - - - - （控制流图）判 断 所 选择 的 排 序方法上一个模块插入排 序函数进行排序优化插 入排序函数 进行排序二分法 插入排序函 数进行排序优化冒 泡函数进行排序直接选 择函数进行排序SHELL 排序函数进 行排序优化的 快速排序函 数进行排序两路归 并排序函数 进行排序桶式排 序函数进行排序基 数 排序 函数进行排序十种排序函数中选一种十种排序函数中选一种排 序完 成，返 回主 函数程 序进 入下一个模块名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

7、 - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 22 页 - - - - - - - - - （数据流图）下面重点分析排序函数: A：插入排序的流程图如下：注： 该排序是把待排序数插入已排好的数列中，从第一个元素开始到第n-1 个元素（数组以第 0 元素开始计）B： 优化插入排序的流程图如下：上一个模块判断 sign的值实 参 是数组array20和 部 分变量如变量 n 程序流向对应的排序函 数对数组元 素进行排序排 序 完成 ， 程序 流 向下 一 个模块取 出 数组 第i个元素（i0）与第 i-1 个元素比较判断大小调用交换函数，把两个值对调， i自减

8、，直到i=0 i 自增， 直到in,(n元 素 个数) 前者小前者大名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 22 页 - - - - - - - - - ：注 ：该排序是把待排序数插入已排好的数列中，从第一个元素开始到第n-1 个元素（数组以第 0 元素开始计） ，对第一种进行适当的修改，提高了运行效率。C：以下配合原代码对二分法插入排序进行说明：void BinaryInsertSorter(int Array,int n) /形参接受数组，n 代表元素个数 i

9、nt temp; int left,right,middle; /分别表示左右中的数for(int i=1;in;i+) /从第一元素开始插入 temp=Arrayi; /待插入数赋给temp left=0;right=i-1; while(left=right) middle=(left+right)/2; if(temp=left;j-) /实现插入并移动部分元素Arrayj+1=Arrayj; Arrayleft=temp; 注 ：通过二分法大大缩小查找范围，该方法适合对大量数据的排序。D： 下面配合源代码对优化冒泡排序进行说明：void ImprovedBubbleSorter(int

10、 Array,int n) /形参接受数组，n 代表元素个数 bool NoSwap; /表示需不需交换for(int i=1;i=i;j-) if(Arrayj,Arrayj-1) swap(Array,j,j-1); NoSwap=false; if(NoSwap) return; E： 下面配合源代码对直接选择排序：void StraighSelectSorter(int Array,int n) /形参接受数组，n 代表元素个数for(int i=0;in-1;i+) /从第 0 个元素开始选择，依次选择较小数 int Smallest=i; for(int j=i+1;jn;j+)

11、/在未排序元素中循环，Smallest 计下最小元素的下标 if(ArrayjArraySmallest) Smallest=j; swap(Array,i,Smallest); / 交换两元素的值 F：下面结合源代码对Shell 排序进行说明：void ModifiedInsertSort(int Array,int n,int delta) for(int i=delta;i=delta;j-=delta) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 22 页 -

12、 - - - - - - - - if(Arrayj0;delta/=2) for(int j=0;jdelta;j+) ModifiedInsertSort(&Arrayj,n-j,delta); /调用，实现排序 J：下面结合源代码对桶式排序进行说明：void BuckerSorter(int Array,int n,int max) /接受数组，以及最大数max int *TempArray=new intn; /建立动态指针int * count=new intmax; /建立动态指针int i; for(i=0;in;i+) TempArrayi=Arrayi; / 把数组 Arra

13、y 赋给诉诸 TempArray for(i=0;imax;i+) counti=0; for(i=0;in;i+) countArrayi+; / countArrayi 表示数值Arrayi 出现的次数for(i=1;i=0;i-) Array-countTempArrayi=TempArrayi; /“对号入座” ，实现排序，（3） ：调用打印函数和输出排序结果的模块设计：上一个模块主 函 数调 用 打印函数用 户 输入 何 种排 序 方式判 断 排序方式按 照 从小 大 输出按 照 从大 到 小输出结束名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

14、 - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 22 页 - - - - - - - - - （控制流图）（数据流图）5:源代码中使用的函数及其说明void swap(int Array,int i,int j): 交换数组 Array 第 i 和 j 个元素的值，程序中需调用多次；void InsertSort(int Array,int n) ：插入排序函数，把待排序元素插入已排序的数列中，最终实现排序；void ImprovedInertSorter(int Array,int n) ：优化插入排序函数，；上一个模块输出提示信息用户输入排序方式对应

15、的数字程 序 把 该 数 字 存入变量 j 中判断 j的值j=1 按 元 素 次序 从 小 到大 把 数 组array 输出按 元 素 次序 从 大 到小 把 数 组array 输出结束j=2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 22 页 - - - - - - - - - void BinaryInsertSorter(int Array,int n)：二分法插入排序函数；void ImprovedBubbleSorter(int Array,int n)

16、：优化冒泡排序函数；void StraighSelectSorter(int Array,int n) ：直接选择排序函数；void ModifiedInsertSort(int Array,int n,int delta)：SHELL 排序函数；int SelectPivot(int left,int right) ：在优化的快速排序函数调用此函数，求中值；int Partition(int Array,int left,int right) ：在优化的快速排序函数调用此函数；void ImprovedQuickSorter(int Array,int left,int right)：优化的

17、快速排序函数；void Merge(int Array,int TempArray,int left,int right,int middle) ：两路归并排序函数；void BuckerSorter(int Array,int n,int max)：桶式排序函数；void RadixSorter(int Array,int n,int d,int r)： 基数排序函数；void printArray(int Array,int n) ：打印函数，即输出结果；注：以上均为外部函数。6：源代码中的算法举例以优化插入排序为例：源代码如下： /优化插入排序void ImprovedInertSort

18、er(int Array,int n) int Temp; for(int i=1;i=0)&(TempArrayj) Arrayj+1=Arrayj; j=j-1; Arrayj+1=Temp; 该排序是把待排序数插入已排好的数列中，从第一个元素开始到第n-1 个元素（数组以第0元素开始计）其流程图如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 22 页 - - - - - - - - - 7、存在的问题与不足及对策（1） ：系统仅提供整数排序， 当数列中有浮点

19、型等数据类型时，系统不能保证排序结果正确，对策：排序数列仅输入整数；（2） ：程序无异常处理机制。对策：用户使用时严格按照系统提示，可保证运行结果正确；8 、操作手册下面结合每一次输入后的界面情况进行说明。（1） ：系统输出提示信息， 用户输入待排序数列的长度，即数据个数； 如下图（系统初始界面）Temp 与第 j个 元 素 比较，j 的初始值是 i-1 取出数组第 i 个元素，赋给变量Temp 判 断 大小当 j 不小于 0 时 j自减，并且把第j个 元 素 的 值 赋 给第 j+1 个元素前者小前者大把 Temp 赋给第j+1 个元素，并且i 自加直到 i=n-1（n 为元素个数）名师资料

20、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 22 页 - - - - - - - - - （以 6 为数列长度为例）（2） ：系统输出提示信息，用户输入数列，长度一定不能错；如下图（以该数列为例）（3） ：系统输出提示信息， 用户根据实际情况选择适当的排序方法；如下图（以插入排序为例）（4） ：系统输出提示信息，用户选择排序方式，输出结果，程序结束；如下图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精

21、心整理 - - - - - - - 第 13 页，共 22 页 - - - - - - - - - （以从大到小为例）9 结束语这次的课程设计的内容是C+ 和 VC+ 语言实现多项式的相加减可视化界面，这对我来说是个很具有挑战性的任务，虽然只做了一个很简单的系统只支持一元多项式的运算， 但通过两个星期的设计也从中学到了不少东西，更深刻的理解了课本中的内容。C+ 是一门实践性较强的课程，为了学好这门课程， 必须在掌握理论知识的同时， 加强上机实践。同时再次深刻理解了C+ 中类的思想和实现，链表的概念和相关操作。 根据实际问题的需要， 对个方面的优缺点加以综合平衡，从中选择比较适宜的实现方法。在本

22、次课程设计中， 我明白了理论与实际相结合的重要性， 并提高了自己组织数据及编写程序的能力，培养了基本的， 良好的程序设计技能。提高综合运用所学知识的能力。在这次课程设计中曾遇到了不少问题，就单凭我一个人的能力很难准时有效的完成这次的课程设计， 在此，我忠心感谢我的指导老师阳慧。阳老师对工作认真负责， 耐心辅导， 知识丰富。 在这次课程设计中给了我很大的帮助。她严谨的治学精神和深厚的理论水平都使我获益非浅。同时还要感谢我的同学， 他们为我提出了很多有用的建议， 帮助我完成了这次的课程设计。最后也要感谢我们学校为我们提供良好的编程环境，使我们能够按时完成任务。名师资料总结 - - -精品资料欢迎下

23、载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 22 页 - - - - - - - - - 参考文献1 、谭诰强主编C+程序设计北京：清华大学出版社2004.6 2 、Diane Zak 著马良荔译 c+编程导论 (第二版 ) 电子工业出版社3 、Judy school 著晏海华译 c+编程 - 从问题分析到程序设计实验指导书电子工业出版社4 郑阿奇，丁有和 . Visual C+教程， 2007年 12 月第一版，北京：机械工业出版社。 2007.12 5 伍俊良 Visual C+ 课程设计与系统开发

24、案例 2002 年 11 月第 1 版，清华大学出版社。2003.1 6 朱时银，马承志，杨飞，王华. C+ Builder 5 编程实例与技巧， 2001年 2 月第一版，北京：机械工业出版社.2001.2 7 孙鑫，余安萍 . VC+ 深入详解， 2007 年 3 月第 1 版， 电子工业出版社，2007.3 8 杨富国，王浩，唐巧奇，王健. Visual C+程序设计开发案例解析，2006年 3 月第一版，北京：清华大学出版社，北京交通大学出版社，2006.3 9 Walter Savitch，江山 . Absolute C+中文版， 2007 年 4 月第 1 版，机械工业出版社，20

25、07.4 附录：源程序代码/ 排序算法的实现#include using namespace std; /插入排序void swap(int Array,int i,int j) int temp=Arrayi; Arrayi=Arrayj; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 22 页 - - - - - - - - - Arrayj=temp; void InsertSort(int Array,int n) for(int i=1;i0;j-) if(

26、ArrayjArrayj-1) swap(Array,j,j-1); else break; /优化插入排序void ImprovedInertSorter(int Array,int n) int Temp; for(int i=1;i=0)&(TempArrayj) Arrayj+1=Arrayj; j=j-1; Arrayj+1=Temp; /二分法插入排序void BinaryInsertSorter(int Array,int n) int temp; int left,right,middle; for(int i=1;in;i+) temp=Arrayi; left=0;righ

27、t=i-1; while(left=right) middle=(left+right)/2; if(temp=left;j-) Arrayj+1=Arrayj; Arrayleft=temp; /优化冒泡排序void ImprovedBubbleSorter(int Array,int n) bool NoSwap; for(int i=1;i=i;j-) if(Arrayj,Arrayj-1) swap(Array,j,j-1); NoSwap=false; if(NoSwap) return; /直接选择排序void StraighSelectSorter(int Array,int n

28、) for(int i=0;in-1;i+) int Smallest=i; for(int j=i+1;jn;j+) if(ArrayjArraySmallest) Smallest=j; swap(Array,i,Smallest); /Shell 排序void ModifiedInsertSort(int Array,int n,int delta) for(int i=delta;i=delta;j-=delta) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共

29、 22 页 - - - - - - - - - if(Arrayj0;delta/=2)for(int j=0;jdelta;j+) ModifiedInsertSort(&Arrayj,n-j,delta); /优化的快速排序int SelectPivot(int left,int right) return (left+right)/2; int Partition(int Array,int left,int right) int temp; int i=left; int j=right; temp=Arrayj; while(i!=j) while(Arrayii) i+; if(i

30、temp)&(ji) j-; if(ij) Arrayi=Arrayj; i+; Arrayi=temp; return i; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 22 页 - - - - - - - - - void ImprovedQuickSorter(int Array,int left,int right) if(right=left) return ; int pivot=SelectPivot(left,right); swap(Array,p

31、ivot,right); pivot=Partition(Array,left,right); ImprovedQuickSorter(Array,left,pivot-1); ImprovedQuickSorter(Array,pivot+1,right); /两路归并排序void Merge(int Array,int TempArray,int left,int right,int middle) for(int j=left;j=right;j+) TempArrayj=Arrayj; int index1=left; int index2=middle+1; int i=left;

32、while(index1=middle)&(index2=right) if(TempArrayindex1TempArrayindex2) Arrayi+=TempArrayindex1+; else Arrayi+=TempArrayindex2+; while(index1=middle) Arrayi+=TempArrayindex1+; while(index2=right) Arrayi+=TempArrayindex2+; void MergeA(int Array,int TempArray,int left,int right,int middle) int index1,i

33、ndex2; int i,j,k; for(i=left;i=middle;i+) TempArrayi=Arrayi; for(j=1;j=right-middle;j+) TempArrayright-j+1=Arrayj+middle; for(index1=left,index2=right,k=left;k=right;k+) if(TempArrayindex1,TempArrayindex2) Arrayk=TempArrayindex1+; else Arrayk=TempArrayindex2-; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -

34、- - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 22 页 - - - - - - - - - void TwoWayMergeSorter(int Array,int TempArray,int left,int right) if(leftright) int middle=(left+right)/2; TwoWayMergeSorter(Array,TempArray,left,middle); TwoWayMergeSorter(Array,TempArray,middle+1,right);MergeA(Array,TempArray,

35、left,right,middle); /桶式排序void BuckerSorter(int Array,int n,int max) int *TempArray=new intn; int * count=new intmax; int i; for(i=0;in;i+) TempArrayi=Arrayi; for(i=0;imax;i+) counti=0; for(i=0;in;i+) countArrayi+; for(i=1;i=0;i-) Array-countTempArrayi=TempArrayi; /基数排序void RadixSorter(int Array,int

36、n,int d,int r) int *TempArray=new intn; int *count=new intr; int i,j,k; int Radix=1; for(i=1;i=d;i+) for(j=0;jr;j+) countj=0; for(j=0;jn;j+) k=(Arrayj/Radix)%r; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 22 页 - - - - - - - - - countk+; for(j=1;j=0;j-) k=(A

37、rrayj/Radix)%r; countk-; TempArraycountk=Arrayj; for(j=0;jn;j+) Arrayj=TempArrayj; Radix*=r; /打印数据void printArray(int Array,int n) int i,j; cout 你选择从小到大还是从大到小的排序,前者输入1,后者输入2:j; cout 排序的结果是:endl; if(j=1) for(i=0;in;i+) coutArrayi=0;i-) coutArrayi ; coutendl; int main() int array20,n; int sign=0,tempA

38、rray20,max=100; int d=2,r=10; cout 在输入数列之前，请输入待排序数据的个数：n; cout 现在可以输入数列：endl; for(int i=0;iarrayi; tempArrayi=0; cout*endl;cout 系统供你选择的排序方法:endl; cout 插入排序 -1 优化插入排序 -2 二分法插入排序-3endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 22 页 - - - - - - - - - cout 优

39、化冒泡 -4 直接选择 -5 SHELL 排序 -6endl; cout 优化的快速排序-7 两路归并排序 -8 桶式排序 -9endl; cout 基数排序 -10endl; cout*endl;cout 请输入相应数字：sign; switch(sign) case 1: InsertSort(array,n);break; case 2: ImprovedInertSorter(array,n);break; case 3: BinaryInsertSorter(array,n);break; case 4: ImprovedBubbleSorter(array,n);break; ca

40、se 5: StraighSelectSorter(array,n);break; case 6: ShellSorter(array,n);break; case 7: ImprovedQuickSorter(array,0,n-1);break; case 8: TwoWayMergeSorter(array,tempArray,0,n-1);break; case 9: BuckerSorter(array,n,max);break; case 10: RadixSorter(array,n,d,r);break; default:break; printArray(array,n); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 22 页 - - - - - - - - -