数学系课程设计注意事项： 算法设计课程设计 --------------快速排序算法设计 班级：信计07级2班 成员：陈悦（组长），曾海龙 何雪松，李欢，吕博，徐强，房辉 前言 排序（sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
）的任意序列，重新排列成一个关键字有序的序列。由于待排序的记录数量不同，使得排序的过程中涉及的存储器不同，可将排序的方法分为两大类：一类是内部排序指的是待排序记录存放在计算机随机存储器中进行的排序过程；另外一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。本次可程序设计主要是利用内部排序中的冒泡排序、选择排序和二路归并排序。利用matlab在矩阵处理方面的优势，结合相关排序思想，编写程序解决问题。 一、问题描述 考虑下列实数集合（数据按从左到右、然后从上到下排列）： 19.99 3.03 1.52 4.99 0.39 5.31 1.85 0.38 4.52 1.08 4.26 4.08 12.00 4.32 5.02 3.58 6.22 2.33 5.70 3.41 6.12 14.10 15.13 9.16 1.08 18.99 10.02 7.12 3.84 6.90 5.79 9.08 7.94 7.39 10.49 17.91 1.71 11.38 5.85 5.88 8.94 6.35 8.10 6.19 9.52 8.93 11.20 18.66 5.79 17.04 2.53 17.79 13.49 12.45 8.24 8.29 7.94 14.20 8.96 11.96 14.30 5.10 11.28 10.49 2.12 19.16 12.84 9.32 9.35 8.92 14.51 9.27 15.21 4.64 18.66 6.45 2.43 1.40 15.35 15.41 9.86 10.17 9.39 15.70 10.46 16.34 9.05 2.71 7.56 15.42 4.76 13.36 17.41 12.21 10.87 10.11 16.11 11.43 17.05 3.53 18.82 17.37 7.56 18.67 2.71 19.04 12.26 11.79 13.31 18.07 14.39 19.00 19.38 14.07 7.51 16.49 1.36 2.00 19.14 12.46 18.85 14.47 19.72 16.59 19.54 7.18 16.97 1.57 1.03 5.36 编制程序，分别用选择排序法、起泡排序法和二路并归排序法对表中数据进行排序。 二、理论知识 （一）冒泡排序的基本思想： 依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数），将小数放前，大数放后，一直比较到最小数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。如此下去，直至最终完成排序。 （二）选择排序的基本思想： 每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。我们主要介绍简单选择排序、树型选择排序和堆排序。 简单选择排序的基本思想：第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行i-1趟比较，直到所有记录排序完成为止。例如：进行第i趟选择时，从当前候选记录中选出关键字最小的k号记录，并和第i个记录进行交换。下面大括号内为当前候选记录，大括号外为当前已经排好序的记录。 初始序列 ｛ 48 62 35 77 55 14 35 98｝ 第一趟 14 ｛ 62 35 77 55 48 35 98 ｝ 第二趟 14 35 ｛ 62 77 55 48 35 98 ｝ 第三趟 14 35 35 ｛ 77 55 48 62 98 ｝ 第四趟 14 35 35 48 ｛55 77 62 98 ｝ 第五趟 14 35 35 48 55 ｛77 62 98 ｝ 第六趟 14 35 35 48 55 62 ｛77 98 ｝ 结果 14 35 35 48 55 62 77 98 （三）二路归并排序思想： 把两个或多个有序表合并成一个有序表的过程称为归并（Merge）。若归并的有序表有两个，叫做二路归并。一般地，若归并的有序表有k个，则称为k路归并。二路归并最为简单和常用，既适用于内部排序，也适用于外部排序。 对有序表反复利用归并过程进行排序的方法称为归并排序（Merging Sort）。利用二路归并操作的排序称为二路归并排序。 二路归并排序的过程是： （1）把无序表中的每一个元素都看作是一个有序表，则有n个有序子表； （2）把n个有序子表按相邻位置分成若干对（若n为奇数，则最后一个子表单独作为一组），每对中的两个子表进行归并，归并后子表数减少一半； （3）反复进行这一过程，直到归并为一个有序表为止。 举例：（括号内的是有序序列） 第一趟 [33 51] [62 96] [17 87][28] 第二趟 [33 51 62 96] [17 28 87] 第三趟 [17 28 33 51 62 87 96] 三、程序清单 (1)function b=bubblesort(b) 冒泡排序函数 (2) function b=selectsort(b) 选择排序函数 (3) function b=msort(a,b,low,high)二路归并排序函数----分开 (4)function b=merge(a,b,low,mid,high) 二路归并排序函数----合并 (5) function b=lrsort(b,f) 对矩阵进行由左至右升序排序函数 (6) function b=updownsort(b,f)对矩阵进行有上至下升序排序函数 (7)function main对矩阵进行操作的主函数 四、程序实现 （1）function b=bubblesort(b) % 冒泡排序源代码 N=length(b); right=N-1; for i=1:(N-1) for j=1:right if b(j)>b(j+1)%比较前后数据项的大小 tmp=b(j); %将当前数据项与相邻
单元
初级会计实务单元训练题天津单元检测卷六年级下册数学单元教学设计框架单元教学设计的基本步骤主题单元教学设计
进行位置交换 b(j)=b(j+1); b(j+1)=tmp; end end end （2）function b=selectsort(b) %选择排序源代码 [n m]=size(b); for h=1:m-1 k=h; for l=h+1:m if b(l)
格式
pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载
b=lrsort(待排序矩阵,排序类型)。排序类型："冒泡排序bubble、选择排序select、二路归并msort"'); end （6）function b=updownsort(b,f) %对矩阵每列由上而下排序，将每列转换成行进行排序，然后再转行成对应的行 [n m]=size(b); switch f %选择排序类型 case 'bubble'%冒泡排序 for i=1:m b(:,i)=bubblesort(b(:,i)')'; end case 'select'%选择排序 for i=1:m b(:,i)=selectsort(b(:,i)')'; end case 'msort'%二路归并排序 for i=1:m b(:,i)=msort(b(:,i)',b(:,i)',1,n)'; end otherwise disp('"updownsort"语法错误！正确格式b=updownsort(待排序矩阵,排序类型)。排序类型："冒泡排序bubble、选择排序select、二路归并msort"'); end （7）main.m b= [19.99 3.03 1.52 4.99 0.39 5.31 1.85 0.38 4.52 1.08 4.26 4.08 12.00 4.32 5.02 3.58 6.22 2.33 5.70 3.41 6.12 14.10 15.13 9.16 1.08 18.99 10.02 7.12 3.84 6.90 5.79 9.08 7.94 7.39 10.49 17.91 1.71 11.38 5.85 5.88 8.94 6.35 8.10 6.19 9.52 8.93 11.20 18.66 5.79 17.04 2.53 17.79 13.49 12.45 8.24 8.29 7.94 14.20 8.96 11.96 14.30 5.10 11.28 10.49 2.12 19.16 12.84 9.32 9.35 8.92 14.51 9.27 15.21 4.64 18.66 6.45 2.43 1.40 15.35 15.41 9.86 10.17 9.39 15.70 10.46 16.34 9.05 2.71 7.56 15.42 4.76 13.36 17.41 12.21 10.87 10.11 16.11 11.43 17.05 3.53 18.82 17.37 7.56 18.67 2.71 19.04 12.26 11.79 13.31 18.07 14.39 19.00 19.38 14.07 7.51 16.49 1.36 2.00 19.14 12.46 18.85 14.47 19.72 16.59 19.54 7.18 16.97 1.57 1.03 5.36 ]; c=lrsort(b,'bubble');%利用冒泡排序，将目标矩阵从左至右升序排列 c=updownsort(c,'bubble');%利用冒泡排序，将目标矩阵从上至下升序排列 d=lrsort(b,'select');%利用选择排序，将目标矩阵从左至右升序排列 d=updownsort(d,'select');%利用选择排序，将目标矩阵从上至下升序排列 e=lrsort(b,'msort');%利用二路归并排序，将目标矩阵从左至右升序排列 e=updownsort(e,'msort');% 利用二路归并排序，将目标矩阵从上至下升序排列 五、程序结果 b= 0.38 0.39 1.08 1.52 1.85 3.03 4.08 4.26 4.52 4.99 5.31 11.38 14.3 1.03 1.57 2 3.58 4.32 5.02 5.7 6.12 6.22 9.16 10.49 12 16.34 1.08 2.33 3.41 5.36 6.35 7.12 7.39 7.94 9.08 10.02 13.49 14.2 17.91 1.36 2.43 4.64 5.85 6.9 8.1 8.93 8.94 9.52 11.2 14.1 15.13 18.66 1.4 2.71 5.79 6.19 7.18 8.96 9.32 9.35 11.96 12.45 15.21 15.7 18.82 1.71 3.84 5.88 6.45 8.29 9.27 10.17 10.46 12.84 14.51 15.42 17.79 18.99 2.12 4.76 7.51 8.24 8.92 9.86 10.49 11.28 15.35 15.41 17.04 18.66 19.16 2.53 5.1 7.56 9.05 9.39 12.21 13.36 14.39 16.49 17.37 17.41 18.67 19.38 2.71 5.79 7.94 10.87 11.43 12.46 14.07 16.11 16.97 18.07 19 19.04 19.72 3.53 7.56 10.11 11.79 12.26 13.31 14.47 16.59 17.05 18.85 19.14 19.54 19.99 六、参考文献 [1]. 王红梅. 算法设计与分析. 北京：清华大学出版社，2010。 [2].徐瑞，黄兆东，阎凤玉.Matlab 科学与工程分析.北京：科学出版社，2007. [3].严蔚敏，吴伟民.数据结构.北京：清华大学出版社.2006. 七、小组成员分工合作清单 姓名 班级 任务分工 陈悦 信计072班 程序的编写 徐强 何雪松 相关资料的查阅和收集 吕博 曾海龙 李欢
论文
政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载
的撰写 房辉 八、总结： 经过本次课程设计，首先，让我们熟悉了matlab程序设计的一般
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
，相关函数的调用方式，以及matlab在处理矩阵方面的所发挥的优势！其次，通过本次课程设计让我体会到对数组排序不同的排序方法，各自的优缺点，比如，冒泡排序的主体思想简单，但是在排序处理的时间方面没有其他两种排序方法快！而二路归并排序是一种稳定的排序方法，在内部排序中很少使用二路归并排序。选择排序在本次设计中使用的是简单选择排序，是冒泡排序方法的一个改进，在计算次数上有所下降，从而时间复杂度也相对较小。另外，通过本次课程设计，让我意思到团队协作的重要性，我们在本次设计中各司其职，各尽其责，主要将本组队员再细分成三组-------找资料、编写程序、撰写论文！这样减少了本次设计的整体完成时间！大大提高了程序设计效率！
浙公网安备 33021202002483