排序C语言实验报告.docx

《排序C语言实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、排序数学系李一鹏PB12001076第五组1.试验题目：排序2.实验目的：掌握各种内部排序思想。3.实验内容：每一个在令狐冲身边出现的女性都会在令狐冲心中占有一定“地位”，例如小师妹的地位值是23456，任盈盈的地位值是30000，东方不败的地位值是32767，蓝凤凰的是1234，市集卖菜大妈41，市集路过小姑娘2000……现在令狐冲希望把她们按顺序一个个攻略，请编一个程序，把她们按地位排序。4.算法思想：本程序有冒泡，快排，插入，希尔，选择，堆排，归并七个排序。下面介绍堆排和归并。堆排：建堆时先把初态视为只有一个结点的大根堆，每加入

2、一个数据与父结点比较，若父结点小于当前结点则上移，重复操作直至父结点比当前结点大。排序时交换堆尾与根，堆尾指标前移，根与子结点比较，与大者交换，重复操作直至子结点均小于当前结点。归并：把序列半分，先把两个子序列排序，然后用两个指标记录子序列当前最小值，把右指标插入两指标之间的序列，左指标记录为当前插入点的下一个位置，右指标右移。5.程序清单：#include#include#includetypedefstructdatatype{intnode,data;}dtype;dt

3、ypea[1000];intn,sum1,sum2;//sum1记录比较次数，sum2移动次数voidreadln(){//用文件读入待排序数据inti;FILE*f1;f1=fopen("a300.txt","r");fscanf(f1,"%d",&n);for(i=1;i<=n;i++){a[i].node=i;fscanf(f1,"%d",&a[i].data);}fclose(f1);}voidbubblesort(){//冒泡排序inti,j;dtypet;for(i=n-1;i;i--)for(j=i;j

4、um1++;if(a[j].data>a[j+1].data){t=a[j];a[j]=a[j+1];a[j+1]=t;sum2++;}}}voidqsort(intl,intr){//快速排序inti,j,m;dtypet;i=l;j=r;m=a[l].data;sum2++;while(i<=j){while(a[i].datam)j--,sum1++;if(i<=j){t=a[i];a[i]=a[j];a[j]=t;i++;j--;sum2++;}}if(j>l)qso

5、rt(l,j);if(im){a[j+1]=a[j];j--;sum1++;sum2++;}a[j+1]=a[0];sum2++;}}voidshellsort(intd){//隔了d个数的插入排序inti,j,m,k;for(i=1;i<=d;i++)for(j=i+d;j<=n;j+=d){a[0]=a

6、[j];m=a[0].data;k=j-d;sum2++;while(k>0&&a[k].data>m){a[k+d]=a[k];k-=d;sum2++;sum1++;}a[k+d]=a[0];sum2++;}}voidshells(){//希尔排序inti,m,d[100];printf("Inputthesumofyourshellarray:");scanf("%d",&m);printf("Inputyourshellarray:");for(i=1;i<=m;i++)scanf("%d",&d[i]);while(g

7、etchar()!=10);for(i=m;i;i--)shellsort(d[i]);}voidselectsort(){//选择排序inti,j,k,m;dtypet;for(i=1;i

8、.data;sum2++;while(a[i/2].data