《排序算法比较课程设计》由会员分享，可在线阅读，更多相关《排序算法比较课程设计（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)/ 从右向左搜索- 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
