设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 各种排序(你懂的?)
返回列表 发新帖
查看: 4606|回复: 14

[技术交流] 各种排序(你懂的?)

[复制链接]
raotf
发表于 2011-7-6 14:34:47 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
本帖最后由 raotf 于 2011-7-22 19:22 编辑 
#include <stdio.h>
#include <conio.h>
#include <Windows.h>
#include <time.h>

#define MAX 12345

void data_shuchu(int* p,int leng);
void data_fuzhi(int* p,int* data,int leng);
void paixu_maopao(int* p,int leng);
void paixu_xuanze(int* p,int leng);
void paixu_charu(int* p,int leng);
void paixu_kuaisu(int* p,int tou,int wei);
int* paixu_guibing(int* p,int leng);
int* guibing_hebing(int* zuo_data,int zuo_leng,int* you_data,int you_leng);
int kuaisu_dingwei(int* p,int tou,int wei);
double pk_paixu(int* p,int leng,char* paixu);


void main()
{

int data[MAX];
int p[MAX];
int i;
double yongshi;
double paixu_time[5]={0};
char* paixu_str[]={"插入排序","快速排序","归并排序","冒泡排序","选择排序"};

srand(time(0));
for(i=0;i<MAX;i++)
data[i]=rand();

for(i=0;i<10*5;i++)
{
if(0==i%5)
printf("第%d轮:\n",i/5+1);

data_fuzhi(p,data,MAX);
//data_shuchu(p,MAX);
yongshi=pk_paixu(p,MAX,paixu_str[i%5]);
//data_shuchu(p,MAX);
paixu_time[i%5]+=yongshi;
printf("%s排序用时: %lf秒\n",paixu_str[i%5],yongshi); 
if(4==i%5)
printf("\n");
}

for(int j=0;j<5;j++)
printf("%s平均用时: %lf秒\n",paixu_str[j],paixu_time[j]/(i/5));

getch();
return;
}


double pk_paixu(int* p,int leng,char* paixu)
{
int* data;
double t_avg;
LONGLONG t1_long;
LONGLONG t2_long;
LARGE_INTEGER litmp;

QueryPerformanceFrequency(&litmp);
t_avg=litmp.QuadPart;

QueryPerformanceCounter(&litmp);
t1_long=litmp.QuadPart;

if(!strcmp(paixu,"归并排序"))
{
data=paixu_guibing(p,leng);
}
else if(!strcmp(paixu,"冒泡排序"))
{
paixu_maopao(p,leng);
}
else if(!strcmp(paixu,"选择排序"))
{
paixu_xuanze(p,leng);
}
else if(!strcmp(paixu,"插入排序"))
{
paixu_charu(p,leng);
}
else if(!strcmp(paixu,"快速排序"))
{
paixu_kuaisu(p,0,leng-1);
}

QueryPerformanceCounter(&litmp);
t2_long=litmp.QuadPart;


if(!strcmp(paixu,"归并排序"))
data_fuzhi(p,data,leng);

return (t2_long-t1_long)/t_avg;
}

void data_shuchu(int* p,int leng)
{
for(int i=0;i<leng;i++)
{ 
if(i%10==0)
printf("\n");
printf("%d ",p[i]);
}
printf("\n");
return;
}

void data_fuzhi(int*p,int* data,int leng)
{
for(int i=0;i<leng;i++)
*(p+i)=*(data+i);
return;
}

int* paixu_guibing(int* p,int leng)
{
if(leng<=1)
return p;

int zuo_leng=leng/2;
int you_leng=leng-zuo_leng;
int* zuo_data=new int[zuo_leng];
int* you_data=new int[you_leng];

for(int i=0;i<zuo_leng;i++)
{
*(zuo_data+i)=*(p+i);
*(you_data+i)=*(p+i+zuo_leng);
}
if(0!=leng/2)
*(you_data+you_leng-1)=*(p+leng-1);

zuo_data=paixu_guibing(zuo_data,zuo_leng);
you_data=paixu_guibing(you_data,you_leng);
return guibing_hebing(zuo_data,zuo_leng,you_data,you_leng);
}

int* guibing_hebing(int* zuo_data,int zuo_leng,int* you_data,int you_leng)
{
int* data=new int[zuo_leng+you_leng];

int zuo=0;
int you=0;

while(zuo<zuo_leng&&you<you_leng)
{
if(*(zuo_data+zuo)<=*(you_data+you))
{
*(data+zuo+you)=*(zuo_data+zuo);
zuo++;
}
else
{
*(data+zuo+you)=*(you_data+you);
you++;
}
}
while(zuo<zuo_leng)
data[zuo+you]=zuo_data[zuo++];
while(you<you_leng)
data[zuo+you]=you_data[you++];

return data;
}

void paixu_kuaisu(int *p,int tou,int wei)
{
if(tou<wei)
{
int index=kuaisu_dingwei(p,tou,wei);
paixu_kuaisu(p,tou,index-1);
paixu_kuaisu(p,index+1,wei);
}
return;
}

int kuaisu_dingwei(int *p,int tou,int wei)
{
int data=p[tou+(wei-tou)/2];
p[tou+(wei-tou)/2]=p[tou];

while(tou<wei)
{
while(tou<wei&&*(p+wei)>=data)
wei--;
*(p+tou)=*(p+wei);

while(tou<wei&&*(p+tou)<=data)
tou++;
*(p+wei)=*(p+tou);

}
*(p+tou)=data;
return tou;
}

void paixu_maopao(int* p,int leng)
{
int data;
for(int i=0;i<leng-1;i++)
{
for(int j=leng-1;j>i;j--)
{
if(*(p+j)<*(p+j-1))
{
data=*(p+j);
*(p+j)=*(p+j-1);
*(p+j-1)=data;
}
}
}
return;
}

void paixu_xuanze(int* p,int leng)
{
int data;
for(int i=0;i<leng-1;i++)
{
for(int j=i;j<leng;j++)
{
if(*(p+i)>*(p+j))
{
data=*(p+i);
*(p+i)=*(p+j);
*(p+j)=data;
}
}
}
return;
}

void paixu_charu(int *p,int leng)
{
int data;
int index;
for(int i=1;i<leng;i++)
{
data=*(p+i);
index=i;
while(index>0&&*(p+index-1)>data)
{
*(p+index)=*(p+index-1);
index--;
}
*(p+index)=data;
}

return;
}


下面是更新版~~~~~
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <Windows.h>
#include <time.h>

#define MAX 123456
#define PAIXU_CHARU 0
#define PAIXU_KUAISU 1
#define PAIXU_GUIBING 2
#define PAIXU_MAOPAO 3
#define PAIXU_XUANZE 4
#define PAIXU_XIER 5
#define PAIXU_YIERSAN 6
#define PAIXU_GESHIBAI 7
#define PAIXU_DUI 8
#define PAIXU_QSORT 9

#define FANGFASHU 10


void data_shuchu(int* p,int leng);
void data_fuzhi(int* p,int* data,int leng);
void paixu_maopao(int* p,int leng,int (* cmp)(const void* a,const void* b));
void paixu_xuanze(int* p,int leng,int (* cmp)(const void* a,const void* b));
void paixu_charu(int* p,int leng,int (* cmp)(const void* a,const void* b));
void paixu_kuaisu(int* p,int leng,int (* cmp)(const void* a,const void* b));
void paixu_xier(int* p,int leng,int (* cmp)(const void* a,const void* b));
void paixu_geshibai(int* p,int leng,int (* cmp)(const void* a,const void* b));
void paixu_dui(int* p,int leng,int (* cmp)(const void* a,const void* b));
int paixu_fangfa(const void* a,const void* b); 
int* paixu_guibing(int* p,int leng,int (* cmp)(const void* a,const void* b));
int* paixu_yiersan(int* p,int leng,int (* cmp)(const void* a,const void* b));
int* guibing_hebing(int* zuo_data,int zuo_leng,int* you_data,int you_leng,int (* cmp)(const void* a,const void* b));
int kuaisu_dingwei(int* p,int tou,int wei,int (* cmp)(const void* a,const void* b));
void dui_jian(int* p,int s,int leng,int (* cmp)(const void* a,const void* b));
double pk_paixu(int* p,int leng,int style,int (* cmp)(const void* a,const void* b)); 


void main()
{

int* data=new int[MAX];
int* p=new int[MAX];
int i;
double yongshi;
double paixu_time[FANGFASHU]={0};
char* paixu_str[FANGFASHU]={"插入排序","快速排序","归并排序","冒泡排序","选择排序","希尔排序","计数排序","基数排序","堆排序 ","QSORT "};

srand(time(0));
for(i=0;i<MAX;i++)
data[i]=rand();

for(i=0;i<3*FANGFASHU;i++)
{
if(0==i%FANGFASHU)
printf("第%d轮:\n",i/FANGFASHU+1);

data_fuzhi(p,data,MAX);
//data_shuchu(p,MAX);
yongshi=pk_paixu(p,MAX,i%FANGFASHU,paixu_fangfa);
//data_shuchu(p,MAX);
paixu_time[i%FANGFASHU]+=yongshi;

printf("%s排序用时: %lf\n",paixu_str[i%FANGFASHU],yongshi); 

if(FANGFASHU-1==i%FANGFASHU)
printf("\n");
}

for(int j=0;j<FANGFASHU;j++)
printf("%s平均用时: %lf\n",paixu_str[j],paixu_time[j]/(i/FANGFASHU));

getch();
return;
}


double pk_paixu(int* p,int leng,int style,int (* cmp)(const void* a,const void* b))
{
int* data;
double t_avg;
LONGLONG t1_long;
LONGLONG t2_long;
LARGE_INTEGER litmp;

QueryPerformanceFrequency(&litmp);
t_avg=litmp.QuadPart;

QueryPerformanceCounter(&litmp);
t1_long=litmp.QuadPart;

switch(style)
{
case PAIXU_CHARU:
//paixu_charu(p,leng,cmp);
break;

case PAIXU_KUAISU:
paixu_kuaisu(p,leng,cmp);
break;

case PAIXU_GUIBING:
data=paixu_guibing(p,leng,cmp);
break;

case PAIXU_MAOPAO:
//paixu_maopao(p,leng,cmp);
break;

case PAIXU_XUANZE:
//paixu_xuanze(p,leng,cmp);
break;

case PAIXU_XIER:
paixu_xier(p,leng,cmp);

case PAIXU_YIERSAN:
data=paixu_yiersan(p,leng,cmp);
break;

case PAIXU_GESHIBAI:
paixu_geshibai(p,leng,cmp);
break;

case PAIXU_DUI:
paixu_dui(p,leng,cmp);
break;

case PAIXU_QSORT:
qsort(p,leng,sizeof(int),cmp);
break;

default:break;
}

QueryPerformanceCounter(&litmp);
t2_long=litmp.QuadPart;


if(PAIXU_GUIBING==style||PAIXU_YIERSAN==style)
data_fuzhi(p,data,leng);

return (t2_long-t1_long)/t_avg;
}

void data_shuchu(int* p,int leng)
{
for(int i=0;i<leng;i++)
{ 
if(i%10==0)
printf("\n");
printf("%d ",p[i]);
}
printf("\n");
return;
}

void data_fuzhi(int*p,int* data,int leng)
{
for(int i=0;i<leng;i++)
*(p+i)=*(data+i);
return;
}

int* paixu_guibing(int* p,int leng,int (* cmp)(const void* a,const void* b))
{
if(leng<=1)
return p;

int zuo_leng=leng/2;
int you_leng=leng-zuo_leng;
int* zuo_data=new int[zuo_leng];
int* you_data=new int[you_leng];

for(int i=0;i<zuo_leng;i++)
{
*(zuo_data+i)=*(p+i);
*(you_data+i)=*(p+i+zuo_leng);
}
if(0!=leng/2)
*(you_data+you_leng-1)=*(p+leng-1);

zuo_data=paixu_guibing(zuo_data,zuo_leng,cmp);
you_data=paixu_guibing(you_data,you_leng,cmp);
return guibing_hebing(zuo_data,zuo_leng,you_data,you_leng,cmp);
}

int* guibing_hebing(int* zuo_data,int zuo_leng,int* you_data,int you_leng,int (* cmp)(const void* a,const void* b))
{
int* data=new int[zuo_leng+you_leng];

int zuo=0;
int you=0;

while(zuo<zuo_leng&&you<you_leng)
{
if(0>=cmp((zuo_data+zuo),(you_data+you)))
{
*(data+zuo+you)=*(zuo_data+zuo);
zuo++;
}
else
{
*(data+zuo+you)=*(you_data+you);
you++;
}
}
while(zuo<zuo_leng)
data[zuo+you]=zuo_data[zuo++];
while(you<you_leng)
data[zuo+you]=you_data[you++];

return data;
}

void paixu_kuaisu(int* p,int leng,int (* cmp)(const void* a,const void* b))
{
int* stack=new int[leng*2];
int top=0;
int tou=0;
int wei=leng-1;
int index;

while(tou<wei)
{
index=kuaisu_dingwei(p,tou,wei,cmp);

stack[top++]=index+1;
stack[top++]=wei;
wei=index-1;
while(tou>=wei&&top)
{
wei=stack[--top];
tou=stack[--top];
}
}

return;
}

int kuaisu_dingwei(int *p,int tou,int wei,int (* cmp)(const void* a,const void* b))
{
int data=p[tou+(wei-tou)/2];
p[tou+(wei-tou)/2]=p[tou];

while(tou<wei)
{
while(tou<wei&&0<=cmp((p+wei),&data))
wei--;
*(p+tou)=*(p+wei);

while(tou<wei&&0>=cmp((p+tou),&data))
tou++;
*(p+wei)=*(p+tou);

}
*(p+tou)=data;
return tou;
}

void paixu_maopao(int* p,int leng,int (* cmp)(const void* a,const void* b))
{
int data;

for(int i=0;i<leng-1;i++)
{
for(int j=leng-1;j>i;j--)
{
if(0>cmp((p+j),(p+j-1)))
{
data=*(p+j);
*(p+j)=*(p+j-1);
*(p+j-1)=data;
}
}
}
return;
}

void paixu_xuanze(int* p,int leng,int (* cmp)(const void* a,const void* b))
{
int data;

for(int i=0;i<leng-1;i++)
{
for(int j=i;j<leng;j++)
{
if(0>cmp((p+j),(p+i)))
{
data=*(p+i);
*(p+i)=*(p+j);
*(p+j)=data;
}
}
}
return;
}

void paixu_charu(int *p,int leng,int (* cmp)(const void* a,const void* b))
{
int data;
int index;

for(int i=1;i<leng;i++)
{
data=*(p+i);
index=i;
while(index>0&&0>cmp(&data,(p+index-1)))
{
*(p+index)=*(p+index-1);
index--;
}
*(p+index)=data;
}

return;
}

void paixu_xier(int* p,int leng,int (* cmp)(const void* a,const void* b))
{
int index;
int data;
int n;

for(n=leng/2;n>0;n/=2)
{
for(int i=n;i<leng;i++)
{
data=p[i];
index=i-n;
while(index>=0&&0>cmp(&data,(p+index)))
{
p[index+n]=p[index];
index-=n;
} 
p[index+n]=data;
}
}
return;
}

int* paixu_yiersan(int* p,int leng,int (* cmp)(const void* a,const void* b))
{ 
int max=0;
for(int i=0;i<leng;i++)
if(max<p[i])
max=p[i];

int* index=new int[max+1];
int* data=new int[leng];
bool shunxu=true;
int a=1;
int b=2; 
if(0<cmp(&a,&b))
shunxu=false;

memset(index,0,(max+1)*sizeof(int));

for(int i=0;i<leng;i++)
index[p[i]]++;

for(int i=1;i<=max;i++)
index[i]+=index[i-1];

for(int i=leng-1;i>=0;i--)
{
if(shunxu)
data[index[p[i]]-1]=p[i];
else
data[leng-index[p[i]]]=p[i];
index[p[i]]--;
}

return data;
}

void paixu_dui(int* p,int leng,int (* cmp)(const void* a,const void* b))
{
int data;
for(int i=leng/2;i>=0;i--)
dui_jian(p,i,leng,cmp);

for(int i=leng-1;i>0;i--)
{
data=p[0];
p[0]=p[i];
p[i]=data;
dui_jian(p,0,i-1,cmp);
}

return;
}

void dui_jian(int* p,int s,int leng,int (* cmp)(const void* a,const void* b))
{
int data=p[s];

for(int i=2*s;i<leng;i*=2)
{
if(i<leng&&0>cmp((p+i),(p+i+1)))
i++;
if(0<=cmp(&data,(p+i)))
break;
p[s]=p[i];
s=i;
}
p[s]=data;
return;
}

void paixu_geshibai(int* p,int leng,int (* cmp)(const void* a,const void* b))
{
int max=1;
int x=1;
int n=0;
int p_index=0;
int* p_data[10];
int data_index[10]={0};
bool max_xunzhao=true;

bool shunxu=true;
int a=1;
int b=2; 
if(0<cmp(&a,&b))
shunxu=false;

for(int i=0;i<10;i++)
p_data[i]=new int[leng];

while(x<=max)
{
for(int i=0;i<leng;i++)
{
if(max_xunzhao)
if(max<p[i])
max=p[i];
if(x>p[i])
p_data[0][data_index[0]++]=p[i];
else
{
n=(p[i]/x)%10;
p_data[n][data_index[n]++]=p[i];
}
}
if(shunxu)
for(int i=0;i<10;i++)
{
for(int j=0;j<data_index[i];j++)
p[p_index++]=p_data[i][j];
data_index[i]=0;
}
else
for(int i=9;i>=0;i--)
{
for(int j=0;j<data_index[i];j++)
p[p_index++]=p_data[i][j];
data_index[i]=0;
}
x*=10;
p_index=0;
max_xunzhao=false;
}
return;
}

int paixu_fangfa(const void* a,const void* b)
{
return *(int*)a-*(int*)b;
}



备注版~~~

排序_PK.rar (4.12 KB, 下载次数: 17, 售价: 3 鱼币)

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

raotf
 楼主| 发表于 2011-7-6 14:39:41 | 显示全部楼层
沙发自己做~~~
没注释是偶的一贯作风~~~
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

仰望天上的光
发表于 2011-7-6 14:46:50 | 显示全部楼层
（1）这些排序方法不实用，建议参考qsort函数，实现一个增强版本的qsort函数，可以指定排序算法。
（2）这些都是基于比较的排序，速度太慢，还可以加上 计数排序，基数排序  这些非基于比较的速度更快的排序法。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

LNH_Sniper
发表于 2011-7-6 18:58:52 | 显示全部楼层
raotf 发表于 2011-7-6 14:39

                               
登录/注册后可看大图

沙发自己做~~~
没注释是偶的一贯作风~~~

执行效率，相信在学的时候，已经有所了解了。应用到实际问题中吧。
与君共勉
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

服气
发表于 2011-7-6 22:48:08 | 显示全部楼层
额 楼主写代码时加上注释好不？  我看着头晕哈
不过效率都不高 还是多看看算法吧 我也正在学呢
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

raotf
 楼主| 发表于 2011-7-10 22:45:53 | 显示全部楼层
本帖最后由 raotf 于 2011-7-10 22:47 编辑
仰望天上的光 发表于 2011-7-6 14:46

                               
登录/注册后可看大图

（1）这些排序方法不实用，建议参考qsort函数，实现一个增强版本的qsort函数，可以指定排序算法。
（2）这 ...


我擦~~~~
指定排序方法!!!!!!!!!
快排竟然需要多用近5倍时间~~~~
本来只需qsort的1/3左右,加后就比qsort慢多了~~~~

然后问下想把比较类型int*改为void*
就是不知道怎么索引和交换数据
比如说
我想把p [ i ] [i]和p[i+1]的数据交换
但不知道p是结构体还是整型该怎么弄......
先谢了

[/i]
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

raotf
 楼主| 发表于 2011-7-10 22:51:46 | 显示全部楼层
服气 发表于 2011-7-6 22:48

                               
登录/注册后可看大图

额 楼主写代码时加上注释好不？  我看着头晕哈
不过效率都不高 还是多看看算法吧 我也正在学呢

效率都不高????
那排序什么高啊~~~
最常用的应该是快排把
非比较的排序好像都有局限性啊!!!
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

Be_envious
发表于 2011-7-11 17:22:20 | 显示全部楼层
楼主 有点折腾人啊 下次 直接发二进制码 比较好
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

raotf
 楼主| 发表于 2011-7-11 23:06:20 From FishC Mobile | 显示全部楼层
Be_envious 发表于 2011-7-11 17:22  楼主 有点折腾人啊 下次 直接发二进制码 比较好

好吧-_-
有时间我就把备注加上
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

cqk2980
发表于 2013-5-17 13:43:25 | 显示全部楼层
无回帖，不论坛，这才是人道。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

我挖
发表于 2013-7-2 21:31:56 | 显示全部楼层
看帖，回复支持下
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

fishmo
发表于 2013-7-2 23:43:59 | 显示全部楼层
看看老帖，支持下
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

fishmo
发表于 2013-7-3 16:20:36 | 显示全部楼层
万恶的回复啊
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

都市小矮人
发表于 2013-7-3 16:50:02 | 显示全部楼层
强烈支持！！！
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

★→初始化
发表于 2013-7-3 16:56:48 From FishC Mobile | 显示全部楼层
谢谢分享！
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-24 06:12

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表