数据结构课程设计_排序算法比较【完整版】.doc

数据结构课程设计排序算法比较 XXXXXX大学数据结构课程设计报告目 录排序算法比较1、 需求分析2、 程序的主要功能3、 程序运行平台4、 数据结构5、 算法及时间复杂度6、 测试用例7、 程序源代码二 感想体会与总结排序算法比较一、需求分析利用随机函数产生N个随机整数（N = 500，1000，1500，2000，2500，,30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（统计为图表坐标形式）。二、程序的主要功能1.用户输入任意个数，产生相应的随机数2.用户可以自己选择排序方式（直接插入排序、折半插入排序、起泡排序、快速排序、选择排序、堆排序、基数排序）的一种3.程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间。三、程序运行平台Visual C+ 6.0版本四、数据结构本程序的数据结构为线形表，线性顺序表、线性链表。1、结构体： typedef struct int *r; /r指向线形表的第一个结点。 r0闲置，不同的算法有不同的用处，如用作哨兵等。 int length; /顺序表的总长度Sqlist;2、空线性表Status InitSqlist(Sqlist &L)L.r=(int *)malloc(MAXSIZE*sizeof(int); /分配存储空间if(!L.r) printf(存储分配失败！);exit(0); /存储分配失败L.length=0;/初始长度为0return OK;五、算法及时间复杂度（一）各个排序是算法思想：（1）直接插入排序：将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表。（2）折半插入排序：插入排序的基本插入是在一个有序表中进行查找和插入，这个查找可利用折半查找来实现，即为折半插入排序。（3）起泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。（4）快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。（5）选择排序：通过N-I次关键字间的比较，从N-I+1个记录中选出关键字最小的记录，并和第I（1=I=N）个记录交换。（6）堆排序：在堆排序的算法中先建一个大顶堆，既先选得一个关键字作为最大的记录并与序列中最后一个记录交换，然后对序列中前N-1记录进行选择，重新将它调整成一个大顶堆，如此反复直到排序结束。（7）基数排序：按最低位优先法先对低位关键字进行排序，直到对最高位关键字排序为止，经过若干次分配和收集来实现排序（二）时间复杂度分析排序算法 最差时间时间复杂度 是否稳定？插入排序 O(n2)O(n2) 稳定 冒泡排序O(n2)O(n2) 稳定 快速排序O(n2)O(n*log2n) 不稳定 选择排序O(n2)O(n2) 稳定 堆排序O(n*log2n) O(n*log2n) 不稳定 基数排序O(n*log2n)O(n2)稳定10000个数据的时间比较：算法名称用时直接插入排序0.25折半插入排序0.219起泡排序0.704快速排序0.016选择排序0.39堆排序0.0001基数排序0.016六、测试用例1、首先选择需要排序的数字个数，比如输入5000。2、系统显示出随机产生的随机数。 用户选择排序方式，比如选择1.直接插入排序3、 系统将随机数排序后整齐的显示出来。4、 用户可以选择继续排序或者退出系统。七、程序源代码/*第六题：排序算法比较设计要求：利用随机函数产生N个随机整数（N = 500，1000，1500，2000，2500，,30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、|选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（统计为图表坐标形式）。*/#include stdio.h#include stdlib.h#include time.h/计时#define ERROR 0#define OK 1#define OVERFLOW -2#define MAXSIZE /用户自己规定排序的数字的长度typedef int Status;typedef struct int *r; / r0闲置 int length; /顺序表的总长度Sqlist;/构造一个空线性表Status InitSqlist(Sqlist &L)L.r=(int *)malloc(MAXSIZE*sizeof(int); /分配存储空间if(!L.r) printf(存储分配失败！);exit(0); /存储分配失败L.length=0;/初始长度为0return OK;/输入随机数并显示在界面上Status ScanfSqlist(int &N,Sqlist &L)int i;printf(请输入要排序的元素个数N: );scanf(%d,&N);for(i=1;i=N;i+)L.ri=rand(); /随机产生样本整数printf(nn);printf( 随机产生了%d个随机数，它们是：n,N);for(i=1;i=N;i+)printf(%7.2d ,L.ri);printf(n);L.length=N; /存储线性表的长度return OK;/输出排序之后的数据Status PrintfSqlist(int N,Sqlist L)int i;printf(数据个数：);/输出数据个数printf(%dn,L.length);printf(排序后的数据：(从左向右依次增大)n);/输出数据for(i=1;i=N;i+)printf(%7.2d ,L.ri);printf(n); return OK;/*/ 直接插入排序/*Status InsertSort(Sqlist &L)/参考书P265算法10.1int i,j;if(L.length=0)printf(要排序的数据为空！);return ERROR;for(i=2;i=L.length;i+)if(L.riL.ri-1) /将L.ri插入有序子表L.r0=L.ri; /复制为监视哨L.ri=L.ri-1; for(j=i-2;L.r0L.rj;j-)L.rj+1=L.rj; /记录后移L.rj+1=L.r0; /插入到正确位置return OK;/*/ 折半插入排序/*Status BInsertSort(Sqlist &L) /参考书P267算法10.2int i,j,mid,low,high;if(L.length=0)printf(要排序的数据为空！);return ERROR;for(i=2;i=L.length;i+)L.r0=L.ri; /将L.ri暂存在L.r0low=1;high=i-1;while(low=high) /在rlow.high中折半查找有序插入的位置mid=(low+high)/2;if(L.r0=high+1;j-) /插入点后的数据后移L.rj+1=L.rj; L.rhigh+1=L.r0; /将数据插入/forreturn OK;/* 希尔排序*/ /参考书P272算法10.4及10.5/*Status ShellInsert(Sqlist &L,int dk)/希尔插入排序 int i,j;/前后位置的增量是dkfor(i=dk+1;i=L.length;i+)/r0只是暂存单元，不是哨兵，if(L.ri0 & L.r0L.rj;j-=dk)L.rj+dk=L.rj;/记录后移,查找插入位置L.rj+dk=L.r0;/插入return OK;Status ShellSort(Sqlist &L,int dlta5,int t) /希尔排序 int i;if(L.length=0)printf(要排序的数据为空！);return ERROR;for(i=0;it;i+)ShellInsert(L,dltai);/一趟增量为dltak的插入排序return OK;*/*/ 起泡排序/*Status BubbleSort(Sqlist &L)int i,j,t;if(L.length=0)printf(要排序的数据为空！);return ERROR;for(i=1;i=L.length-1;i+)for(j=1;jL.rj+1) /前面的数据后面数据时t=L.rj+1;L.rj+1=L.rj;L.rj=t; /将元素交换return OK;/*/ 快速排序/*int Partition(Sqlist &L, int low, int high) /交换顺序表中子表L.rlow.high的记录，使得枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大于它int pivotkey; /记录关键字L.r0=L.rlow; /用子表的第一个纪录作枢轴纪录 pivotkey=L.rlow; /用枢轴纪录关键字 while (lowhigh) while(low=pivotkey) high-;L.rlow= L.rhigh; /将比枢轴记录小的记录移到低端while(lowhigh & L.rlow=pivotkey) low+;L.rhigh=L.rlow; /将比枢轴记录大的数移到高端 L.rlow=L.r0; /枢轴记录到位 return low;/Partition函数void Qsort (Sqlist &L,int low, int high) int pivotloc;if (lowhigh) /长度大于1，可以进行 pivotloc=Partition(L, low ,high);Qsort(L,low,pivotloc-1); /对低子表递归排序，pivotloc是枢轴位置Qsort(L,pivotloc+1,high); /对高子表递归排序/Qsort函数Status QuickSort (Sqlist &L) if(L.length=0)printf(要排序的数据为空！);return ERROR;Qsort(L,1,L.length);return OK;/QuickSort/*/ 选择排序/*Status ChooseSort(Sqlist &L)int i,j,k,t;if(L.length=0)printf(没有数据！);return ERROR;for(i=1;i=L.length;i+) /排序的趟数k=i;for(j=i+1;j=L.length;j+) /比较第i个元素以及其后的数据中最小的 if(L.rjL.rk)k=j;if(i!=j) /将最小数据赋值给L.rit=L.ri;L.ri=L.rk;L.rk=t;return OK;/*/ 堆排序/*Status HeapAdjust(Sqlist &L,int s,int m) /调整L.rs的关键字,使L.rsm成大顶堆int i;L.r0=L.rs;for(i=2*s;i+1=m;i*=2) /沿数据较大的孩子结点向下筛选if(im & L.ri=L.ri) /L.r0插入在S位置上break;L.rs=L.ri;s=i;L.rs=L.r0; /插入新数据 return OK;Status HeapSort(Sqlist &L) /堆排序int i,t;if(L.length=0)printf(没有数据！);return ERROR;for(i=L.length/2;i0;i-)HeapAdjust(L,i,L.length);for(i=L.length;i1;i-)t=L.r1; /将堆顶记录和当前未经排序的子序列L.r1.i中最后一个记录互换L.r1=L.ri;L.ri=t;HeapAdjust(L,1,i-1); /将L.r1.i-1重新调整为大顶堆return OK;/*/ 基数排序/*typedef struct node int key; node *next; RecType; Status RadixSort(Sqlist L) int t,i,j,k,d,n=1,m; RecType *p,*s,*q,*head10,*tail10; /定义各链队的首尾指针 for(i=1;ikey=L.ri; if(i=1) /当为第一个元素时 q=s; p=s; t+; else q-next=s; /将链表连接起来q=s; t+; q-next=NULL; d=1;while(n0) /将每个元素分配至各个链队for(j=0;jkey/d; k=k%10; if(headk=NULL) /进行分配 headk=p; tailk=p; else tailk-next=p; tailk=p; p=p-next; /取下一个待排序的元素 p=NULL; /用于收集第一个元素时的判断for(j=0;jnext=headj; q=tailj; q-next=NULL; /最后一个结点的next置为空 d=d*10; n=0;m=1;while(mkey; i+; p=p-next;return OK;/*/ 主函数/*void main()Sqlist L;Sqlist L0;InitSqlist(L); /初始化LInitSqlist(L0); int m,i; char choice=z;clock_t start, finish; /定义clock_t用于计时double duration; /向L中输入元素printf(n n);printf( n);printf( 算法排序比较系统 n);printf( n);printf( n); printf( 以下是各个排序算法的代号：nn);printf( 1、直接插入排序 n);printf( 2、折半插入排序 n);printf( 3、起泡排序 n);printf( 4、快速排序n);printf( 5、选择排序n);printf( 6、堆排序n);printf( 7、基数排序n); printf( 8、退出该系统nn);ScanfSqlist(m,L0);printf(n);printf( 1、直接插入排序 n);printf( 2、折半插入排序 n);printf( 3、起泡排序 n);printf( 4、快速排序n);printf( 5、选择排序n);printf( 6、堆排序n);printf( 7、基数排序n); printf( 8、退出该系统nn);printf(n请选择排序的方式,数字1-7: );scanf(%d,&choice); /选择排序方式赋值choice，用于后面的函数选择while(choice8)printf(输入方式有误。n请输入1-7选择排序方式，或者选择8退出系统);scanf(%d,&choice);while(choice!=8)for(i=1;i=L0.length;i+)L.ri=L0.ri;L.length=L0.length;switch(choice)case 1:/直接插入排序start = clock(); InsertSort(L);finish = clock();break;case 2:/折半插入排序start = clock();BInsertSort(L); finish = clock(); break;case 3:/起泡排序start = clock();BubbleSort(L);finish = clock(); break;case 4:/快速排序start = clock();QuickSort(L); finish = clock(); break;case 5:/选择排序start = clock();ChooseSort(L);finish = clock(); break;case 6:/堆排序start = clock();HeapSort(L);finish = clock(); break;case 7:/基数排序start = clock();RadixSort(L);finish = clock(); break;case 8:/直接退出break;PrintfSqlist(m,L); /输出数据和L的长度duration = (double)(finish - start) / CLOCKS_PER_SEC; /输出算术时间printf(n本次排序运算所用的时间是：%lf secondsn,duration); printf( 本次排序结束。n);printf( _n); printf( 继续本系统吗？nn); printf( 以下是各个排序算法的代号：n); printf( 1、直接插入排序n); printf( 2、折半插入排序n); printf( 3、起泡排序n); printf( 4、快速排序n); printf( 5、选择排序n); printf( 6、堆排序n); printf( 7、基数排序n); printf( 8、退出该系统n);printf(n请请输入1-7选择排序方式，或者选择8退出系统:);scanf(%d,&choice);while(choice8)printf(输入方式有误。n请输入1-7选择排序方式，或者选择8退出系统);scanf(%d,&choice);感想体会与总结好的算法编程技巧高效率好的程序。1、 做什么都需要耐心，做设计写程序更需要耐心。一开始的时候，我写函数写的很快，可是等最后调试的时候发现错误很隐蔽，就很费时间了。后来我先在纸上构思出函数的功能和参数，考虑好接口之后才动手编，这样就比较容易成功了。2、 做任何事情我决定都应该有个总体规划。之后的工作按照规划逐步展开完成。对于一个完整的程序设计，首先需要总体规划写程序的步骤，分块写分函数写，然后写完一部分马上纠错调试。而不是像我第一个程序，一口气写完，然后再花几倍的时间调试。一步步来，走好一步再走下一步。写程序是这样，做项目是这样，过我们的生活更是应该这样。3、 感觉一开始设计结构写函数体现的是数据结构的思想，后面的调试则更加体现了人的综合素质，专业知识、坚定耐心、锲而不舍，真的缺一不可啊。4、 通过这次课设，不仅仅复习了C语言相关知识、巩固了数据结构关于栈和排序的算法等知识，更磨练了我的意志。在平时的测量工作中，他积极做好传、帮、带工作，热心地把自己学到和掌握好的操作技艺毫无保留地传授给徒弟and actual case whether match; by is located land right nature; property status, whether has damage or quality problem; property using situation, rental or use; reference around similar property price, judge assessment value of rationality; whether exists property disputes, and seized, and freeze, and mortgage, and demolition, and transformation, limit situation. 2. to land right mortgage of, survey people should verified following information: land right card by contains Ming information (right people, and location, and nature, and term, and area,) and actual case whether match; land nature; land flat situation; ground buildings situation; reference around similar land price, judge assessment value of rationality; mortgage real whether has other mortgage right or notice registration established prior; whether exists property disputes, and seized, and freeze, and mortgage, limit situation. 3. other chattels, ownership, the value of the mortgage should be implemented, and whether factors such as easy handling. (C) pledge of collateral i