排序算法比较课程设计.doc

数据结构课程设计排序算法的比较专 业： 计算机科学与技术 班级学号： 学生姓名： 系 别： 信息技术工程学院指导教师： 时 间： 1.1题目排序算法的比较1.2 课题来源课程组自拟1.3课题类型： 综合型1.4 目的意义： 通过该课程设计的操作与实践，使学生真正掌握数据结构相关算法的实现及应用方法，在一定程度上提高使用数据结构相关算法的综合设计能力，具体掌握的基本能力如下：（1）、使学生能够综合运用所学知识，解决实际问题。培养学生对整体课程知识综合运用和融会贯通的能力。（2）、掌握各种排序算法（直接插入排序、冒泡排序、快速排序、简单选择排序）的思路核心，比较他们之间的优劣 （3）、培养学生分析、解决问题和编程等实际动手能力。1.5基本要求：（1）、 任意性：系统首先生成1000个随机整数，然后分别用不同的排序方法对其进行升序排序，给出每种方法的比较次数或所用时间。（2）、友好性：界面要友好，输入有提示，尽量展示人性化。（3）、可读性：源程序代码清晰、有层次。 (4)健壮性：用户输入非法数据时，系统要及时给出警告信息。 1.6使用的各种工具软件和工作环境:工作环境：第一教学楼四楼实验室五机房。运行环境：microsoft visual c+6.01.7设计内容简介：包括课程设计的基本结构流程、运行环境等（1）、课程设计的基本结构流程头文件：#include stdlib.h/包括两函数srand()和rand来设置随机种子以生随机数#include time.h/时钟static long qc2=0, bc2=0,sc2=0,ic2=0;/定义全局变量用于输出比较次数主函数：void main产生n个随机数、定义数组并且调用操作函数。操作函数void operate：可选择四种排序算法中的任意一种，调用此排序函数并且输出排序所有时间、排序交换次数和排序比较次数。冒泡排序函数bubblesort：通过无序区中相邻记录关键字值间的比较和位置的交换，使关键字最小的记录如“气泡”一样逐渐漂浮到水面。过程：首先将一第n个记录的关键字和第n-1个记录关键字进行比较，若为逆序，则将两个记录交换之，然后比较倒数第n-2和倒数n-3记录的关键字。依次类推，直至第2个记录和第1个记录的关键字进行过比较为止。上述过程称做第一趟起泡排序，其结果使得关键字最小的记录被安置到第一个记录的位置上。然后进行第二趟起泡排序，对后n-1个记录进行同样操作，其结果是使关键字次小的记录被安置到第i个记录的位置上。简单选择排序函数selectsort： 每趟从待排序列中选取一个关键字值最小的记录，用m记录其最小数的位置，然后判断其位置是否放在第i个位置，如果不与第i个位置相同则交换，依次判断次小关键字位置，顺序放在已排序的记录的最后。直接插入排序函数insertsort：每次将一个待排序的记录，按其关键字值的大小插入到已经排序部分的文件中的适当位置上，直到全部插入完成。快速排序函数quicksort：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。流程图 开始选择方式手动随机调用程序选择排序方式 冒泡选择直接插入快速输出结果结束程序源代码：#include #include#include #include #include #define max 1000using namespace std;void print(long r,long n)for(int i=1;i=n;i+)coutsetw(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;/-/选择排序/-/static 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;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=r0;/插入到正确位置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 long pivotloc = partition(r,low,high,n);/ 对 l.rlow.high 进行一次划分qt=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(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-start)/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 选择排序所用时间：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;cout 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;cout n;operate(a, n);break;case 0:cout您已选择退出程序，谢谢使用n;break;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请输入要产生的随机数的个数（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=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）、快速排序：快速排序是对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 （3）、假设待排序的序列为r s,r s+1,rt，首先任意选取一个记录（通常可选第一个记录rs）作为枢轴（或支点），然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较它大的记录都安置在它的位置之后。由此可见，该“枢轴”为分界线，将序列分割成两个子序列。这个过程称做一趟快速排序（或一次划分）。 （4）、一趟快速排序的具体做法是：附设两个指针left和right，它们的初值分别为left和right，高枢轴记录的关键字为temp，则首先从right所指位置起向前搜索找到第一个关键字小于temp的记录和枢轴记录互相交换，然后从left所指位置起向后搜索，找到第一个关键字大于temp的记录和枢轴记录互相交换，重复这两步直至left=right为止。1.9创意的技术实现：介绍课程设计中重点创意的技术实现技巧、核心程序等；1) 直接插入排序：插入排序的基本思想是：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。简言之：边插入边排序，保证子序列中随时都是有序的。直接插入排序是一种最简单的排序方法,它的基本操作是将一个记录插入到已经排好的有序表中，从而得到一个新的、记录数增1的有序表。2)快速排序：快速排序是对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序的序列为rs,rs+1,rt，首先任意选取一个记录（通常可选第一个记录rs）作为枢轴（或支点），然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较它大的记录都安置在它的位置之后。由此可见，该“枢轴”为分界线，将序列分割成两个子序列。这个过程称做一趟快速排序（或一次划分）。 一趟快速排序的具体做法是：附设两个指针left和right，它们的初值分别为left和right，高枢轴记录的关键字为temp，则首先从right所指位置起向前搜索找到第一个关键字小于temp的记录和枢轴记录互相交换，然后从left所指位置起向后搜索，找到第一个关键字大于temp的记录和枢轴记录互相交换，重复这两步直至lef