差别怎么可以这么大？
- 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 0typedef 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 123456RecordType 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
------解决方案--------------------
恩，真有这么好。。
[解决办法]
这个是必须的啊，数据越大，两种算法差距越大，一个是log2n,一个是n^2
[解决办法]
不过快排也有缺点，pivok选择不好的话性能会严重退化，如果数列已经有序，在bubble中设置一个flags，可以到常数的性能
[解决办法]
外物都是相辅相成的。有的情况需要它，有时则没必要需要它
[解决办法]
楼主看一看他们的时间复杂度就知道了：冒泡，O（n^2）， 快排：在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，就像楼上说的！也有可能性能有退化
[解决办法]
快排算法是图灵奖获得者 Tony Hoare设计的，在最优的情况下，快排的时间复杂度为nlogn。
而且还可以经过很多优化。
冒泡排序的时间复杂度是O(n2)，比较容易理解，但效率比较低。
[解决办法]
呵呵 去画画两者的函数图象 你就会看出来
[解决办法]
楼主好好理解一下时间复杂度这个概念。你就懂了。
[解决办法]
nlogn和n^2是不同的级别哦。可以画一个曲线，在n越大的情况下，区别越明显。
[解决办法]
恩，不知道你能不能盲写快排。
一般我们都是直接调stdlib的qsort，bsearch之类的。