差别如何可以这么大
差别怎么可以这么大?
123456个数冒泡用了your programm running time is: 107484ms
快排用了your programm running time is: 47ms
------解决方案--------------------
- C/C++ code
#include "stdafx.h" #include "headfile.h" #include "BubbleSort.h" #include "QKSort.h" #include "stdlib.h" #include "time.h" #include "windows.h" #include "conio.h " #define TRUE 1 #define FALSE 0 typedef int KeyType; typedef int OtherType; typedef struct { KeyType key; OtherType other_data; }RecordType; void BubbleSort(RecordType r[], int length ) /*对记录数组r做冒泡排序,length为数组的长度*/ { int n,i,j; int change; RecordType x; n=length; change=TRUE; for ( i=1 ; i<= n-1 && change ;++i ) { change=FALSE; for ( j=1 ; j<= n-i ; ++j) if (r[j].key > r[j+1].key ) { x= r[j]; r[j]= r[j+1]; r[j+1]= x; change=TRUE; } } } /* BubbleSort */ int QKPass(RecordType r[],int left,int right) { //一次快速排序,并得到基准位置 RecordType temp; int low=left,high=right; temp=r[left];//选择基准记录 while(low<high) { while((low<high )&& (r[high].key>=temp.key)) high--; if (low<high) { r[low]=r[high]; low++; } while((low<high )&& (r[low].key<temp.key)) low++; if (low<high) { r[high]=r[low]; high--; } } r[low]=temp; return low; } void QKSort(RecordType r[],int low,int high) { int pos=0; if (low<high) { pos=QKPass(r,low,high);//调用一趟快速排序,以枢轴元素为界划分两个子表。 QKSort(r,low,pos-1);//左子表排序 QKSort(r,pos+1,high);//右子表排序 } } // AllKindsOfSort.cpp : 定义控制台应用程序的入口点。 // #define MAX 123456 RecordType r[MAX]; void fuzhi(RecordType r[], int length )//给数组元素赋值 { srand( (unsigned)time( NULL ) ); //初始化随机数 for (int i=0;i<length;i++) { r[i].key=rand()%MAX; } } void print(RecordType r[],int length) { printf("数组元素为:"); for (int i=0;i<length;i++) { printf("%d\t",r[i].key); } printf("\n"); } void WriteRecord(unsigned rTime)//将程序结果运行时间写入文件 { FILE *fpRecord=NULL; char *s="your programm running time is: "; char *c="ms "; if((fpRecord=fopen("record.txt","wt+"))==NULL) { printf("Cannot open file strike any key exit!"); getch(); exit(1); } fprintf( fpRecord, "%s", s); fprintf( fpRecord, "%d", rTime); fprintf( fpRecord, "%s", c); fclose(fpRecord); } int _tmain(int argc, _TCHAR* argv[]) { //程序运行时间程序块 time_t start,end; start=time(NULL); ///实验表明标准库中的时间函数精度不够 unsigned uStartTime = GetTickCount();//该函数只有在Win2000及以上的版本才被支持 unsigned uEndTime; unsigned rTime=0;//程序运行时间 //////////////////////////////////////////////////////////////////////////// //RecordType r[MAX]; fuzhi(r,MAX); //print(r,MAX); BubbleSort(r,MAX); //QKSort(r,0,MAX); //print(r,MAX); //////////////////////////////////////////////////////////////////////////// uEndTime = GetTickCount(); end=time(NULL); rTime=uEndTime-uStartTime; printf("%ums elapsed.\n",rTime); printf( "\1: The different is %6.3f\n ",difftime(end,start));//输出一个大概的时间。 /////////////////////////////////////////////////////////////////////////////// WriteRecord(rTime);//时间写入文件。 //system("pause"); return 0; }
123456个数冒泡用了your programm running time is: 107484ms
快排用了your programm running time is: 47ms
------解决方案--------------------