《[计算机软件及应用]排序综合.doc》由会员分享，可在线阅读，更多相关《[计算机软件及应用]排序综合.doc（36页珍藏版）》请在三一办公上搜索。
1、*大学信息科学与工程学院数据结构综合设计报告 排序综合(可视化)学号： *姓名： *专业： *班级： * 实验室（中心）：*指导老师： * 完成时间： 2013-06-25*大学信息科学与工程学院课程设计任务书课 程 数据结构班级*指导教师*题 目排序综合 同组人数1设计要求 利用随机函数产生N个随机整数(20000以上),对这些数进行多种方法进行排序。要求：1) 至少采用三种方法实现上述问题求解2) 比较每一种排序算法的性能报告书要求设计报告主要包括内容（参见后面的格式）：1系统的功能需求及分析2类结构及类设计说明3系统总体结构4系统实现及主要代码5系统功能测试6设计体会要求： 学生完成课程
2、设计后，每个同学均应提交课程设计报告及软件； 设计报告要求文字通畅，排版规范； 设计报告文字原则上不少于3000字（程序代码除外），并装订成册。版面要求1题目用黑体三号，段后距18磅（或1行），居中对齐；2标题用黑体四号，段前、段后距6磅（或0.3行）；3正文用小四号宋体，行距为固定值“20”，程序代码用固定值“15”；4标题按“一”、“”、“1”、“”顺序编号。上机时间安排星期周次一二三四五六日第17周1-41-41-41-41-4自定自定第18周1-41-41-41-41-4自定自定指导地点及考核时间1、指导地点：*信息技术实验室2、考核时间：第18周星期五上午（答辩方式考核，学生用PPT
3、汇报及演示）摘 要数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。排序算法是数据结
4、构学科经典的内容，其中内部排序现有的算法有很多种，其中包含冒泡排序，直接插入排序，简单选择排序，希尔排序，快速排序，堆排序等，各有其特点。对排序算法比较的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。关键字：数据结构；算法比较；比较次数；时间复杂度35-
5、 35 -目 录摘要 03一、概要 05二、排序算法 06三、流程图与各功能界面简介 11四、各功能模块简介 14五、存储与显示 16 六、排序过程演示 18七、结果分析 22 八、主要代码 23结束语 35参考文献 36 教师评阅意见： 签名： 年 月 日成绩：以下为设计报告正文一:概要1.1设计目的 数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学
6、习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。1）本演示程序对以下5种常用的内部排序算法进行实测比较：冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序；2）待排序表的元素的关键字为整数。比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）；3）演示程序以以用户和计算机的对话方式执行，在计算机终端上显示提示信息，对随机数组进行排序，并输出比较指标值；5）利用可视化界面让用户进行选择并显示出运行结果。4）最后对结果作出简单分析。1.2预期目标按要求输入不同
7、的操作。选择后，根据不同的选择进行不同的操作，最终达到对各算法进行比较的目的。通过此次课程设计主要达到以下目的了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二:排序算法 2.1各排序算法的特点1）冒泡排序冒泡排序的基本概念是：依次比较相邻的两个数，将大数放在前面，小数放在后面。即首先比较第1个和第2个数，将大数放前，小数放后。然后比较第2个数和第3个数
8、，将大数放前，小数放后，如此继续，直至比较最后两个数，将大数放前，小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数），将大数放前，小数放后，一直比较到最小数前的一对相邻数，将大数放前，小数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。如此下去，直至最终完成排序。由于在排序过程中总是大数往前放，小数往后放，相当于气泡往上升，所以称作冒泡排序。主要代码:void MaopaoSort(int *arr,int n)int temp,i=0,j=0,k=0; for(i=1;in;
9、i+)for(j=0;jarrj+1)temp=arrj+1;arrj+1=arrj;arrj=temp;2）插入排序每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。主要代码:void insertSort(int *a, int n) int i,j,temp; for(i = 1; i=0 & tempaj) aj+1 = aj; j-; aj+1 = temp; 3）选
10、择排序（1）在一组元素ViVn-1中选择具有最小排序码的元素（2）若它不是这组元素中的第个元素，则将它与这一组元素中的第一个元素对调；（3）在这组元素中剔除这个具有最小排序码的元素，在剩下的元素Vi+1Vn-1中重复执行第（1）（2）步，直到剩余元素只有一个为止。主要代码:void selectSort(int *a,int n) int i,j,k,temp; for(i = 0; in - 1; i+) k = i; for(j = i+1; jaj) k = j; if(i=k) continue; temp = ai; ai = ak; ak = temp; 4）快速排序首先检查数据列
11、表中的数据数，如果小于两个，则直接退出程序。如果有超过两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序；主要代码:void quickSort(int *a, int i, int j) int m,n,temp,k; n = j;m = i; k = a(i+j)/2; do while(amk & mk & ni) n-; if(m=n) temp = am; am = an; an = temp; m+; n-; while(m=n); if(mi) quickSort(a,i,n); 5） 希尔排序先取一个正整数d1
12、n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2=1) for(i = k; i=0 & xaj) aj+k = aj; j-=k; aj+k = x; k/=2; 2.2各算法的比较方法1.稳定性比较 插入排序、冒泡排序、简单选择排序及其他线形排序是稳定的 希尔排序、快速排序是不稳定的2.时间复杂性比较 插入排序、冒泡排序、选择排序的时间复杂性为O(n2) 其它非线形排序的时间复杂性为O(nlog2n) 线形排序的时间复杂性为O(n);3.辅助空间的比较 线形排序的辅助空间为O(n),其它排序的辅助空间为O(1);4.其它比较插入、冒泡排序的速度较慢，但参加排序的序列
13、局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序。当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序 三:流程图与各功能界面简介3.1使用流程图:查看结果退出希尔排序快速排序选择排序冒泡排序插入排序产生随机数排序演示使用须知及简介 登录退出关于3
14、.2使用须知界面3.3登录界面3.3演示界面3.4关于界面3.4提示界面四:各功能模块简介4.1登录功能 为了保护本演示程序的的安全性，本程序设置了登录密码保护，当用户在输入正确的账号和密码后，才可以使用本演示程序。这也从一定程度上保证了本系统的安全性。4.2产生随机数功能 当用户在输入最小数，最大数和产生的随机数个数后单击产生随机数按钮系统则会按照用户的需要产生随机数并在标签中显示前200个随机数。注意:前面文本框填最小数，中间的填最大数，当最小数大于最大数后系统则会给用户进行提示（），随机数的个数不能够超过100000个否则会提示（）。当正确的输入几个数后才可以产生随机数。4.3各排序功能
15、及事件1）冒泡排序 在用户单击冒泡排序按钮后响应 private void maopaobutton_Click(object sender, EventArgs e) 事件来调用冒泡排序算法对随机数进行排序。并在maopaolabel中显示所用步数和消耗时间。2）插入排序 在用户单击冒泡排序按钮后响应 private void insertbutton_Click(object sender, EventArgs e) 事件来调用插入排序算法对随机数进行排序。并在insertlabel中显示所用步数和消耗时间。3） 选择排序 在用户单击冒泡排序按钮后响应 private void Selec
16、tbutton_Click(object sender, EventArgs e) 事件来调用选择排序算法对随机数进行排序。并在Selectlabel中显示所用步数和消耗时间。4）快速排序 在用户单击冒泡排序按钮后响应 private void quickbutton_Click(object sender, EventArgs e) 事件来调用快速排序算法对随机数进行排序。并在quicklabel中显示所用步数和消耗时间。5） 希尔排序 在用户单击冒泡排序按钮后响应 private void shellbutton_Click(object sender, EventArgs e) 事件来调
17、用希尔排序算法对随机数进行排序。并在shelllabel中显示所用步数和消耗时间。4.4结果显示功能 通过待用Result对话框来进行排序过程和排序前后的随机数变化进行显示，当单击排序前按钮时触发private void button2_Click(object sender, EventArgs e)事件，通过Result对话框显示排序前的随机数，当单击排序后按钮是触发private void button3_Click(object sender, EventArgs e)事件，也通过Result对话框显示排序后的随机数，同时当满足显示排序过程条件时，会调用Result对话框显示排序的过程
18、。 注意:由于考虑到对话框加载的时间问题，在Result对话框中最多显示前2000个随机数。五:主要存储与显示5.1产生随机数并存储通过创建随机数种子Random Random1 = new Random();然后定义一个变量获取随机数int i1 = Random1.Next(min, max+1);从而在每次调用时都将产生从min到max之间的随机数,其中min和max分别为用户输入的最小值和最大值。定义全局数组int A; int B;令A = new intcount;B = new intcount;（count为用户输入的随机数个数，保证可以进行动态分配数组大小，不造成空间的浪费。
19、）其中数组B用来存储产生的随机数，并且不会进行改变，数组A用来对随机数数组进行复制后让各排序算法进行排序然后比较各排序算法的好坏。数组的复制代码: for (int o = 0; o count; o+) Ao = Bo; 5.2在scand(label)中显示前200个随机数 int i1 = Random1.Next(min, max+1); if (i + 1) = 200) scand.Text += i1 + ; if (i + 1) % 20 = 0&(i+1)=200) scand.Text+=n+ ; 5.3在listView中增加节点的过程首先在产生随机数的时候就要生成lis
20、tview的标题。并对标题的宽度进行设置，具体如下：listView1.View = View.Details;listView1.Columns.Add(步数, 50); listView1.Columns.Add(互换的元素, 100); listView1.Columns.Add(交换后顺序, 200);这时listview中的标题就已经显示完毕。然后显示子项，为了使每次产生的子项不重复，在进行显示前要清除listview中的子项listView1.Items.Clear();然后在每次变化后记录更改后的数组并进行显示，具体过程如下代码: ListViewItem.ListViewSub
21、Item sb = new ListViewItem.ListViewSubItem();ListViewItem item = new ListViewItem();item.Text = Convert.ToString(k); (k为交换次数)sb.Text = Convert.ToString(Aj) + + Convert.ToString(Aj + 1);item.SubItems.Add(sb);sb = new ListViewItem.ListViewSubItem();for (h = 0; h count; h+) sb.Text += Convert.ToString(
22、Ah) + ;item.SubItems.Add(sb);listView1.Items.Add(item);5.4排序过程的画面显示 1）显示每次改变后的随机数数组，把交换的元素标记为红色。把与上次改变数组未发生元素交换的随机数数组标记为蓝色。首先定义一个结果显示对话框Result dlg = new Result();并把结果显示对话框的标题改为dlg.Text = *排序演示过程;然后通过调用Result对话框中的createlabels()函数显示当前数组的各元素。Createlabels()函数会根据数组的大小动态的产生随机数个数个labels。其中标记为红色即labelsl.For
23、eColor = System.Drawing.Color.Red;同理标记为蓝色也是相同过程。 2）记录改变的元素位置并在相应位置进行画线。在结果对话框中定义 List X1 = new List();List X2 = new List();List Y1 = new list();List Y2 = new List();其中用（X1，Y1）；来存储第一个点的坐标，用（X2，Y2）来存储第二个点的坐标。每次进行交换时都会记录下这些点的坐标。然后调用系统Graphics进行画线。例如画一条线的代码为: Graphics g = e.Graphics;Pen pen1 = new Pen(C
24、olor.Blue);g.DrawLine(pen1, X1a, Y1a, X2a, Y2a);5.5各排序所耗时间的计算与显示 在程序运行前定义时间对象DateTime d1 = DateTime.Now;排序完后定义DateTime d2 = DateTime.Now;然后在标签中显示maopaolabel.Text += 所用时间: + Convert.ToString(d2-d1) + n;这样即完成了计算并显示。六:排序过程演示6.1冒泡排序过程演示6.2选择排序过程演示6.3快速排序过程演示6.4插入排序过程演示6.5希尔排序过程演示6.6几种排序的比较6.7排序前的随机数6.8排
25、序后的随机数七：结果分析排序种类1010010001000050000冒泡排序10.01100501.16246910.01000580.770516419.799198620.00900551.01459060.00700610.788525219.833221730.01265791.02631540.00600400.785523719.742158140.00914360.97408300.00600400.772518819.763175950.00800531.24556790.00600580.774519119.7921976选择排序10.00100070.03792090.0
26、0300060.29320167.363908920.00100070.03702470.00300160.29319367.565039130.00200040.04002710.00300150.31521207.490997340.00200230.03870780.00300340.29219437.566.45550.00099880.03802760.00300200.29619707.4569685快速排序10.00300150.07714180.00100300.00600350.033021520.00200080.07741190.00100020.00601010.032
27、019930.00200080.07705650.00099880.00600400.032020940.00200140.07655130.00100060.00600960.037022350.00200500.07868370.00100070.00600260.0320232插入排序10.00200090.04058740.00400270.32321318.251500520.00200040.04238160.00300160.35023268.179455730.00099880.04078200.00300110.35323978.281521940.00200460.0400
28、2810.00300200.32421528.534692650.00199990.04233030.00300100.32421298.1964619希尔排序10.00100070.00200700.00100440.00500800.028022920.00099930.00199900.00100250.00600960.027018930.000.00275100.00100350.00500330.028021440.00100390.00400170.00100250.00500520.027020450.00100850.00100070.000.00500570.0270180
29、 分析:当产生的随机数个数为10与100时由于要加载listview导致时间比真正排序长，但从中我们也不难发现希尔排序最快，而冒泡排序最慢。当随机数个数在1000、10000和50000时我们通过数据就可以发现，希尔排序与快速排序相对最快，其次到选择排序，再到插入排序，最后冒泡排序是最慢的。 综上我们可以发现实验的结果与我们知道的理论值是相同的。八:主要代码8.1Form1中主要代码(注意:排序的代码只留了一个冒泡，其它方法与之类型，这里不予一一列举)using System;using System.Collections.Generic;using System.ComponentMode
30、l;using System.Data;using System.Drawing;using System.Linq;using System.Text;using System.Threading.Tasks;using System.Windows.Forms; int A; int B;/保存随机数数的数组 private void createbutton_Click(object sender, EventArgs e) maopaolabel.Text = null; xunzelabel.Text = null; quicklabel.Text = null; insertlab
31、el.Text = null; shelllabel.Text = null; listView1.Columns.Clear(); listView1.Items.Clear(); Random Random1 = new Random(); max = Convert.ToInt32(MaxtextBox.Text); min = Convert.ToInt32(MintextBox.Text); count = Convert.ToInt32(CounttextBox.Text); Random ra = new Random(unchecked(int)DateTime.Now.Tic
32、ks); B = new intcount; if (max min) scand.Text = 对不起你输入的范围不正确!; else scand.ForeColor = System.Drawing.Color.Black; scand.Text = null; scand.Text += 产生随机数:; for (int i = 0; i count; i+) /产生min到max的随机数 int i2 = ra.Next(min, max + 1); int i1 = Random1.Next(min, max+1); Bi = i1; if (i + 1) = 200) scand.
33、Text += i1 + ; if (i + 1) % 20 = 0&(i+1) 8 & ResultcomboBox.SelectedIndex = 0&count 15 & ResultcomboBox.SelectedIndex = 0) MessageBox.Show(你要显示的演示过程过大,请重新输入随机数个数，或者选择不显示); maopaobutton.Enabled = false; quickbutton.Enabled = false; Selectbutton.Enabled = false; shellbutton.Enabled = false; insertbutton.Enabled = false; if (ResultcomboBox.SelectedIndex = 1 | Convert.ToInt32(CounttextBox.Text) 50000) MessageBox.Show(考
