讨论：是算法的问题还是的规调用的问题？大量排序速度差别极大！
讨论：是算法的问题还是的规调用的问题？大量排序速度差别极大！
A、初始化一些变量
float* pfSj; //存放一个数据系列，现用随机生成的方式生成它
pfSj=new float[1000];
pxuhao=new int[1000]; //存放序号的数列
for(int i=0;i<1000;i++)
{
SuzuXuhao[i]=i;
*(pfSj+i)=i;
}
B、析构——别忘了哦，内存泄漏就是这样造成的
delete[]pfSj;
delete[]pxuhao;;
1、冒泡排序
void CQuickPaiXuDoc::MaopaoPx2(float *pSuzu, int *pXuhao, int low, int high)
{
int n=0;
float temp;
int m,temp2;
int flag=0;
do{
flag=0;
for( m=low;m<high-n-1;m++)
{
if(*(pSuzu+m)>*(pSuzu+m+1))
{
temp=*(pSuzu+m);
*(pSuzu+m)=*(pSuzu+m+1);
*(pSuzu+m+1)=temp;
temp2=*(pXuhao+m);
*(pXuhao+m)=*(pXuhao+m)+1;
*(pXuhao+m+1)=temp2;
flag=1;
}
//*(pXuhao+m)=m+1;
};
n++;
}while(flag==1);
}
void CQuickPaiXuDoc::OnSceng() //生成随机数列的函数
{
srand((unsigned)time(NULL));
for(int i=0;i<1000;i++)
{
//Suzu[i]=rand()%1000;
//SuzuRam[i]=Suzu[i];
*(pfSj+i)=rand()%1000;
*(pxuhao+i)=i;
}
UpdateAllViews(NULL,NULL);
}
3、快速排序函数
void CQuickPaiXuDoc::QuickPaixu2(float *fsuju, int *xuhao, int low, int high)
{
int i=low;int
j=high;
float t=*(fsuju+low);
int tpx=*(xuhao+low);
while (i<j)
{
while (i<j && (*(fsuju+j)>t)) j--;
*(fsuju+i)=*(fsuju+j);
*(xuhao+i)=*(xuhao+j);
while (i<j && (*(fsuju+i)<=t)) i++;
*(fsuju+j)=*(fsuju+i);
*(xuhao+j)=*(xuhao+i); //存放序号的数组int* xuhao,
*(fsuju+i) = t;
*(xuhao+i)=tpx;
QuickPaixu2(fsuju,xuhao,low,i-1); //递归调用此函数
QuickPaixu2(fsuju,xuhao,i+1,high);
}
}
调用的函数
void CQuickPaiXuDoc::OnPaixu() //250次生成、排序对比测试
{
//……(我的应用中实际是1000次以上大量排序)
for(int np=0;np<250;np++)
{
OnSceng() ;
MaopaoPx2(pfSj,pxuhao,0,1000););//调用冒泡排序对数组pSj进行排序
// QuickPaixu2(pfSj,pxuhao,0,999); //作为对比的快速排序算法
}
}
我的测试对比结果发现，
冒泡排序只要4秒钟（赛扬1G，全是调用内存和其他硬件无关）
而“快速排序”用了超过10分钟！
理论上“快速排序对随机数据速度应该很快的，冒泡排序最笨，也是所花时间最稳定地算法。
不知道为什么会这样？差别超过100倍？各位试试看，给点意见
问题点数：30、回复次数：4Top
1 楼Kenmark（fenix）回复于 2006-07-03 10:54:39 得分 10
你的算法实现有问题！
一般不用说O（nlogn)所用时间肯定比O(n^2)少，还有就是数据特性比较差
QUICKSORT最快nlogn最慢n^2
使用O(nlogn)的HEAPSORT最快了大概
还有1000不是大量10^7以上还能算算Top
2 楼facaile（细细小雨）回复于 2006-07-03 12:44:36 得分 0
好像3、快速排序函数
void CQuickPaiXuDoc::QuickPaixu2(float *fsuju, int *xuhao, int low, int high)也没有什么问题啊，高手能不能试试看，发表一下意见Top
3 楼Polarislee（北极星)(无房无车，飘在北京）回复于 2006-07-03 15:33:34 得分 5
你使用的用于排序的序列是什么样的？Top
4 楼crazy_lazy_pig（疯狂懒猪）回复于 2006-07-03 15:38:20 得分 15
while (i<j)
{
while ((*(fsuju+j)>t)) j--;
*(fsuju+i)=*(fsuju+j);
*(xuhao+i)=*(xuhao+j);
while ((*(fsuju+i)<=t)) i++;
*(fsuju+j)=*(fsuju+i);
*(xuhao+j)=*(xuhao+i); //存放序号的数组int* xuhao,
}
*(fsuju+i) = t;
*(xuhao+i)=tpx;
QuickPaixu2(fsuju,xuhao,low,i-1); //递归调用此函数
QuickPaixu2(fsuju,xuhao,i+1,high);
Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
