实现各种排序算法并分析与比较.rar_shell排序_各种排序_各种排序算法_堆排序_快速排序

#include<stdio.h> #define M 100 int max; int m; int compare=0; int exchange=0; int loaddata(int list[]) { FILE *fp; int i,j=1; printf("\n\n\n\n\n\n\n\n\n\n"); printf(" **********请选择数据类型:***********\n\n"); printf(" 1.递增排列的原始数据(最好情况）.\n"); printf(" 2.非递增排列的原始数据（最坏情况）.\n"); printf(" 3.任意排序的原始数据(一般情况）.\n"); printf(" *************************************\n\n"); printf(" 请选择："); scanf("%d",&i); switch(i) { case 1:{ fp=fopen("notdescending.txt","r"); break; } case 2:{ fp=fopen("descending.txt","r"); break; } case 3:{ fp=fopen("radom.txt","r"); break; } default :{ printf("your choice is illeagal! please choose agaian!\n"); loaddata(list); } } while((fscanf(fp,"%d",&list[j++]))!=EOF); max=j-1; fclose(fp); return i; } reloaddata(int i,int list[]) { FILE *fp; int j=1; switch(i) { case 1:{ fp=fopen("notdescending.txt","r"); break; } case 2:{ fp=fopen("descending.txt","r"); break; } case 3:{ fp=fopen("radom.txt","r"); break; } default :{ printf("your choice is illeagal! please choose agaian!\n"); loaddata(list); } } while((fscanf(fp,"%d",&list[j++]))!=EOF); max=j-1; fclose(fp); } /*输出提示*/ tish2(int list[]) { int i; printf("排序后的序列:"); for(i=1;i<max;i++) printf("%d ",list[i]); printf("\n\n"); } /*插入排序*/ void insertsort(int list[]) { int i,j; for(i=2;i<max;i++) /*依次插入从第2个开始的所有元素*/ { list[0]=list[i]; /*设置哨所，准备找插入位置*/ exchange++; j=i-1; while(list[0]<list[j]) /*找插入位置并后移*/ { list[j+1]=list[j]; /*后移*/ j--; compare++; exchange++; } compare++; list[j+1]=list[0]; /*插入第i 个元素的副本，即前面设置的哨兵*/ exchange++; } tish2(list); switch(m) { case 1: printf("最好情况:\n");break; case 2: printf("最坏情况：\n");break; case 3: printf("一般情况：\n");break; } printf("总比较次数：%d\n",compare); printf("总移动次数：%d",exchange); } /*SHELL排序*/ shellpass(int *list,int d) { int i,j; for(i=d+1;i<max;i++) { compare++; if(list[i]<list[i-d]) /*需将list[i]插入有序子表*/ { list[0]=list[i];j=i-d; /*list[0]为临时变量*/ exchange++; do{ list[j+d]=list[j]; j=j-d; exchange++; compare++; }while(j>0&&list[0]<list[j]); /*记录后移，查找插入位置*/ list[j+d]=list[0]; /*插入到正确的位置*/ exchange++; } } } shellsort(int* list) { int increment=max; compare=exchange=0; do{ increment=increment/3+1; shellpass(list,increment);} /*一趟增量为increment的插入排序*/ while(increment>1); tish2(list); switch(m) { case 1: printf("最好情况:\n");break; case 2: printf("最坏情况：\n");break; case 3: printf("一般情况：\n");break; } printf("总比较次数：%d\n",compare); printf("总移动次数：%d",exchange); } /*冒泡排序*/ bubblesort(int *list) { int i=1,j,temp; int done=0; compare=exchange=0; while (i<=max-1&&!done) /*最多进行max-1次冒泡，如果没有发生交换则结束*/ { done=1 ; compare++; for(j=1;j<=max-1-i;j++) /*只需比较max-1-i次*/ if(list[j]>list[j+1]) /*如果当前的元素大于后面的元素*/ { temp=list[j]; /*用中间变量进行交换*/ list[j]=list[j+1]; list[j+1]=temp; done=0; exchange+=3; compare++; } i++; } tish2(list); switch(m) { case 1: printf("最好情况:\n");break; case 2: printf("最坏情况：\n");break; case 3: printf("一般情况：\n");break; } printf("总比较次数：%d\n",compare); printf("总移动次数：%d\n",exchange); } /*快速排序*/ quicksort(int*list,int left,int right) { int i,j; int pivot; /*分割指针*/ int temp; /*用于数值交换是的暂存变量*/ i=left;j=right+1; pivot=list[left]; /*取最左边的元素*/ if(i<j) { do { compare++; do /*从左到右找比pivot大的值*/ { i++;compare++; }while(list[i]<=pivot&&i<=right); do /*从右到左找比皮vot小的值*/ { j--;compare++; }while(list[j]>=pivot&&j>left); if(i<j) /*交换list[i]，list[j]的值*/ { temp=list[i]; list[i]=list[j]; list[j]=temp; exchange+=3; } }while(i<j); temp=list[left]; /*交换list[left]，list[j]的值*/ list[left]=list[j]; list[j]=temp; exchange+=3; quicksort(list,left,j-1); quicksort(list,j+1,right); } } /*简单选择排序*/ simpleselectsort(int *list) { int i,j,k; compare=exchange=0; for(i=1;i<max;i++) /*每次选择一个最小的元素的位置，和第i个元素交换*/ { k=i; /*记下当前最小元素的位置*/ compare++; for(j=i+1;j<max;j++) /*修改当前最小元素的位置*/ if(list[j]<list[k]){ k=j;compare++;} if(k!=i) /*如果第i次的最小元素位置k不等于i，则将第k，i个元素交换*/ { list[0]=list[i]; /*以没有用到的第0个元素作为ie中间变量*/ list[i]=list[k]; list[k]=list[0]; exchange+=3; } } tish2(list); switch(m) { case 1: printf("最好情况:\n");break; case 2: printf("最坏情况：\n");break; case 3: printf("一般情况：\n");break; } printf("总比较次数：%d\n",compare); printf("总移动次数：%d\n",exchange); } /*堆排序*/ void sift(int *list ,int root,int n) { int child,rootkey; list[0]=list[root]; rootkey=list[root]; exchange+=2; child=2*root; while(child<=n){ /*沿值较大的孩子节点向下筛*/ if((child<n)&&(list[child]<list[child+1])) { child++;compare++;} /*child关键字较大值的记录下标*/ if(rootkey>list[child]) { compare++;break;} else { list[child/2]=list[child];exchange++; child*=2; compare++; /*list[0]应该插入位置child上*/ } } list[child/2]=list[0]; /*插入*/ exchange++; } heapsort(int *list) { int i,temp; compare=exchange=0; for(i=(max-1)/2;i>=1;i--) sift(list,i,max-1); /*把list建成大顶堆*/ for(i=max-2;i>=1;i--) /*将堆顶记录和当前未经排序列list中最后一个记录交换*/ { temp=list[i+1]; list[i+1]=list[1]; list[1]=temp; exchange+=3; sift(list,1,i); } tish2(list); switch(m) { case 1: printf("最好情况:\n");break; case 2: printf("最坏情况：\n");break; case 3: printf("一般情况：\n");break; } printf("总比较次数：%d\n",compare); printf("总移动次数：%d\n",exchange); } /*归并排序*/ /*一次归并排序*/ void merge(int *tabs,int *tabg,int u,int m,int v) { int i,j,k,t; i=u; /*i从第一段的起始位置开始，一直到最终位置m*/ j=m+1; /*i从第二段的起始位置开始，一直到最终位置v*/ k=u; /*k表示的是目标tabg的起始位置*/ while(i<=m&&j<=v) { /*将两段有序元素中元素值较小的元素依次放入目标tabg中*/ if(tabs[i]<=tabs[j]) {tabg[k]=tabs[i++];compare++;exchange++;} else {tabg[k]=tabs[j++];compare++;exchange++;} k++; } if(i<=m) /*将第一段剩余元素放入目标tabg中*/ { compare++; for(t=i;t<=m;t++) {tabg[k+t-i]=tabs[t];exchange++;}} else { compare++;for(t=j;t<=v;t++) /*将第二段剩余元素放入目标tabg中*/ { tabg[k+t-j]=tabs[t];exchange++;}} } /*一趟归并排序*/