[C语言] 各种排序—你都会吗（计数排序,基数排序，快速排序，...） [复制链接]

raotf

版主

Rank: 12

主题: 18
帖子: 326
C币: 1431 枚
在线时间: 238 小时

发表于 2011-8-16 15:52:18 |显示全部楼层

分享到：

共包含
"插入排序","快速排序","归并排序","冒泡排序","选择排序","希尔排序","计数排序","基数排序","堆排序 "

#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 //qsort函数
#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_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));
//上面是各种不同排序的实现函数
// int* p----要排序的数组
// int leng-----数组的长度
// int (* cmp)(const void* a,const void* b)-------排序方法函数的指针
int paixu_fangfa(const void* a,const void* b); //指定的排序方法
double pk_paixu(int* p,int leng,int style,int (* cmp)(const void* a,const void* b));
//排序并返回所用时间
//int style-----指定用什么方法排序
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++) //每种方法调用3次
{
if(0==i%FANGFASHU)
printf("第%d轮:\n",i/FANGFASHU+1);
data_fuzhi(p,data,MAX); //把data里德数据复制给p
//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;
}
//根据style传来的的值对号入座,调用不同的方法排序
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) //长度小于等于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);
//用传进来的数据p分别给zuo_data\you_data变量赋值
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++;
}
}
//上面是根据比较左右两边的大小决定是谁先给data赋值,一个一个的
//直到有一边没数据了,就不用比较了~~~
while(zuo<zuo_leng)
data[zuo+you]=zuo_data[zuo++];
while(you<you_leng)
data[zuo+you]=you_data[you++];
//然后把剩下的数据直接赋值给data,只有一个while会执行,
//如果左右都有数据是跳不出上面那段循环的
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; //这里也可以用wei,因为tou=wei
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;
}
//上面把n当成1,就是插入排序了,一模一样~~~~
//最终n就是要变成1的,进行一个真正的插入排序(最后一趟)
//之所以比插入快,是因为之前的排序使最后一趟插入是不需要擦太深~~~~
}
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)); //把index中的数据初始化为0
for(int i=0;i<leng;i++)
index[p[i]]++;
//把有值的地方赋值为1
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]]--;
}
//根据index中的位置把p中的值赋值给data
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];
//为10个基数申请空间
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]; //小于x就不用计算n的值了,因为计算了也是0
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;
}
//上面是看升序还降序,决定是++还--
//把空间里的数据按顺序放回p
x*=10;
p_index=0;
max_xunzhao=false;
}
return;
}
int paixu_fangfa(const void* a,const void* b) //排序方法,是降序还升序
{
return *(int*)a-*(int*)b;
}