论坛 › 数据结构与算法 › 各种排序(你懂的?)

raotf 发表于 2011-7-6 14:34:47

各种排序(你懂的?)

本帖最后由 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;
int p;
int i;
double yongshi;
double paixu_time={0};
char* paixu_str[]={"插入排序","快速排序","归并排序","冒泡排序","选择排序"};

srand(time(0));
for(i=0;i<MAX;i++)
data=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);
//data_shuchu(p,MAX);
paixu_time+=yongshi;
printf("%s排序用时: %lf秒\n",paixu_str,yongshi);
if(4==i%5)
printf("\n");
}

for(int j=0;j<5;j++)
printf("%s平均用时: %lf秒\n",paixu_str,paixu_time/(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);
}
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;
int* you_data=new int;

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;

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_data;
while(you<you_leng)
data=you_data;

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;
p=p;

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;
int* p=new int;
int i;
double yongshi;
double paixu_time={0};
char* paixu_str={"插入排序","快速排序","归并排序","冒泡排序","选择排序","希尔排序","计数排序","基数排序","堆排序 ","QSORT "};

srand(time(0));
for(i=0;i<MAX;i++)
data=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+=yongshi;

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

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

for(int j=0;j<FANGFASHU;j++)
printf("%s平均用时: %lf\n",paixu_str,paixu_time/(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);
}
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;
int* you_data=new int;

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;

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_data;
while(you<you_leng)
data=you_data;

return data;
}

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

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

stack=index+1;
stack=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;
p=p;

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;
index=i-n;
while(index>=0&&0>cmp(&data,(p+index)))
{
p=p;
index-=n;
}
p=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)
max=p;

int* index=new int;
int* data=new int;
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]++;

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

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

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;
p=p;
p=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;

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=p;
s=i;
}
p=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;
int data_index={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=new int;

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

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



备注版~~~

raotf 发表于 2011-7-6 14:39:41

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

仰望天上的光 发表于 2011-7-6 14:46:50

（1）这些排序方法不实用，建议参考qsort函数，实现一个增强版本的qsort函数，可以指定排序算法。
（2）这些都是基于比较的排序，速度太慢，还可以加上 计数排序，基数排序这些非基于比较的速度更快的排序法。

LNH_Sniper 发表于 2011-7-6 18:58:52

raotf 发表于 2011-7-6 14:39 static/image/common/back.gif
沙发自己做~~~
没注释是偶的一贯作风~~~

执行效率，相信在学的时候，已经有所了解了。应用到实际问题中吧。
与君共勉

服气 发表于 2011-7-6 22:48:08

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

raotf 发表于 2011-7-10 22:45:53

本帖最后由 raotf 于 2011-7-10 22:47 编辑

仰望天上的光 发表于 2011-7-6 14:46 http://bbs.fishc.com/static/image/common/back.gif
（1）这些排序方法不实用，建议参考qsort函数，实现一个增强版本的qsort函数，可以指定排序算法。
（2）这 ...

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

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

raotf 发表于 2011-7-10 22:51:46

服气 发表于 2011-7-6 22:48 static/image/common/back.gif
额 楼主写代码时加上注释好不？我看着头晕哈
不过效率都不高 还是多看看算法吧 我也正在学呢

效率都不高????
那排序什么高啊~~~
最常用的应该是快排把
非比较的排序好像都有局限性啊!!!

Be_envious 发表于 2011-7-11 17:22:20

楼主 有点折腾人啊 下次 直接发二进制码 比较好

raotf 发表于 2011-7-11 23:06:20

Be_envious 发表于 2011-7-11 17:22楼主 有点折腾人啊 下次 直接发二进制码 比较好

好吧-_-
有时间我就把备注加上

cqk2980 发表于 2013-5-17 13:43:25

无回帖，不论坛，这才是人道。

我挖 发表于 2013-7-2 21:31:56

看帖，回复支持下

fishmo 发表于 2013-7-2 23:43:59

看看老帖，支持下

fishmo 发表于 2013-7-3 16:20:36

万恶的回复啊

都市小矮人 发表于 2013-7-3 16:50:02

强烈支持！！！

★→初始化 发表于 2013-7-3 16:56:48

谢谢分享！

查看完整版本: 各种排序(你懂的?)