排序算法及应用

课程名称数据结构与算法实验项目编号1505P000201实验项目名称排序算法及应用实验学时2学时实验日期实验地点计算机应用技术实验室指导教师班级姓名学号一、实验目的掌握常用的排序方法，深刻理解排序的定义和各种排序方法的特点。通过实验观察不同方法的不同之处，记录并分析各种排序方法的结果。二、实验环境硬件：每个学生需配备计算机一台。操作系统：Windows；软件：Windows操作系统+TurboC等；三、实验要求在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键宇比较次数和关键字移动次数，以取得直观感受。要求：理解及熟练运用直接插入排序、快速排序、堆排序和归并排序、哈希排序等内部排序算法。通过计数统计各算法的关键字比较次数和关键字移动次数。分析算法的时间复杂度、空间复杂度及稳定性等各项指标。四、实验内容在自己的U盘的“姓名+学号”文件夹中创建“实验16”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。设计随机数来测试排序算法运行时间的程序，其中可以通过修改RANDNUM的值来更改测试的数据量。具体参考如下：#detineRANDNUM10000//随机数的个数for（i=0;i<RANDNUM;i++）（//产生1万个随机数iRandNum[i]=rand（）%RANDNUM;排序算法进行测试（也和上一个实验结果进行比较），记录运行时间;把需排序的数改为20000，进行同样测试，并比较测试结果。通过随机的数据比较各算法的关键宇比较次数和关键字移动次数，取得直观感受并分析算法各项性能指标。（随机数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动））五、代码如下#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<time.h>〃辅助函数，求数据的最大位数intmaxbit(intL[],intn)(intd=1,i=0;//保存最大的位数intp=10;for(i=0;i<n;i++)(while(L[i]>=p)(p*=10;d++;}}returnd;}〃基数排序voidradixsort(intL[],intlen)(intd=maxbit(L,len);long*tmp=(long*)malloc(len*sizeof(long));long*count=(long*)malloc(10*sizeof(long));;//计数器，10个桶longi,j,k;intradix=1;for(i=1;i<=d;i++)(〃进行d次排序for(j=0;j<10;j++)//每次分配前清空计数器count[j]=0;for(j=0;j<len;j++)(〃统计每个桶中的记录数k=(L[j]/radix)%10;count[k]++;}for(j=1;j<10;j++)//将tmp中的位置依次分配给每个桶count[j]=count[j-1]+count[j];for(j=len-1;j>=0;j--)(//将所有桶中记录依次收集到tmp中k=(L[j]/radix)%10;count[k]--;tmp[count[k]]=L[j];}for(j=0;j<len;j++)//将临时数组的内容复制到L中L[j]=tmp[j];radix=radix*10;free(tmp);free(count);}intRandomInteger(longlow,longhigh)(longk;k=(long)(rand()%(high-low+1)+low);returnk;}voidzht_InsertSort(SqList*L)(/*对顺序表L作直接插入排序。算法10.1*/ftime(&t1);inti,j,t;for(i=2;i<=(*L).length;++i)ifLT((*L).r[i].key,(*L).r[i-1].key)/*"<"，需将L.r[i]插入有序子表*/((*L).r[0]=(*L).r[i];/*复制为哨兵*/for(j=i-1;LT((*L).r[0].key,(*L).r[j].key);--j)(*L).r[j+1]=(*L).r[j];/*记录后移*/(*L).r[j+1]=(*L).r[0];/*插入到正确位置*/}ftime(&t2);t=(t2.time-t1.time)*1000+(litm);printf("直接插入排序用时%d毫秒\n",t);}voidzht_BInsertSort(SqList*L)(/*对顺序表L作折半插入排序。算法10.2*/ftime(&t1);inti,j,m,low,high,t;for(i=2;i<=(*L).length;++i)((*L).r[0]=(*L).r[i];/*将L.r[i]暂存到L.r[0]*/low=1;high=i-1;while(low<=high)(/*在r[low..high]中折半查找有序插入的位置*/m=(low+high)/2;/*折半*/ifLT((*L).r[0].key,(*L).r[m].key)high=m-1;/*插入点在低半区*/elselow=m+1;/*插入点在高半区*/}for(j=i-1;j>=high+1;--j)(*L).r[j+1]=(*L).r[j];/*记录后移*/(*L).r[high+1]=(*L).r[0];/*插入*/}ftime(&t2);t=(t2.time-t1.time)*1000+(litm);printf("折半插入排序用时%d毫秒\n",t);}intmain()(longi=0;long*L=(long*)malloc(10000*sizeof(long));clock_tstart,finish;doubleduration;srand((long)time(NULL));for(i=0;i<10000;i++)(L[i]=i;//RandomInteger(0,10000);}start=clock();radixsort(L,10000);finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;for(i=0;i<10000;i++)(printf("%7.2ld",L[i]);}printf("%5.4lfs”,duration);getchar();getchar();getchar();return0;}六、运行结果截图VD:\c语言储伊题目\输入100。膈谁I对1皿0（］个数据进行排序：蔓接拓•入排序用时54电秒I折半插入排序用时53亳秒2—路插入排序用时函0毫秒Processexitedafter7.024secondswithreturnvalue0E青按任意键继续...七、实验总结与体会排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。直接插入排序：将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。艮即先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。希尔排序：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。选择排序：在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。堆排序：初始时把要排序的n个