数据结构课程设计—内部排序算法比较.doc

#include#include#include#define MAXNUM 100#define RADIX 10#define MAX 8#define MAX_SPACE 10000typedef int KeysType;typedef structKeysType keysMAX;int next;SLCell;typedef struct SLCell rMAX_SPACE; int keynum; int recnum; SLList; typedef int ArrTypeRADIX; typedef struct int key; datatype; datatype RMAXNUM;/定义结构体数组 int cn11=0; int mn11=0;void CreateSLList(SLList &L,int n,datatype R ) /基数排序 L.recnum=n;L.keynum=3;mn10+=2; /printf(please input data numbers:/n); /scanf(%d,&L.recnum); /printf(please input keynumbers:/n); /scanf(%d,&L.keynum); /printf(please input %d numbers:/n,L.recnum); for(int i=1;i=L.recnum;i+) cn10+; int j=L.keynum-1;L.ri.keysj-=Ri.key/100;L.ri.keysj-=Ri.key%100/10;L.ri.keysj=Ri.key%10;mn10+=3; for(i=0;i=0;j-) printf(%d,L.ri.keysj); cn10+;cn10+; printf( ); cn10+; printf(n); void Distribute(SLCell (&r)MAX_SPACE,int i,ArrType &f,ArrType &e) /基数排序 int j,p; for(j=0;jRADIX;j+) cn10+; fj=0; mn10+; cn10+; for(p=r0.next;p;p=rp.next) cn10+; j=rp.keysi;mn10+; if (!fj) fj=p;mn10+; else rej.next=p; mn10+; ej=p;mn10+; cn10+; void Collect(SLCell (&r)MAX_SPACE,int i,ArrType f,ArrType e) /基数排序 int j,t; for(j=0;!fj;j+);cn10+; r0.next=fj;mn10+; cn10+; t=ej; mn10+; while (jRADIX-1) cn10+; for(j+;jRADIX-1&!fj;j+); cn10+; if (fj) rt.next=fj; t=ej; mn10+=2; cn10+; cn10+; rt.next=0; mn10+; void RadixSort(SLList &L) /基数排序 int i; L.keynum=3;mn10+; ArrType f,e; for(i=0;iL.keynum;i+) cn10+; Distribute(L.r,i,f,e); Collect(L.r,i,f,e); /printf(第%d趟收集后:n,i+1); /Display(L); printf(n); cn10+; void A(datatype R , int n)/基数排序* SLList L; CreateSLList(L, n,R); /printf(排序前的结果是:n); /Display(L); RadixSort(L); /printf(排序后的结果是:n); /Display(L); void D_InsertSort(datatype R , int n)/直接排序 int i,j;for(i=2; i=n; i+) cn0+; if (Ri.keyRi-1.key) R0=Ri; mn0+; for(j=i-1; R0.keyRj.key; j-)Rj+1=Rj; Rj+1=R0; mn0+=2; void Select_Sort(datatype R ,int n)/简单选择排序 int i,j,k; for(i=1;in;i+) k=i;for(j=i+1; j=n; j+) cn1+; if(Rj.keyRk.key) k=j; if (i=k) R0=Rk; Rk=Ri; Ri=R0; mn1+=3; void Insert(datatype R,int n)/直接插入排序* int i,j; for(i=2;i=n;+i) if(Ri.keyRi-1.key) cn6+; R0.key=Ri.key; Ri.key=Ri-1.key; mn6+=2; for(j=i-2;R0.keyRj.key;-j) Rj+1.key=Rj.key; mn6+=2; cn6+; cn6+; Rj+1.key=R0.key; mn6+;else cn6+;cn6+; cn6+; void Bubble_Sort (datatype R , int n)/冒泡排序 int i, j; int swap;for(i=1; in-1; i+) swap=0; for(j=1; j=n-i; j+) cn2+; if (Rj.keyRj+1.key) R0=Rj; Rj=Rj+1; Rj+1=R0; mn2+=3; swap=1; if(swap=0) break; void Zhe_ban(datatype R , int n)/折半插入排序*int i,j,low,high,m;for(i=2;i=n;+i)R0.key=Ri.key;mn7+;low=1;high=i-1;while(low=high)cn7+;m=(low+high)/2;if(R0.key=high+1;-j)Rj+1.key=Rj.key;cn7+;mn7+;cn7+; cn7+;void shell_sorts(datatype R ,int n)/希尔排序int k,i,j,dk; int dlta3=5,3,1;for(k=0;k3;+k)cn8+;dk=dltak;mn8+;for(i=dk+1;i=n;+i)cn8+;if(Ri.key0&(R0.keyRj.key);j-=dk)Rj+dk.key=Rj.key;cn8+;mn8+; cn8+; Rj+dk.key=R0.key;mn8+;cn8+;cn8+;void HeapAdjust(datatype R , int s, int t)/堆排序 datatype rc; int i,j ; rc=Rs; i=s; for(j=2*i; j=t; j=2*j) cn3+; if(jt & Rj.key Rj.key) break; Ri=Rj; mn3+; i=j; Ri=rc;void HeapSort(datatype R , int n)/堆排序* int i; for(i=n/2; i0; i- ) HeapAdjust(R, i, n); for(i=n; i1; i-) R0=R1; R1=Ri; Ri=R0; mn3+=3; HeapAdjust(R,1, i-1); void Merge(datatype R , datatype R1 , int s, int m , int t)/归并排序 int i,j,k; i=s; j=m+1; k=s; while (i=m&j=t) cn4+; if(Ri.keyRj.key) R1k+=Ri+; mn4+; else R1k+=Rj+; mn4+; while (i=m) R1k+=Ri+; mn4+; while (j=t) R1k+=Rj+; mn4+;void MSort(datatype R , datatype R1 , int s, int t)/归并排序 int m; if(s=t) R1s=Rs; mn4+; else m=(s+t)/2; MSort(R, R1, s, m); MSort(R, R1, m+1, t); Merge(R1, R, s, m, t); void MergeSort(datatype R , datatype R1 , int n)/归并排序* MSort(R, R1,1, n); int Partition(datatype R , int low, int high) R0=Rlow; mn5+; while(lowhigh) while(low=R0.key) cn5+; high-; if(lowhigh) Rlow=Rhigh; low+; mn5+; while(lowhigh&Rlow.keyR0.key) mn5+; low+; if(lowhigh) Rhigh=Rlow; high-; mn5+; Rlow=R0; mn5+; return low; void erlucharu(datatype R ,datatype d ,int n)/2路排序 /元素0是哨兵。 /int length = count -1; /int Rcount = 0, 49, 38, 65, 97, 76, 13, 27, 49; /对顺序表R作2-路插入排序。 /dn = 0 ; d0.key = R1.key;/R中D的第一个记录为d中排好序的记录。cn9+; int first = 0, final = 0;/first、final分别指示d中排好序的记录的第1个和最后1个记录的位置。 for (int i = 2; i = n; +i)/依次将R的第2个最后一个记录插入d中。 cn9+; if (Ri.key dfinal.key)/待插入记录大于d中最小值，插入到dfinal之后（不需移动d数组的元素）。 cn9+=2; final = final + 1; dfinal.key = Ri.key;mn9+=2; else/待插入记录大于d中最小值，小于d中最大值，插入到d的中间（需要移动d数组的元素）。 cn9+=2; int j = final +;/移动d尾部元素以便按序插入记录。 while (Ri.key dj.key) cn9+; d(j + 1) % n.key = dj.key; j = (j - 1 + n) % n;mn9+=2; cn9+; dj + 1.key = Ri.key;mn9+=2; cn9+;for ( i = 1; i = n; i +)/循环把d赋给R。 cn9+; Ri.key = d(i + first - 1) % n.key;/线性关系。mn9+; cn9+; void Quick_Sort(datatype R , int s, int t)/快速排序 int i; if( st ) i = Partition(R, s, t); Quick_Sort(R, s, i-1); Quick_Sort(R, i+1, t); void prin(datatype R,int n) int i ; printf(排序的结果为：); for(i=1;i25) printf(超出范围重新输入!n); goto a; for(i=1;i=n;i+)Ri.key=1+(int)(1000.0*rand()/(RAND_MAX+1.0);/随机生成1000以内的整数 printf(排序前元素顺序为:); for(i=1;in+1;i+) printf(%d ,Ri.key); printf(n); D_InsertSort(R,n);/直接排序 prin(R,n); Select_Sort(R,n);/简单选择排序 Bubble_Sort(R, n);/冒泡排序 HeapSort(R, n);/堆排序 datatype R1MAXNUM=0; MergeSort(R, R1, n);/二路归并排序 Quick_Sort(R,0, n);/快速排序 /ji_shu(R,n);/基数排序 Insert(R,n);/直接插入排序* Zhe_ban(R,n);/折半插入排序* erlucharu(R, R1,n);/2路排序*/ shell_sorts(R,n);/希尔排序 A(R,n); void zixing_input()/自行输入数字 int n,i; datatype R1MAXNUM=0; printf(请输入你要输入的个数（不大于于30的整数）:); scanf(%d,&n); printf(请输入各个元素:); for(i=1;in+1;i+) scanf(%d,&R1i.key); printf(排序前元素顺序为:); for(i=1;in+1;i+) printf(%d ,R1i.key); printf(n); D_InsertSort(R1,n);/直接排序 prin(R1,n); Select_Sort(R1,n);/简单选择排序 Bubble_Sort(R1, n);/冒泡排序 HeapSort(R1, n);/堆排序 MergeSort(R1, R1, n);/二路归并排序 Quick_Sort(R1,0, n);/快速排序 /ji_shu(R,n);/基数排序 Insert(R1,n);/直接插入排序* Zhe_ban(R1,n);/折半插入排序* erlucharu(R1, R1,n);/2路插入排序*/ shell_sorts(R1,n);/希尔排序 A(R,n); void main(void) int s; printf( |*|n); printf( |-欢 迎 使 用-|n); printf( |-（1）随 机 取 数-|n); printf( |-（2）自 行 输 入-|n); printf( |-（0）退 出 使 用-|n); printf( |*|n); printf( 请 选 择 操 作 方 式： ); scanf(%d,&s); switch(s) case 1: syste