shunxubiao.zip_4 3 2 1

#include <stdio.h> #include <stdlib.h> #include <time.h> #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define LIST_INIT_SIZE 500000 #define ElemType int #define RcdType int typedef struct { ElemType *elem; int length; int listsize; }SqList; int InitList_Sq(SqList &L) { L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }//创建顺序表 void Merge(ElemType c[],ElemType d[],int l,int m,int r) { int i,j,k; i=l; j=m+1; k=l; while((i<=m)&&(j<=r)) if(c[i]<=c[j]) d[k++]=c[i++]; else d[k++]=c[j++]; if(i>m)for(int q=j;q<=r;q++) d[k++]=c[q]; else for (int q=i;q<=m;q++) d[k++]=c[q]; } void MergePass(ElemType x[],ElemType y[],int s,int n) { int i=0; while(i<=n-2*s) { Merge(x,y,i,i+s-1,n-1); i=i+2*s; } if(i+s<n)Merge(x,y,i,i+s-1,n-1); else for(int j=i;j<=n-1;j++) y[j]=x[j]; } void MergeSort(ElemType a[],int n) { ElemType* b=new ElemType[n]; int s=1; while(s<n) { MergePass(a,b,s,n); s+=s; MergePass(b,a,s,n); s+=s; } }//二路排序 struct node { int min; int max; }; void QuickSort(int min,int max,int a[]) { int key = a[min]; int i = min; int j = max; int temp; struct node Stack[100]; int top = 0; Stack[top].min = min; Stack[top].max = max; while(top>-1) { //min max记录当前处理的这个区间的左极限和有极限 i = min = Stack[top].min; j = max = Stack[top].max; top--; key = a[min]; while(i<j) { while((i<j) && (key <= a[j])) {j--;} if(i < j) { temp = a[i];a[i] = a[j];a[j] = temp; i++; } while((i<j) && (key >= a[i])) {i++;} if(i < j) { temp = a[i];a[i] = a[j];a[j] = temp; j--; } }//处理一次 即将比绑定值小的全部放左边 比绑定值大的放右边 if(min < i-1) { top++; Stack[top].min = min; Stack[top].max = i-1; } if(max>i+1) { top++; Stack[top].min = i+1; Stack[top].max = max; } } }//快速排序 void HeapAdjust(int array[],int i,int nLength) { int nChild; int nTemp; for(;2*i+1<nLength;i=nChild) { nChild=2*i+1; if(nChild<nLength-1&&array[nChild+1]>array[nChild]) ++nChild; if(array[i]<array[nChild]) { nTemp=array[i]; array[i]=array[nChild]; array[nChild]=nTemp; } else break; } } void HeapSort(int array[],int length) { int tmp,i; for(i=length/2-1;i>=0;--i) HeapAdjust(array,i,length); for(i=length-1;i>0;--i) { tmp=array[i]; array[i]=array[0]; array[0]=tmp; HeapAdjust(array,0,i); } }//堆排序算法 void sort(int arr[], int n) { int i,j; int t; for(j=0;j<n-1;j++) for(i=0;i<n-1-j;i++) if (arr[i]>arr[i+1]) { t=arr[i]; arr[i]=arr[i+1]; arr[i+1]=t; } }//冒泡排序 void select_sort(int a[],int n) { int i,j,min; int t; for(i=0;i<n-1;i++) { min=i; for(j=i+1;j<n;j++) if(a[min]>a[j]) min=j; if(min!=i) { t=a[min]; a[min]=a[i]; a[i]=t; } } }//选择排序 void main() { int i,j,s; time_t a,b,c; SqList L1,L2,L3; InitList_Sq(L1); InitList_Sq(L2); InitList_Sq(L3); L1.length=LIST_INIT_SIZE; L2.length=LIST_INIT_SIZE; L3.length=10; i=0; printf("************************************************\n"); printf("菜单\n"); printf("1 二路归并排序算法\n"); printf("2 快速排序算法\n"); printf("3 堆排序算法\n"); printf("4 冒泡排序算法\n"); printf("5 选择排序算法\n"); printf("************************************************\n"); printf("请选择\n"); scanf("%d",&j); while(j!=0) { for(i=0;i<L1.listsize;i++) L1.elem[i]=rand(); for(i=0;i<L2.listsize;i++) L2.elem[i]=i; if(j==1) { a=time(NULL); MergeSort(L1.elem,L1.length); b=time(NULL); c=b-a; printf("L1时间为%d\n",c); a=time(NULL); MergeSort(L2.elem,L2.length); b=time(NULL); c=b-a; printf("L2时间为%d\n",c); scanf("%d",&j); } else if(j==2) { a=time(NULL); QuickSort(0,L1.length,L1.elem); b=time(NULL); c=b-a; printf("L1时间为%d\n",c); a=time(NULL); QuickSort(0,L2.length,L2.elem); b=time(NULL); c=b-a; printf("L2时间为%d\n",c); scanf("%d",&j); } else if(j==3) { a=time(NULL); HeapSort(L1.elem,L1.length); b=time(NULL); c=b-a; printf("L1时间为%d\n",c); a=time(NULL); HeapSort(L2.elem,L2.length); b=time(NULL); c=b-a; printf("L2时间为%d\n",c); scanf("%d",&j); } else if(j==4) { a=time(NULL); sort(L1.elem,L1.length); b=time(NULL); c=b-a; printf("L1时间为%d\n",c); a=time(NULL); sort(L2.elem,L2.length); b=time(NULL); c=b-a; printf("L2时间为%d\n",c); scanf("%d",&j); } else if(j==5) { a=time(NULL); select_sort(L1.elem,L1.length); b=time(NULL); c=b-a; printf("L1时间为%d\n",c); a=time(NULL); select_sort(L2.elem,L2.length); b=time(NULL); c=b-a; printf("L2时间为%d\n",c); scanf("%d",&j); } } }