数据结构与算法课程设计排序毕业论文.doc

计算机科学与技术专业数据结构与算法课程设计报告题 目 作 者 指导教师 2013年1月13日摘 要本组课程设计选择了数据排序这一题目。程序通过使用C语言的算法，用直接插入，直接选择，冒泡，快速排序算法实现主菜单设计。通过此程序可快速将任一组数据进行排序。目 录一、 概述 5二、 数据结构设计 6三、 算法设计 7四、 源代码说明 11五、 结果与分析 19图表目录l 图一：手动输入程序运行结果 24l 图二：随机输入程序运行结果 24l 图三：冒泡排序 25l 图四：选择排序 25l 图五：直接插入排序 25l 图六 快速排序 26l 图七：改变随机数的个数显示 26l 图八：退出显示 26l 表一：算法效率分析结果 26 概述1. 问题描述设计一个程序，对的任一组数据完成排序:用直接插入，直接选择，冒泡，快速排序法并实现主菜单设计。2. 分析排序就是将一组任一组数据，根据某一个（几个）关键字按照一定顺序重新排序，使之成为一组有序的序列。直接插入排序，直接选择排序，冒泡排序，快速排序均属于内部排序。题目要求是用直接插入，直接选择，冒泡，快速排序法，实现主菜单设计。即程序运行时通过菜单提示进行算法的选择，并通过此算法对任一组数据进行排序。直接插入排序：待排序的记录放在数组R0n-1中排序过程中某一时刻，R被划分成两个子区间R0i-1 (有序和)Rin-1(无序)。直接插入的基本操作是将当前无序区的一个记录Ri插入到有序区R0i-1中适当的位置。直接选择排序：基本思想：在待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止。冒泡排序：相邻的两个元素进行比较，将小的调到前面，大的调到后面。快速排序：在待排序的数组的n个元素中取一个元素(一般取第一个)，将其移动到这样的位置：在其之前的元素的值都小于它，在其之后的元素都大于它，这样是一趟快速排序；然后对数组的两个部分进行同样的操作，直到每部分只有一个记录为止；总之，每趟使表的第一个元素放在适当位置，将表两分，再对两子表进行同样的递归划分，直至划分的子表长度为1。二、数据结构设计1. 数据结构设计考虑此程序中四种排序算法均运用数组2. 逻辑结构与物理（存储）结构本程序包含了7个主要函数（1）直接插入排序的算法函数 InsertSort（）（2）选择排序算法函数SelectSort（）（3）冒泡排序算法函数BubbleSort（）（4）快速排序的算法函数Partition（）（5）选择函数：void operate(long a, long n)（6）导航菜单函数void DaoHang()（7）主函数 main（） 三、算法设计1. 主要设计思想 本程序从整体上分为7大模块： （1） 直接插入排序的算法函数 InsertSort（）（2）选择排序算法函数SelectSort（）（3）冒泡排序算法函数BubbleSort（）（4）快速排序的算法函数Partition（）（5）选择函数：void operate(long a, long n)（6）导航菜单函数void DaoHang()（7）主函数 main（） 2. 算法的伪码描述冒泡排序算法： long Bubblesort(long R, long n)long y=1;long i,BT=0;i=n;while(i1)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;选择排序：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);if (i!=j)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;快速排序：void quicksort (long R, int low, int high,long n,long y)if (low high) long pivotloc = Partition(R,low,high,n);QT=QT+1;cout第y趟:;y+;print(R,pivotloc-1);coutsetw(2)Rpivotloc;cout;for(long x=pivotloc+1;x=n;x+)coutsetw(5)Rx;cout1)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(2)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 a:main();break;default:cout 输入错误，请选择正确的操作！ n;operate(a, n);break;case 0:cout您已选择退出程序，谢谢使用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();break; case 1:HandInput();break; default:cout输入错误,请重新输入!endl;goto loop;五、结果与讨论以下是选择手动输入数据的程序运行结果：图一：以下为选择随机输入数据的程序运行结果：图二：（1） 以下为选择“1-冒泡排序”的运行结果图三：（2） 以下为选择“2-选择排序”的运行结果图四：（3） 以下为选择“3-直接插入排序”的运行结果图五：（4） 以下为选择“4-快速排序”的运行结果图六：以下为选择“a-改变随机数的个数”的程序运行结果：图七：以下为退出时的显示结果：图八：1. 程序按照预先设计思路运行正确。表格1： 算法比较排序方法所用时间交换次数冒泡0.0611选择0.0463直接插入0.0419快速0.031322.程序除了将数据排序，同时也给出了各算法的排序时间和交换次数。便于比较不同排序方法的效率。下期将要改进的地方是编入二分排序和堆排序算法。 附 录#include #include#include #include #include #define MAX 100000000using 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(2)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;cou