1.归并排序 #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 50000 void merge(int [],int,int,int);//归并排序数组合并函数声明 void mergesort(int [],int,int);//归并排序数组排序函数声明 //主函数 int main() { int i,a1[N]; double t1,t2,t3,t4; for(i=0;i<N;i++) { a1[i]=rand()%N; } //归并排序N个随机数字所用的时间 t2=clock(); mergesort(a1,0,N-1); t2=clock()-t2; /*排好序的结果*/ for(i=0;i<N-1;i++) { printf("%4d\n",a1[i]); } printf("\n归并排序%d个随机数字所用时间为:%f毫秒\n",N,(double)t2); getch(); return 1; } //归并排序 //归并排序合并数组函数的具体实现 void merge(int a[],int low,int middle,int high) { int h,i,j,k; int b[N]; h=low; i=low; j=middle+1; while(h<=middle&&j<=high) { if(a[h]<=a[j]) { b[i]=a[h]; h++; } else { b[i]=a[j]; j++; } i++; } if(h>middle) for(k=j;k<=high;k++) { b[i]=a[k]; i++; } else { for(k=h;k<=middle;k++) { b[i]=a[k]; i++; } } for(k=low;k<=high;k++) { a[k]=b[k]; } } //归并排序函数的具体实现 void mergesort(int a[],int low,int high) { int middle; if(low<high) { middle=(low+high)/2; mergesort(a,low,middle); mergesort(a,middle+1,high); merge(a,low,middle,high); } } 2.快速排序 #include"stdio.h" #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 50000 void quickSort(int a[],int left,int right) { int i,j,temp; i=left; j=right; temp=a[left]; if(left>right) return; while(i!=j)/*找到最终位置*/ { while(a[j]>=temp && j>i) j--; if(j>i) a[i++]=a[j]; while(a[i]<=temp && j>i) i++; if(j>i) a[j--]=a[i]; } a[i]=temp; quickSort(a,left,i-1);/*递归左边*/ quickSort(a,i+1,right);/*递归右边*/ } int main() { double t2=clock(); int i,a[N]; for(i=0;i<N;i++) { a[i]=rand()%N; } quickSort(a,0,N-1); t2=clock()-t2; /*排好序的结果*/ for(i=0;i<N-1;i++) { printf("%4d\n",a[i]); } printf("\n快速排序%d个随机数字所用时间为:%f毫秒\n",N,(double)t2); getch(); return 1; }
3.堆排序 #include <stdio.h> #include <time.h> #include <math.h> #define LEFT(i) ((i)<<1) #define RIGHT(i) (((i)<<1) + 1) #define N 50000 void max_heapify(int a[], int i, int heapsize); void heap_sort(int a[], int heapsize); void build_max_heap(int a[], int heapsize); void exchange(int *x, int *y); //交换两个数的值 void exchange(int *x, int *y) { int temp; temp = *x; *x = *y; *y = temp; } //保持最大堆性质 void max_heapify(int a[], int i, int heapsize) { int left, right, largerest; left = LEFT(i); right = RIGHT(i); if (left <= heapsize && a[left]>a[i]) { largerest = left; }else{ largerest = i; } if (right <= heapsize && a[right]>a[largerest]) { largerest = right; } if(largerest != i) { exchange(&a[i], &a[largerest]); max_heapify(a, largerest, heapsize); } } //建造最大堆 void build_max_heap(int a[], int heapsize) { int i; for (i=(int)ceil(heapsize/2); i >=1 ; i--) { max_heapify(a, i, heapsize); } } //堆排序 void heap_sort(int a[], int heapsize) { //build heap build_max_heap(a, heapsize); while(heapsize>1) { //exchange max exchange(&a[1], &a[heapsize]); heapsize--; max_heapify(a, 1, heapsize); } } int main() { double t2=clock(); int i,a[N]; for(i=0;i<N;i++) { a[i]=rand()%N; } heap_sort(a, N-1); t2=clock()-t2; //打印排序后的数组 for (i=1; i<N ; i++) { printf("%d\n",a[i]); } printf("\n堆排序%d个随机数字所用时间为:%f毫秒\n",N,(double)t2); getch(); return 1; }
4.冒泡排序 #include <stdio.h> #include <time.h> #include <math.h> #define N 50000 int main() { double t2=clock(); int i,j,a[N]; int flag=1; int temp; for(i=0;i<N;i++) { a[i]=rand()%N; } for(i=0;i<N;i++) { for(j=0;j<N-i;j++) { if(a[j+1]<a[j]) { temp=a[j+1]; a[j+1]=a[j]; a[j]=temp; flag=0; } } if(flag==1) { break; } } t2=clock()-t2; //打印排序后的数组 for (i=0; i<N ; i++) { printf("%d\n",a[i]); } printf("\n冒泡排序%d个随机数字所用时间为:%f毫秒\n",N,(double)t2); getch(); return 1; }
时间性能最好的是快速排序,最差的是冒泡排序。。。。。。 |
|