《排序算法比较课程设计.doc》由会员分享，可在线阅读，更多相关《排序算法比较课程设计.doc（15页珍藏版）》请在三一办公上搜索。
1、数据结构课程设计排序算法的比较专 业： 计算机科学与技术 班级学号： 学生姓名： 系 别： 信息技术工程学院指导教师： 时 间： 1.1题目排序算法的比较1.2 课题来源课程组自拟1.3课题类型： 综合型1.4 目的意义： 通过该课程设计的操作与实践，使学生真正掌握数据结构相关算法的实现及应用方法，在一定程度上提高使用数据结构相关算法的综合设计能力，具体掌握的基本能力如下：（1）、使学生能够综合运用所学知识，解决实际问题。培养学生对整体课程知识综合运用和融会贯通的能力。（2）、掌握各种排序算法（直接插入排序、冒泡排序、快速排序、简单选择排序）的思路核心，比较他们之间的优劣 （3）、培养学生分析
2、、解决问题和编程等实际动手能力。1.5基本要求：（1）、 任意性：系统首先生成1000个随机整数，然后分别用不同的排序方法对其进行升序排序，给出每种方法的比较次数或所用时间。（2）、友好性：界面要友好，输入有提示，尽量展示人性化。（3）、可读性：源程序代码清晰、有层次。 (4)健壮性：用户输入非法数据时，系统要及时给出警告信息。 1.6使用的各种工具软件和工作环境:工作环境：第一教学楼四楼实验室五机房。运行环境：Microsoft Visual C+6.01.7设计内容简介：包括课程设计的基本结构流程、运行环境等（1）、课程设计的基本结构流程头文件：#include stdlib.h/包括两函
3、数srand()和rand来设置随机种子以生随机数#include time.h/时钟static long qc2=0, bc2=0,sc2=0,ic2=0;/定义全局变量用于输出比较次数主函数：void main产生n个随机数、定义数组并且调用操作函数。操作函数void operate：可选择四种排序算法中的任意一种，调用此排序函数并且输出排序所有时间、排序交换次数和排序比较次数。冒泡排序函数Bubblesort：通过无序区中相邻记录关键字值间的比较和位置的交换，使关键字最小的记录如“气泡”一样逐渐漂浮到水面。过程：首先将一第n个记录的关键字和第n-1个记录关键字进行比较，若为逆序，则将两
4、个记录交换之，然后比较倒数第n-2和倒数n-3记录的关键字。依次类推，直至第2个记录和第1个记录的关键字进行过比较为止。上述过程称做第一趟起泡排序，其结果使得关键字最小的记录被安置到第一个记录的位置上。然后进行第二趟起泡排序，对后n-1个记录进行同样操作，其结果是使关键字次小的记录被安置到第i个记录的位置上。简单选择排序函数selectsort： 每趟从待排序列中选取一个关键字值最小的记录，用m记录其最小数的位置，然后判断其位置是否放在第I个位置，如果不与第I个位置相同则交换，依次判断次小关键字位置，顺序放在已排序的记录的最后。直接插入排序函数insertsort：每次将一个待排序的记录，按其
5、关键字值的大小插入到已经排序部分的文件中的适当位置上，直到全部插入完成。快速排序函数quicksort：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。流程图 开始选择方式手动随机调用程序选择排序方式 冒泡选择直接插入快速输出结果结束程序源代码：#include #include#include #include #include #define MAX 1000using namespace std;void print(long R,long n)for(int i=1;i=n;i+)co
6、utsetw(4)1)long lastExchangeIndex=1;/表示已经有序for(long j=1;ji;j+)if(Rj+1Rj)long t=Rj;Rj=Rj+1;Rj+1=t; BT+;lastExchangeIndex=j;/记下进行的位置i=lastExchangeIndex;/本趟进行过交换的最后一个记录的位置cout第y趟:;y+;for(long x=1;x=i;x+)coutsetw(4)Rx;coutsetw(3)Ri+1;for(x=i+2;x=n;x+)coutsetw(4)Rx;cout;coutendl;return BT;/-/选择排序/-/stati
7、c long ST=0;long SelectMinKey(long R,long i,long n)/在 Ri.R.length 中选择关键字最小的记录long temp=i;/记录最小的元素值的位置for(int j=i;jRj)temp=j;/ST+;return temp;long selectsort(long R,long n)long j,i,t;long y=1;int ST=0;for( i=1;in;i+)j = SelectMinKey(R,i,n);/ 在 L.ri.L.length 中选择关键字最小的记录if (i!=j) / 与第 i 个记录交换t=Ri;Ri=Rj
8、;Rj=t;ST+; cout第y趟: ;y+;for(long x=1;x=i;x+)coutsetw(4)Rx;coutsetw(3)Ri+1;for(x=i+2;x=n;x+)coutsetw(4)Rx;cout;/print(R,n);coutendl;return ST;/-/直接插入排序/-long insertsort(long R, long n)long y=1;long IT=0,j;for(long i=2;i=n;+i)if(RiRi-1)R0=Ri;/复制为哨兵IT=IT+1;for( j=i-1;R0Rj;-j)Rj+1=Rj;/记录后移IT=IT+1;Rj+1=R
9、0;/插入到正确位置IT=IT+1;cout第y趟: ;y+;coutsetw(4)R1;for(long x=2;x=i;x+)coutsetw(4)Rx;cout;for(x=i+1;x=n;x+)coutsetw(4)Rx;coutendl;return IT;/-/快速排序/-static long QT=0;int Partition (long R, long low, long high,long n)R0 =Rlow; long pivotkey = Rlow; / 枢轴 QT=QT+2;while (lowhigh) while(low=pivotkey)/ 从右向左搜索-
10、high; Rlow = Rhigh;QT=QT+1;while (lowhigh & Rlow=pivotkey)/ 从左向右搜索+ low; Rhigh = Rlow;QT=QT+1;Rlow =R0; QT=QT+1;return low;/ Partitionvoid quicksort (long R, int low, int high,long n,long y)/ 对记录序列L.rlow.high进行快速排序if (low high) / 长度大于1 long pivotloc = Partition(R,low,high,n);/ 对 L.rlow.high 进行一次划分QT
11、=QT+1;cout第y趟:;y+;print(R,pivotloc-1);coutsetw(5)Rpivotloc;cout;for(long x=pivotloc+1;x=n;x+)coutsetw(5)Rx;coutendl;quicksort(R, low, pivotloc-1,n,y); / 对低子序列递归排序quicksort(R, pivotloc+1, high,n,y); / 对高子序列递归排序 / QSortvoid QuickSort(long R,long n) long y=1;quicksort(R,1,n,n,y);/-/操作选择函数/-void operate
12、(long a, long n)void main();long * R = new long n;time_t start, end;/定义两个变量double Time;/排序时间long degree;/排序次数char ch;cout ch;switch(ch)case 1:coutn;coutt=您选择的是冒泡排序=n;for(int i = 1; i =n; i +)/将随机数付给RiRi = ai;start=(double)clock();degree = Bubblesort(R, n);end=(double)clock();Time = (double)(end-star
13、t)/CLK_TCK;/print(R,n);cout n;cout 冒泡排序所用时间：t Time n;cout 冒泡排序交换次数：t degree n;coutn;operate(a, n);break;case 2:coutn;coutt=您选择的是选择排序=n;for(int i = 1; i = n; i +)Ri = ai;start=(double)clock();degree = selectsort(R, n);end=(double)clock();Time = (double)(end-start)/CLK_TCK;/print(R,n);coutn;cout 选择排序所
14、用时间：t Time n;cout 选择排序交换次数：t degree n;cout n;operate(a, n);break;case 3:coutn;coutt=您选择的是直接插入排序=n;for(int i=1; i=n; i +)Ri = ai;start=(double)clock();degree = insertsort(R, n);end=(double)clock();Time = (double)(end-start)/CLK_TCK;/print(R,n);coutn;cout 直接插入排序所用时间： Time n;cout 直接插入排序交换次数： degree n;c
15、out n;operate(a, n);break;case 4:coutn;coutt=您选择的是快速排序=n;for(int i=1; i=n; i +)Ri = ai;start=(double)clock();QuickSort(R, n);end=(double)clock();Time = (double)(end-start)/CLK_TCK;coutn;cout 快速排序所用时间：t Time n;cout 快速排序交换次数：t QT n;待添加的隐藏文字内容3cout n;operate(a, n);break;case 0:cout您已选择退出程序，谢谢使用n;break;
16、case a:main();break;default:cout 输入错误，请选择正确的操作！ n;operate(a, n);break;/-/导航菜单函数/-void DaoHang()coutn* 排序算法比较 *endl; cout*endl; cout= 1 - 冒泡排序 =endl; cout= 2 - 选择排序 =endl;cout= 3 - 直接插入排序 =endl;cout= 4 - 快速排序 =endl; cout= 0 - 退出程序 =endl;cout= a - 改变随机数的个数 =endl; cout*endl;/-/随机输入函数/-void Rand()cout n
17、请输入要产生的随机数的个数（0=n=100000000）： n;cout endl;long *a = new long n;srand(unsigned long)time(NULL);/产生一个以当前时间开始的随机种子for (long i=1; i=n; i+)ai = rand() % n;/n为最大值,其随机域为0n-1 DaoHang();print(a,n);operate(a, n);/-/手动输入函数/-void HandInput()cout请输入数据个数：endl;int n;coutn;cout endl;long *a = new long n;for (long i
18、=1; iai ;DaoHang();operate(a, n);/-/主函数/-void main()loop:cout手动输入请按 1 ，随机输入请按 2 x;switch(x)case 2:Rand();case 1:HandInput();default:cout输入错误,请重新输入!endl;goto loop;输出结果1.8得意之处：重点介绍整个课程设计程序中自已认为最满意、最得意的地方 （1）、定义全局变量用于返回比较次数。 （2）、快速排序：快速排序是对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小
19、，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 （3）、假设待排序的序列为R s,R s+1,Rt，首先任意选取一个记录（通常可选第一个记录Rs）作为枢轴（或支点），然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较它大的记录都安置在它的位置之后。由此可见，该“枢轴”为分界线，将序列分割成两个子序列。这个过程称做一趟快速排序（或一次划分）。 （4）、一趟快速排序的具体做法是：附设两个指针left和right，它们的初值分别为left和right，高枢轴记录的关键字为temp，则首先从right所指位置起向前搜索找到第一个关键字小于temp的
20、记录和枢轴记录互相交换，然后从left所指位置起向后搜索，找到第一个关键字大于temp的记录和枢轴记录互相交换，重复这两步直至left=right为止。1.9创意的技术实现：介绍课程设计中重点创意的技术实现技巧、核心程序等；1) 直接插入排序：插入排序的基本思想是：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。简言之：边插入边排序，保证子序列中随时都是有序的。直接插入排序是一种最简单的排序方法,它的基本操作是将一个记录插入到已经排好的有序表中，从而得到一个新的、记录数增1的有序表。2)快速排序：快速排序是对起泡排序的一种改进。它的基本
21、思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序的序列为Rs,Rs+1,Rt，首先任意选取一个记录（通常可选第一个记录Rs）作为枢轴（或支点），然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较它大的记录都安置在它的位置之后。由此可见，该“枢轴”为分界线，将序列分割成两个子序列。这个过程称做一趟快速排序（或一次划分）。 一趟快速排序的具体做法是：附设两个指针left和right，它们的初值分别为left和right，高枢轴记录的关键字
22、为temp，则首先从right所指位置起向前搜索找到第一个关键字小于temp的记录和枢轴记录互相交换，然后从left所指位置起向后搜索，找到第一个关键字大于temp的记录和枢轴记录互相交换，重复这两步直至left=right为止。3)简单选择排序：选择排序基本思想：在待排的n-i+1个记录中，依次选择关键字最小的记录作为有序序列的第i条记录，逐渐缩小范围直至你全部记录选择完毕。一趟简单排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1in)个记录交换之。显然，对R1n中记录进行简单选择排序的算法为：令i从1至n-1，进行n-1趟选择操作。4)冒泡排
23、序：两两比较待排序列关键字，如果发生逆序，则交换之，直到所有记录都排好有序为止。如：第一趟将关键字最大值对应元素放到第n个位置。5)定义全局变量用于返回比较次数。1.10课程设计中目前存在的问题设计中发现函数返回只能有一个值，但要求输出比较次数与交换次数。本想函数返回交换次数，在函数中直接统计并打印出比较次数。但快速排序因为要递归调用本身，所以，调用一次比较次数就输出一次，但我们只要最后一次的数据。请教老师后定义为比较次数为全局变量，然后在输出，问题迎刃而解1.11设计实践过程中的自我感受:通过该课程设计的操作与实践，训练我们灵活应用所学知识，独立完成对算法的理解、分析、掌握，并编程实现算法全过程的综合实践能力。巩固、深化我们的理论知识，掌握排序算法的主要思想，提高对排序算法的正确分析的能力。更好的掌握应用递归思想。巩固应用递归思想，提高分析能力。集体的力量是很大的，要团结一致，在遇到解决不了的问题时要向老师，同学请教，而且要学会多到图书管或者上网查阅资料来解决所遇到的问题。1.12主要参考资料： （1）、严蔚敏等，数据结构，清华大学出版社，北京.2000 （2）、谭浩强，C语言程序设计，清华大学出版社，北京.
