数据结构课程设计_排序算法比较.docx

数据构造课程设计排序算法比较XXXXXX 大学数据构造课程设计报告第 3 页 共 20 页目 录排序算法比较一、需求分析二、程序的主要功能三、程序运行平台 四、数据构造五、算法准时间简单度六、测试用例七、程序源代码二 感想体会与总结一、需求分析排序算法比较利用随机函数产生N 个随机整数N = 500，1000，1500，2023， 2500，,30000，利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法可添加其它排序方 法进展排序结果为由小到大的挨次，并统计每一种排序所消耗的时间统计为图表坐标形式。二、程序的主要功能1. 用户输入任意个数，产生相应的随机数2. 用户可以自己选择排序方式直接插入排序、折半插入排序、起泡排序、快速排序、选择排序、堆排序、基数排序的一种3. 程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间。三、程序运行平台Visual C+6.0 版本四、数据构造本程序的数据构造为线形表，线性挨次表、线性链表。1、构造体： typedef structint*r; /r 指向线形表的第一个结点。 r0闲置，不同的算法有不同的用处，如用作哨兵等。intlength; /挨次表的总长度Sqlist;2、空线性表Status InitSqlist(Sqlist &L)L.r=(int *)malloc(MAXSIZE*sizeof(int);/安排存储空间if(!L.r)printf(“存储安排失败！“); exit(0); /存储安排失败L.length=0;/初始长度为 0 return OK;五、算法准时间简单度一各个排序是算法思想：（1） 直接插入排序：将一个记录插入到已排好的有序表中，从而得到一个的，记录数增加 1 的有序表。（2） 折半插入排序：插入排序的根本插入是在一个有序表中进展查找和插入，这个查找可利用折半查找来实现，即为折半插入排序。（3） 起泡排序：首先将第一个记录的关键字和其次个记录的关键字进展比较，假设为逆序，则将两个记录交换，然后比较其次个记录和第三个记录的关键字。依此类推，直到第N-1 和第N 个记录的关键字进展过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最终一个记录的位置上。然后进展其次趟起泡排序，对前N-1 个记录进展同样操作。一共要进展N-1 趟起泡排序。（4） 快速排序：通过一趟排序将待排记录分割成独立的两局部，其中一局部记录的关键字均比另一局部记录的关键字小，则可分别对这两局部记录连续进展排序，已到达整个序列有序。（5） 选择排序：通过N-I 次关键字间的比较，从N-I+1 个记录中选出关键字最小的记录，并和第I1<=I<=N个记录交换。（6） 堆排序：在堆排序的算法中先建一个大顶堆，既先选得一个关键字作为最大的记录并与序列中最终一个记录交换，然后对序列中前N-1 记录进展选择，重将它调整成一个大顶堆，如此反复直到排序完毕。（7） 基数排序：按最低位优先法先对低位关键字进展排序，直到对最高位关键字排序为止，经过假设干次安排和收集来实现排序排序算法最差时间时间简单度是否稳定？插入排序O(n2)O(n2)稳定冒泡排序O(n2)O(n2)稳定二时间简单度分析数据构造课程设计排序算法比较快速排序O(n2)O(n*log n)2不稳定选择排序堆排序O(n2)O(n*log n)O(n2)O(n*log n)稳定不稳定22基数排序O(n*log n)O(n2)稳定210000 个数据的时间比较：算法名称 直接插入排序折半插入排序起泡排序快速排序选择排序堆排序 基数排序用时0.250.2190.7040.0160.390.00010.016六、测试用例1、首先选择需要排序的数字个数，比方输入 5000。第 5 页 共 20 页数据构造课程设计排序算法比较2、系统显示出随机产生的随机数。用户选择排序方式，比方选择 1.直接插入排序第 6 页 共 20 页数据构造课程设计排序算法比较3、系统将随机数排序后整齐的显示出来。4、用户可以选择连续排序或者退出系统。七、程序源代码/*第六题：排序算法比较设计要求：利用随机函数产生N 个随机整数N = 500，1000，1500，2023， 2500，,30000，第 7 页 共 20 页数据构造课程设计排序算法比较利用直接插入排序、折半插入排序，起泡排序、快速排序、|选择排序、堆排序，基数排序七 种排序方法可添加其它排序方法进展排序结果为由小到大的挨次，并统计每一种排序所消耗的时间统计为图表坐标形式。*/ #include “stdio.h“#include “stdlib.h“#include “time.h“/计时#define ERROR 0#define OK 1#define OVERFLOW -2#define MAXSIZE 100000 /用户自己规定排序的数字的长度typedef int Status;typedef structint*r; / r0闲置intlength; /挨次表的总长度Sqlist;/构造一个空线性表Status InitSqlist(Sqlist &L)L.r=(int *)malloc(MAXSIZE*sizeof(int);/安排存储空间if(!L.r)printf(“存储安排失败！“); exit(0); /存储安排失败L.length=0;/初始长度为 0 return OK;/输入随机数并显示在界面上 Status ScanfSqlist(int &N,Sqlist &L)int i;printf(“请输入要排序的元素个数N: “); scanf(“%d“,&N);for(i=1;i<=N;i+)L.ri=rand; /随机产生样本整数第 10 页 共 20 页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.ri<L.ri-1)/将 L.ri插入有序子表L.r0=L.ri;/复制为监视哨L.ri=L.ri-1;for(j=i-2;L.r0<L.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.r0 low=1;high=i-1;while(low<=high)/在 rlow.high中折半查找有序插入的位置mid=(low+high)/2;if(L.r0<L.rmid)/插入点在低半区/whileelsehigh=mid-1;low=mid+1;/插入点在高半区for(j=i-1;j>=high+1;j-)/插入点后的数据后移L.rj+1=L.rj;L.rhigh+1=L.r0;/将数据插入/for return OK;/*希尔排序*/法 10.4 及 10.5/*Status ShellInsert(Sqlist &L,int dk)/希尔插入排序/参考书P272 算int i,j;/前后位置的增量是dkfor(i=dk+1;i<=L.length;i+)/r0只是暂存单元，不是哨兵，if(L.ri<L.ri-dk)/将 L.ri插入有序增量子表L.r0=L.ri;/暂存L.r0for(j=i-dk;j>0 && L.r0<L.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;i<t;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;j<=L.length-i;j+)if(L.rj>L.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 (low<high)while(low<high && L.rhigh>=pivotkey)high-;L.rlow= L.rhigh;/将比枢轴记录小的记录移到低端while(low<high && 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(low<high)/长度大于 1，可以进展/Qsort 函数pivotloc=Partition(L, low ,high);Qsort(L,low,pivotloc-1);/对低子表递归排序，pivotloc 是枢轴位置Qsort(L,pivotloc+1,high);/对高子表递归排序StatusQuickSort (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.rj<L.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(i<m && L.ri<L.ri+1)/i 为数据较大的记录下标i+;if(L.r0>=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;i>0;i-)HeapAdjust(L,i,L.length);for(i=L.length;i>1;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 nodeintkey; node *next;RecType;StatusRadixSort(Sqlist L)int t,i,j,k,d,n=1,m;RecType *p,*s,*q,*head10,*tail10;/定义各链队的首尾指针for(i=1;i<=L.length;i+)/将挨次表转化为链表s=(RecType*)malloc(sizeof(RecType); s->key=L.ri;if(i=1)/当为第一个元素时elseq=s; p=s; t+;q->next=s;/将链表连接起来q=s;t+; d=1;q->next=NULL;while(n>0)/将每个元素安排至各个链队for(j=0;j<10;j+)/初始化各链队首、尾指针headj = NULL; tailj = NULL;while(p!=NULL)/对于原链表中的每个结点循环k=p->key/d; k=k%10;if(headk=NULL)/进展安排elseheadk=p; tailk=p;tailk->next=p; tailk=p;p=p->next;/取下一个待排序的元素p=NULL;/用于收集第一个元素时的推断for(j=0;j<10;j+)/对每一个链队循环， 搜集每一个元素if(headj!=NULL)/进展搜集if(p=NULL)elsep=headj; q=tailj;q->next=headj; q=tailj;q->next=NULL;/最终一个结点的next 置为空d=d*10;n=0; m=1;while(m<=L.length)/推断当L 中的元素都除d 后是不是都为零了if(L.rm/d)!=0)i=1;elsen+; m+;m+;while(p!=NULL) /将链表转换为挨次表L.ri=p->key; i+;p=p->next;return OK;/*/主函数/* void mainSqlist L;Sqlist L0;InitSqlist(L);/初始化 L InitSqlist(L0);int m,i;char choice=”z”;clock_t start, finish; /定义clock_t 用于计时double duration;/向L 中输入元素n“);n“);n“);printf(“nn“); printf(“printf(“算法排序比较系统printf(“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(choice<1|choice>8)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(choice<1|choice>8)统“);printf(“输入方式有误。n 请输入 1-7 选择排序方式，或者选择 8 退出系scanf(“%d“,&choice);感想体会与总结好的算法编程技巧高效率好的程序。1、做什么都需要急躁，做设计写程序更需要急躁。一开头的时候， 我写函数写的很快，可是等最终调试的时候觉察错误很隐蔽，就很费时间了。后来我先在纸上构思出函数的功能和参数，考虑好接口之后才动手 编，这样就比较简洁成功了。2、做任何事情我打算都应当有个总体规划。之后的工作依据规划逐步开放完成。对于一个完整的程序设计，首先需要总体规划写程序的步 骤，分块写分函数写，然后写完一局部马上纠错调试。而不是像我第一个程序，一口气写完，然后再花几倍的时间调试。一步步来，走好一步再走下一步。写程序是这样，做工程是这样，过我们的生活更是应当这样。3、感觉一开头设计构造写函数表达的是数据构造的思想，后面的调试则更加表达了人的综合素养，专业学问、坚决急躁、锲而不舍，真的缺一不行啊。4、通过这次课设，不仅仅复习了C 语言相关学问、稳固了数据构造关于栈和排序的算法等学问，更磨练了我的意志。