当前位置：网站首页>通用型冒泡、选择、插入、希尔、快速排序的代码实现
通用型冒泡、选择、插入、希尔、快速排序的代码实现
2022-04-23 06:18:00 【发呆的小球童】
通用型冒泡、选择、插入、希尔、快速排序的代码实现
/************************************************************************* > File Name: sort.c > Author: xxx > Mail: xxx.com > Created Time: ************************************************************************/
#include <stdio.h>
#include <string.h>
#include <stddef.h>
//#define quicksort
#define shellsort
//#define insertsort
//#define selectsort
//#define bubblesort
#define N 8
struct T {
int a;
float d;
};
void print_arr(float * arr,size_t size);
void print_str(char ** arr,size_t size);
void print_struct(struct T * s,size_t size);
int cmpstr(const void * a,const void * b);
int cmpfun(const void * a,const void * b);
void swap(void * para1,void * para2,size_t size);
void bubble_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*));
void select_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*));
void insert_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*));
void shell_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*));
static int quick_sort_recursive(void *arr,int first,int end,size_t size,int (*compar)(const void*, const void*));
int quick_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*));
float values[] = {
22.7,12.5,51.8,51.3,2,90.9,33,67};
char * straa[] = {
"zhangsan","lisi","wangerma","xiaoming","baijuyi","anji","pita","nini"};
struct T strudata[] = {
{
51,51.3},
{
23,23.4},
{
89,89.6},
{
100,100.1},
{
55,55.7},
{
67,67.08},
{
45,45.7},
{
11,11.9}
};
//print_arr
void print_arr(float * arr,size_t size)
{
int i;
for( i = 0; i < size; i++)
{
printf("%-4.1f ",arr[i]);
}
printf("\n");
}
//print_str
void print_str(char ** arr,size_t size)
{
int i;
for( i = 0; i < size; i++)
{
printf("%s\n",*(arr + i));
}
}
//print_struct
void print_struct(struct T * s,size_t size)
{
int i;
for( i = 0; i < size; i++)
{
printf("%d: %.1f\n",s[i].a,s[i].d);
}
}
//compare
int cmpfun(const void * a,const void * b)
{
const float *aa = (float *)a;
const float *bb = (float *)b;
return (*aa > *bb) - (*aa < *bb);
}
//compare_string
int cmpstr(const void * a,const void * b)
{
char **pt1 = (char **)a;
char **pt2 = (char **)b;
return strcmp(*pt1,*pt2);
}
int cmpT_by_d(const void * a,const void * b)
{
struct T * pt1 = (struct T *) a;
struct T * pt2 = (struct T *) b;
return (pt1->d > pt2->d) - (pt1->d < pt2->d);
}
//swap memory
void swap(void * para1,void * para2,size_t size)
{
char buff[size];
char *a = (char *)para1;
char *b = (char *)para2;
memcpy(buff,a,size);
memcpy(a,b,size);
memcpy(b,buff,size);
}
//bubble_sort
void bubble_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*))
{
int i,j;
char *basetemp = (char *)base;
char buff[size];
for(i = 0 ; i < nitems -1; i++)
{
for(j = 0; j <nitems - i -1;j++ )
{
if(compar((basetemp + (j*size)),(basetemp + (j + 1)*size)) > 0)
{
memcpy(buff,basetemp + (j*size),size);
memcpy(basetemp + (j*size),basetemp + (j + 1)*size,size);
memcpy(basetemp + (j + 1)*size,buff,size);
}
}
}
}
//select_sort
void select_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*))
{
int i,j,min;
char *basetemp = (char *)base;
//printf("%p %p\n",base + 1,base + 2);
for(i = 0; i < nitems - 1;i++)
{
min = i;
for(j = i + 1; j < nitems;j++ )
{
//printf("%d \n",(*cmpfun)((base1 + (min*size)),(base1 + (j*size))));
if(compar(basetemp + min*size,basetemp + j*size) > 0)
{
min = j;
}
}
//printf("%d %d\n",min,i);
if( min != i)
{
swap(basetemp + min*size,basetemp + i*size,size);
}
}
}
//insert_sort
void insert_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*))
{
int i,j;
char buff[size];
char *basetemp = (char*)base;
for(i = 1; i < nitems;i++)
{
if(compar(basetemp + (i - 1)*size,basetemp + i*size) > 0 )
{
memcpy(buff,basetemp + i * size,size);
for(j = i -1; (j >= 0) && compar(basetemp + j * size,buff) > 0;j--)
{
// printf("%d\n",j);
memcpy(basetemp + (j + 1)*size,basetemp + j*size,size);
}
//printf("--------\n");
memcpy(basetemp + (j + 1)*size,buff,size);
}
}
}
//shell_sort
void shell_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*))
{
int i,j,inc;
char buff[size];
char *basetemp = (char *)base;
for(inc = nitems >> 1; inc >= 1;inc >>= 1)
{
for(i = inc; i < nitems; i ++)
{
if(compar(basetemp + (i - inc)*size,basetemp + i*size) > 0 )
{
memcpy(buff,basetemp + i * size,size);
for(j = i - inc; (j >= 0) && compar(basetemp + j * size,buff) > 0;j -= inc)
{
memcpy(basetemp + (j + inc)*size,basetemp + j*size,size);
}
memcpy(basetemp + (j + inc)*size,buff,size);
}
}
// printf("increment:%d\n",inc);
// print_arr(values,N);
}
}
//quick_sort_recursive
static int quick_sort_recursive(void *arr,int first,int end,size_t size,int (*compar)(const void*, const void*))
{
int i = first;
int j = end;
int pivot;
char * arrtemp = (char *)arr;
while( i < j)
{
while( i < j && (compar(arrtemp + j*size,arrtemp + i*size) >= 0))
j--;
if( i < j)
{
swap(arrtemp + i*size,arrtemp + j*size,size);
i++;
}
while( i < j && (compar(arrtemp + j*size,arrtemp + i*size) >= 0))
i++;
if(i < j)
{
swap(arrtemp + i*size,arrtemp + j*size,size);
j--;
}
}
pivot = i;
if(first < end)
{
quick_sort_recursive(arrtemp,first,pivot-1,size,compar);
quick_sort_recursive(arrtemp,pivot+1,end,size,compar);
}
return 0;
}
//quick_sort
int quick_sort(void * base,size_t nitems,size_t size,int (*compar)(const void*, const void*))
{
quick_sort_recursive(base,0,nitems-1,size,compar);
return 0;
}
//main
int main(int argc, const char *argv[])
{
printf("排序前：\n");
print_arr(values,N);
print_str(straa,N);
print_struct(strudata,N);
printf("------------------------------------------\n");
#ifdef quicksort
quick_sort(values,N,sizeof(float),cmpfun);
quick_sort(straa,N,sizeof(char *),cmpstr);
quick_sort(strudata,N,sizeof(struct T),cmpT_by_d);
#endif
#ifdef shellsort
shell_sort(values,N,sizeof(float),cmpfun);
shell_sort(straa,N,sizeof(char *),cmpstr);
shell_sort(strudata,N,sizeof(struct T),cmpT_by_d);
#endif
#ifdef insertsort
insert_sort(values,N,sizeof(float),cmpfun);
insert_sort(straa,N,sizeof(char *),cmpstr);
insert_sort(strudata,N,sizeof(struct T),cmpT_by_d);
#endif
#ifdef selectsort
select_sort(values,N,sizeof(float),cmpfun);
select_sort(straa,N,sizeof(char *),cmpstr);
select_sort(strudata,N,sizeof(struct T),cmpT_by_d);
#endif
#ifdef bubblesort
bubble_sort(values,N,sizeof(float),cmpfun);
bubble_sort(straa,N,sizeof(char *),cmpstr);
bubble_sort(strudata,N,sizeof(struct T),cmpT_by_d);
#endif
printf("排序后：\n");
print_arr(values,N);
print_str(straa,N);
print_struct(strudata,N);
}
版权声明
本文为[发呆的小球童]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_44548016/article/details/116954346
边栏推荐
猜你喜欢
随机推荐
关于短视频技术轮廓探讨
带您遨游太空，美摄科技为航天创意小程序提供全面技术支持
可视化常见问题解决方案（七）画图刻度设置解决方案
北峰油气田自组网无线通信对讲系统解决方案
关于短视频平台框架搭建与技术选型探讨
Metro wireless intercom system
《Attention in Natural Language Processing》翻译
“泉”力以赴·同“州”共济|北峰人一直在行动
以智能生产引领行业风潮！美摄智能视频生产平台亮相2021世界超高清视频产业发展大会
自定义classloader并实现热部署-使用loadClass
美摄助力百度“度咔剪辑”，让知识创作更容易
quill-editor图片缩放、在一个页面使用多个富文本框、quill-editor上传图片地址为服务器地址
JDBC连接池
PyTorch 11. Regularization
Solution of emergency communication system for major security incidents
美摄科技受邀LVSon2020大会 分享《AI合成虚拟人物的技术框架与挑战》
PyTorch 18. torch. backends. cudnn
可视化之路（十）分割画布函数详解
go iris框架实现多服务Demo：通过（监听8083端口的）服务1中的接口启动（监听8084端口的）服务2
城市应急管理|城市突发事故应急通信指挥调度系统