快快快快快快快快快快排

编程入门行业动态更新时间:2024-10-13 14:27:10

快快快快快快快快快快排

作者简介：დ旧言~，目前大一，现在学习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 函数
▫️模拟实现比较函数

上代码🙉🙉🙉

#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()
{//排一个结构体中的agetest3();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模拟之排序结构体agetest2();return 0;
}