作者简介:დ旧言~,目前大一,现在学习Java,c,Python等
座右铭:松树千年终是朽,槿花一日自为荣。
望小伙伴们点赞👍收藏✨加关注哟💕💕
C语言实现快排☺️
ℹ️为了追求能在最短的时间中做更多的事情,更加便捷。从最早的马车,到🛻,其次到🛤,最后到🛩。都是为了便捷而发明的工具,而C语言中人们也发明更加便捷的排序,我们称之为------快排。🫤🫤🫤
ℹ️我们最初认识的冒泡法,逻辑简单,但是使用起来单一,占据更多内存,冒泡法的短板及其明显。而快排逻辑复杂,可以解决多种排序问题,并且占据少量的内存。大家跟上我的步伐,一起来看看C语言的快排到底是个啥🏂
💤使用快排
1️⃣快排知识
我们知道快排这个函数有四个参数void* base, size_t num, size_t size,int (compar)(const void,const void*)
🔹void* base:指向需要排序的数组的第一个元素地址。
🔹size_t num:排序的元素个数。
🔹size_t size:一个元素的大小单位字节数。
🔹int (compar)(const void,const void*):是一个函数指针,指向有两个参数,参数类型为const void*
🔹void*:无具体类型的指针,可以接受任意类型指针。(不能直接解引用操作,也不能直接进行指针运算)
2️⃣快排使用
调用qsort函数方法为:qsort(arr,sizeof(arr)/sizeof(arr[0]),sizeof(int),int_cmp)
▪️第一个参数:为数组名
▪️第二个参数:数组元素个数
▪️第三个参数:数组类型大小
▪️第四个参数:调用一个比较函数(比较函数需要自己实现)
3️⃣举个栗子
🚩排一个整数数组
▫️写出主函数
▫️在主函数调用 qsort 函数
▫️模拟实现比较函数
上代码🙉🙉🙉文章来源:https://www.toymoban.com/news/detail-562780.html
#include<stdio.h>
#include<stdlib.h>//快排函数的头文件
#include<string.h>
//排一个整数数组
int int_cmp(const void* p1,const void* p2)
{
return *(int*)(p1)-*(int*)(p2);
}
void test1()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
//调用快排函数
qsort(arr, sz, sizeof(arr[0]), int_cmp);
//打印
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
//排序整数数组
test1();
return 0;
}
🚩排一个结构体中的 age
▫️写出主函数
▫️在主函数调用 qsort 函数
▫️模拟实现比较函数
上代码🙉🙉🙉
#include<stdio.h>
#include<stdlib.h>//快排函数的头文件
#include<string.h>
//排一个结构体
struct stu
{
char name[20];
int age;
};
int struct_cmp(const void* p1, const void* p2)
{
return strcmp(((struct stu*)p1)->name, ((struct stu*)p2)->name);
}
void test3()
{
struct stu arr[3] = { {"zhangsan",20},{"lisi",19},{"wangwu",18} };
int sz = sizeof(arr) / sizeof(arr[0]);
//调用快排函数
qsort(arr, sz, sizeof(arr[0]), struct_cmp);
//打印
int i = 0;
for (i = 0; i < 3; i++)
{
printf("%s %d\n", arr[i].name, arr[i].age);
}
}
int main()
{
//排一个结构体中的age
test3();
return 0;
}
💤模拟快排
为了更加深入快排知识,我们来模拟这个函数🤪🤪🤪
1️⃣模拟快排方法
💦写出主函数
💦主函数调用模拟的快排函数**(这里需要调用交换函数,返回值函数)**
💦写出返回值函数
2️⃣模拟快排知识
🚩返回值函数
这里的返回值函数就和上面的调用比较函数一样
//整数函数比较函数
int int_cmp(const void* p1,const void* p2)
{
return *(int*)(p1)-*(int*)(p2);
}
//结构体函数比较函数
int struct_cmp(const void* p1, const void* p2)
{
return strcmp(((struct stu*)p1)->name, ((struct stu*)p2)->name);
}
🚩交换函数
因为需要满足每种类型的交换,因此不可能交换类型,只能交换每一个字节大小,
我们知道,char的字节数为一个字节,这样的话,我们可以把每种类型都转换成char类型大小,就可以实现字节进行交换。
调用交换函数实参:(char*)arr + j * size(强转成char类型,偏移一个元素类型大小)
void Swap(char* p1, char* p2,int size)
{
int i = 0;
char tmp = 0;
for (i = 0; i < size; i++)
{
tmp = *p1;
*p1 = *p2;
*p2 = tmp;
p1++;
p2++;
}
}
🚩调用快排函数
🔹调用快排函数为四个参数
- ▪️第一个参数:为数组名
▪️第二个参数:数组元素个数
▪️第三个参数:数组类型大小
▪️第四个参数:调用一个比较函数(比较函数需要自己实现)
🔹先一个元素交换,后面一个元素字节数交换(采用两个for循环)
上代码🙉🙉🙉
void bubble_sort(void* arr, int sz, int size, int(*cmp_int)(void*, void*))
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
int j = 0;
for (j = 0; j < sz - i - 1; j++)
{
if (cmp_int( (char*)arr + j*size , (char*)arr + (j + 1)*size ) > 0)
{
Swap((char*)arr + j * size, (char*)arr + (j + 1) * size, size);
}
}
}
}
3️⃣举个栗子
🚩排一个整数数组
//返回值函数
int cmp_int(const int* p1, const int* p2)
{
return *(int*)(p1)-*(int*)(p2);
}
//交换函数
void Swap(char* p1, char* p2,int size)
{
int i = 0;
char tmp = 0;
for (i = 0; i < size; i++)
{
tmp = *p1;
*p1 = *p2;
*p2 = tmp;
p1++;
p2++;
}
}
//模拟快排
void bubble_sort(void* arr, int sz, int size, int(*cmp_int)(void*, void*))
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
int j = 0;
for (j = 0; j < sz - i - 1; j++)
{
if (cmp_int( (char*)arr + j*size , (char*)arr + (j + 1)*size ) > 0)
{
Swap((char*)arr + j * size, (char*)arr + (j + 1) * size, size);
}
}
}
}
//排序整数数组
void test1()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
//打印
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
//实现qsort模拟之排序整数数组
test1();
return 0;
}
🚩排一个结构体中的 age
//返回值函数
struct stu//定义结构体
{
char name[20];
int age;
};
int cmp_struct(const int* p1, const int* p2)
{
return strcmp(((struct stu*)p1)->name, ((struct stu*)p2)->name);
}
//交换函数
void Swap(char* p1, char* p2,int size)
{
int i = 0;
char tmp = 0;
for (i = 0; i < size; i++)
{
tmp = *p1;
*p1 = *p2;
*p2 = tmp;
p1++;
p2++;
}
}
//模拟快排
void bubble_sort(void* arr, int sz, int size, int(*cmp_int)(void*, void*))
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
int j = 0;
for (j = 0; j < sz - i - 1; j++)
{
if (cmp_int( (char*)arr + j*size , (char*)arr + (j + 1)*size ) > 0)
{
Swap((char*)arr + j * size, (char*)arr + (j + 1) * size, size);
}
}
}
}
//排序结构体age
void test2()
{
struct stu arr[3] = { {"zhangsan",20},{"lisi",19},{"wangwu",18} };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz, sizeof(arr[0]), cmp_struct);
//打印
int i = 0;
for (i = 0; i < 3; i++)
{
printf("%s %d\n", arr[i].name, arr[i].age);
}
}
int main()
{
//实现qsort模拟之排序结构体age
test2();
return 0;
}
💤结束语🎉🎉🎉
今天内容就到这里啦,时间过得很快,大家沉下心来好好学习,会有一定的收获的,大家多多坚持,嘻嘻,成功路上注定孤独,因为坚持的人不多。那请大家举起自己的小说给博主一键三连,有你们的支持是我最大的动力💞💞💞,回见。
文章来源地址https://www.toymoban.com/news/detail-562780.html
到了这里,关于快快快快快快快快快快排的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!