数据结构实验报告-排序算法

实验五（快速、堆、基数）排序算法的设计一、实验目的和要求实验目的：1.深刻理解排序的定义和各种排序方法的特点，并能灵活运用。2.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。3.了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的性能的分析方法。实验要求：要求彻底弄懂排序的物理存储结构，并通过此试验为以后的现实使用打下基础。二、实验内容和原理：（1）实验内容：设计快速排序，堆排序和基数排序的算法。（2）实验原理：快速排序：在待排序的n个数据中，任取一个数据为基准，经过一次排序后以基准数据把全部数据分为两部分，所有数值比基准数小的都排在其前面，比它大的都排在其后，然后对这两部分分别重复这样的过程，直到全部到为为止。堆排序：对待排序的n个数据，依它们的值大小按堆的定义排成一个序列，从而输出堆顶的最小值数据（按最小值跟堆排序），然后对剩余的数据再次建堆，便得到次小的，如此反复进行输出和建堆，直到全部排成有序列。基数排序：LSD法：先按最低关键字位k1对待排序数据中的n个值进行排序，按k1值把待排序文件中的n个记录分配到具有不同k1值的若干个堆，然后按k1值从小到大的次序收集在一起，下次再按高一位关键子位k2的值进行分配和收集，如此不断地按更高一位关键字位进行分配和收集，直到用kn分配和收集之后，整个数据按多关键字位有序。三、实验环境硬件：（1）学生用微机；（2）多媒体实验教室；（3）局域网环境；软件：（1）WindowsXP中文操作系统；（2）TurboC3.0；四、算法描述及实验步骤描述:（1）快速排序:例：初始关键字3673659713ijj向左扫描后3673659713ijR[j]移入R[i]1373659736iji向右扫描1373659736ijR[i]移入R[j]后1336659773iji向左扫描1336659773iji向左扫描1336659773iji向左扫描1336659773iji=j第一次结束1次排序结束后13366597732次排序结束后13366597733次排序结束后1336657397（排序结束）堆排序：4333618272（初始状态）堆排序：例：初始值612111081．把数据建成堆，n＝5,就从第三个数据开始，3,2,1个数据筛选过程如下图：2．建立好了初始堆后，就要从最后一个元素开始，把第k个元素和根交换，然后把根筛选一次3．再从第--k个元素开始进行与跟交换这时，再进行筛选，直到所有的k=0时堆排序完毕。基数排序：分为两个部分，第一个分配位数，第二个收集。创建一个结构体数组用于分配时保存同一关键位的元素。个位数字为低关键字位，十位数字为高关键字位。关键字位值的范围为0—9，qu[i].f与qu[i].r为第i个队列的头指针和尾指针。将不qu[i].f不为空的链表相连，分个位和十位先后进行收集。直到所有的关键字位都被分配完毕，收集完成后退出。流程图:（1）快速排序:121011686121110861211108调用到的partition(i,j)函数:（2）堆排序:R[0]=R[i];R[i]=R[0];returni;当ij时反复做当R[j].key=R[0].key&&ij时反复做当R[i].key=R[0].key&&ij时反复做j--;count++;R[i]=R[j];i++;count++;R[j]=R[i];创建结构体数组:struct{intlow,high;}s[N0/2+1];inttop=0,i,j,k;s[++top].low=1;s[top].high=n;当top不为0时反复做i=s[top].low;j=s[top--].high;k=partition(i,j);s[++top].low=k+1;s[top].high=j;s[++top].low=i;s[top].high=k-1;k-1iyesnok+1jyesno调用到的函数sift(j,n):intk=2*i;R[0]=R[i];当k=m时反复做km&&R[k+1].keyR[k].keyyesnocount++R[i]=R[k];i=k;k=2*i;count++;break;k++R[k].keyR[0].keyYesnoR[i]=R[0];intjj=n/2;j--;直到j=1时为止sift(j,n)j=n;j--;直到j=2时为止R[0]=R[1];R[1]=R[j];R[j]=R[0];sift(1,j-1);（3）基数排序:typedefstructnode{keytypekey;structnode*next;}ND;struct{ND*f,*r;}qu[10];ND*p,*head;inti,j,k;longdd=1;当值为1时反复做i=0;i++;直到i10为止qu[i].f=qu[i].r=NULL;i=1;i++;直到i=n;为止k=R[i].key/dd%10;count++;p=(ND*)malloc(sizeof(ND));qu[k].f==NULLyesnoqu[k].f=qu[k].r=p;qu[k].r-next=p;qu[k].r=p;p-key=R[i].key;p-next=NULL;intflag=0;i=0;head=qu[i].f;当qu[i].f==NULL时反复做i++;当i9时反复做j=i+1;当j10&&qu[j].f==NULL时反复做j++;count++;j=10yesnobreak;qu[i].r-next=qu[j].f;flag=1;i=j;flag==0yesnobreak;i=0;i++直到i10;为止qu[i].f=qu[i].r=NULL;p=head;dd*=10;当值为p时head=p-next;k=p-key/dd%10;count++;qu[k].f==NULLyesnoqu[k].f=qu[k].r=p;qu[k].r-next=p;qu[k].r=p;qu[k].r-next=NULL;p=head;p=qu[0].f;i=1;当值为p时qu[0].f=p-next;R[i++].key=p-key;free(p);p=qu[0].f;实验步骤:[程序代码]#includestdlib.h#includealloc.h#defineN030000typedefintkeytype;typedefstructnode/*创建待排序的数*/{keytypekey;/*待排序的数*/}Element;ElementR[N0+1];/*存储一组待排序的数*/intn=150;/*定义随机生成数的个数为150*/voidgetData()/*随机产生150个数*/{inti;randomize();for(i=1;i=n;i++)R[i].key=random(1000);}voidprintData()/*将getData()函数产生的数据输出*/{inti;for(i=1;i=n;i++){printf(%6d,R[i].key);/*输出数据*/if(i%8==0)printf(\n);}printf(\n);}longcount;/*用来计算排序的次数*/intpartition(inti,intj)/*快速排序的一次排序过程*/{R[0]=R[i];/*确定分割基准*/while(ij){while(R[j].key=R[0].key&&ij){j--;count++;}/*自后向前扫描小于基准关键字的数*/R[i]=R[j];/*当扫描到小于基准关键字的数时将小的数赋给当前关键字所在的位置*/while(R[i].key=R[0].key&&ij){i++;count++;}/*自前向后扫描大于基准关键字的数*/R[j]=R[i];/*当扫描到大于基准关键字的数时将大的数赋给当前关键字所在的位置*/}R[i]=R[0];/*将基准记录移入最终位置*/returni;/*返回基准记录的最终位置*/}voidquickSort()/*快速排序*/{struct/*用来对待排序数进行区间分割*/{intlow,high;/*把区间分割成两块，分别用low和high标记*/}s[N0/2+1];/*最多分割成N0/2+1个区间*/inttop=0,i,j,k;/*i，j为指示器变量*/s[++top].low=1;s[top].high=n;while(top){i=s[top].low;j=s[top--].high;k=partition(i,j);/*进行排序*/if(k-1i){s[++top].low=i;s[top].high=k-1;}if(k+1j){s[++top].low=k+1;s[top].high=j;}}}voidsift(inti,intm)/*调整堆*/{intk=2*i;/*k初始化为2i，即指向待筛记录的左孩子*/R[0]=R[i];/*待筛记录送临时工作单元中*/while(k=m)/*逐层向下筛选*/{if(km&&R[k+1].keyR[k].key)k++;/*若右孩子记录关键字值小，让count指向右孩子*/count++;if(R[k].keyR[0].key)/*如果孩子的值大于其父亲，则进行调整*/{R[i]=R[k];/*孩子记录上移*/i=k;/*为继续向下筛选做准备*/k=2*i;count++;}elsebreak;/*孩子记录关键字大时，筛选结束，退出循环*/}R[i]=R[0];/*将最初的筛选记录填入正确位置*/}voidheapSort()/*堆排序*/{intj;/*定义循环变量*/for(j=n/2;j=1;j--)sift(j,n);/*调用筛选法，初始化堆*/for(j=n;j=2;j--)/*n-1次输出堆顶记录并调整堆*/{R[0]=R[1];R[1]=R[j];R[j]=R[0];/*堆顶记录与当前堆中最后一个记录交换*/sift(1,j-1);/*调用筛选法重建堆*/}}voidradixSort()/*基数排序*/{typedefstructnode/*用链表来存储待排序数组*/{keytypekey;/*数据域*/structnode*next;/*指向下个结点的指针域*/}ND;struct{ND*f,*r;/*定义队头和队尾指针*/}qu[10];/*定义队头和队尾指针数组*/ND*p,*head;inti,j,k;longdd=1;for(i=0;i10;i++)qu[i].f=qu[i].r=NULL;/*初始化队列为空*/for(i=1;i=n;i++){k=R[i].key/dd%10;count++;/*先取个位数进行比较*/p=(ND*)malloc(sizeof(ND));if(qu[k].f==NULL)qu[k].f=qu[k].r=p;/*如果队列为空作为队头结点插入*/else/*否则插入队尾*/{qu[k].r-next=p;qu[k].r=p;}p-key=R[i].key;/*数据给p*/p-next=NULL;/*队尾指向NULL为后续做准备*/}while(1){intflag=0;i=0;while(qu[i].f==NULL)i++;/*找第一个非空队列*/head=qu[i].f;while(i9)/*控制一次的收集*/{j=i+1;while(j10&&qu[j].f==NULL)j++;count++;if(j=10)break;qu[i].r-next=qu[j].f;flag=1;i=j;}if(flag==0)break;/*如果没有数据，退出循环*/for(i=0;i10;i++)qu[i].f=qu[i].r=NULL;p=head;dd*=10;while(p){head=p-next;k=p-key/dd%10;/*取十位数进行比较*