【C语言】_使用冒泡排序模拟实现qsort函数

目录

1. 排序函数的参数

2. 排序函数函数体

2.1 比较元素的表示

2.2 交换函数Swap的实现

2.3 排序函数bubble_sort的实现

3. 测试整型数据排序

3.1 整型数据比较函数cmp_int的实现

3.2 整型数据排序后输出函数print_int的实现

3.3 整型数据测试函数test_int的实现 

3.4 完整程序及运行结果 

4. 测试结构体型数据排序

4.1 创建结构体型数据

4.2 结构体型数据比较函数cmp_stu_byxxxx的实现

4.3 结构体型数据排序后输出函数print_stu的实现

4.4 结构体型数据测试函数test_stu的实现

4.5 完整程序及运行结果

---

 qsort采用快排实现，现使用冒泡进行模拟实现；

 关于排序，冒泡排序实现文章参考如下：
【C语言】_冒泡排序及其优化思路-CSDN博客https://blog.csdn.net/m0_63299495/article/details/145014576

关于qsort函数，具体使用方法文章参考如下：

【C语言】_qsort函数-CSDN博客https://blog.csdn.net/m0_63299495/article/details/145076745

1. 排序函数的参数

void bubble_sort(void* base, // 参数1：泛型指针接收待排序数组基址size_t sz,				 // 参数2：正数变量接收待排数据个数size_t width,            // 参数3：正数变量接收单个待排数据大小int(*cmp)(const void* p1,const void* p2) 
// 参数4：函数指针变量接收待排数据大小比较函数地址、
{  }

注：理解函数指针的重要作用，正是由于函数指针cmp的实现，才实现了多种类型元素的比较；

2. 排序函数函数体

2.1 比较元素的表示

1、对于冒泡排序，比较原则为相邻元素进行比较。

对于原排整型数据的冒泡排序，可使用>=<对 arr[ j ]与arr[ j+1 ]直接进行判断；

但为实现各种类型数据的排序，则需重新编写元素比较函数cmp；

2、关于相邻元素的表示，当前待排序数组基址为base，待排序元素大小为width，

对于第 j 个与第 j+1 个元素，可将base强转为char*类型后偏移对应倍数的数据元素大小width，

即表示为：(char*)base + j × width 与 (char*)base + (j+1) × width；

cmp((char*)base+j*width,(char*)base+(j+1)*width)

2.2 交换函数Swap的实现

1、对于原排整型数据的冒泡排序，可创建整型临时变量tmp对arr[ j ]与arr[ j+1 ]进行交换；

但对于多种类型数据，编写时临时变量不能确定为某一具体类型，

单独封装交换函数Swap以实现交换功能；

2、关于Swap函数的参数类型，由于已强转为char*类型，故其参数类型直接写为char*类型即可；

3、对于Swap函数，仅有待交换元素的起始指针并不能完成交换，还需提供待交换元素大小；

void Swap(char* buf1, char* buf2,size_t width) 
{  }

4、由于元素大小未知，可令待交换元素逐字节进行交换，交换元素大小width次：

void Swap(char* buf1, char* buf2,size_t width) {for (int i = 0; i < width; i++) {char* tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}

2.3 排序函数bubble_sort的实现

void bubble_sort(void* base, // 参数1：泛型指针接收待排序数组基址size_t sz,				 // 参数2：正数变量接收待排数据个数size_t width,            // 参数3：正数变量接收单个待排数据大小int(*cmp)(const void* p1,const void* p2)) {  // 参数4：函数指针变量接收待排数据大小比较函数地址// 确定趟数: // 对于sz个数，需排sz-1趟int i = 0;for (int i = 0; i < sz - 1; i++) {// 1趟排序内:// 假设该序列已经有序：int flag = 1;int j = 0;// 确定1趟内比较次数：// 对于第i趟，待排序数个数：sz-i个，需比较的数的对数：sz-1-i对for (j = 0; j < sz - 1 - i; j++) {// 比较相邻两个数据/元素：if (cmp((char*)base+j*width,(char*)base+(j+1)*width)>0) {// 交换两个元素Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);// 进入循环体发生交换<=>序列非有序，将标志重置为0：flag = 0;}}// 本趟未交换，则表示序列已经有序，终止后续趟数if (flag == 1) {break;}}
}

3. 测试整型数据排序

3.1 整型数据比较函数cmp_int的实现

int cmp_int(const void* p1, const void* p2) {return *(int*)p1 - *(int*)p2;
}

3.2 整型数据排序后输出函数print_int的实现

void print_int(int* arr, int sz) {for (int i = 0; i < sz; i++) {printf("%d ", *(arr + i));}
}

3.3 整型数据测试函数test_int的实现 

void test_int() {int arr[] = { 9,7,5,3,1,8,6,4,2,0 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr,sz,sizeof(arr[0]),cmp_int);print_int(arr, sz);
}

3.4 完整程序及运行结果 

#include<stdio.h>
int cmp_int(const void* p1, const void* p2) {return *(int*)p1 - *(int*)p2;
}
void Swap(char* buf1, char* buf2,size_t width) {for (int i = 0; i < width; i++) {char* tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}
void bubble_sort(void* base, // 参数1：泛型指针接收待排序数组基址size_t sz,				 // 参数2：正数变量接收待排数据个数size_t width,            // 参数3：正数变量接收单个待排数据大小int(*cmp)(const void* p1,const void* p2)) {  // 参数4：函数指针变量接收待排数据大小比较函数地址// 确定趟数: // 对于sz个数，需排sz-1趟int i = 0;for (int i = 0; i < sz - 1; i++) {// 1趟排序内:// 假设该序列已经有序：int flag = 1;int j = 0;// 确定1趟内比较次数：// 对于第i趟，待排序数个数：sz-i个，需比较的数的对数：sz-1-i对for (j = 0; j < sz - 1 - i; j++) {// 比较相邻两个数据/元素：if (cmp((char*)base+j*width,(char*)base+(j+1)*width)>0) {// 交换两个元素Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);// 进入循环体发生交换<=>序列非有序，将标志重置为0：flag = 0;}}// 本趟未交换，则表示序列已经有序，终止后续趟数if (flag == 1) {break;}}
}
void print_int(int* arr, int sz) {for (int i = 0; i < sz; i++) {printf("%d ", *(arr + i));}
}
void test_int() {int arr[] = { 9,7,5,3,1,8,6,4,2,0 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr,sz,sizeof(arr[0]),cmp_int);print_int(arr, sz);
}
int main() {test_int();return 0;
}

运行结果如下：

4. 测试结构体型数据排序

4.1 创建结构体型数据

typedef struct Stu {char name[20];int age;
}Stu;

4.2 结构体型数据比较函数cmp_stu_byxxxx的实现

由于结构体有多个成员变量，分别编写对应排序函数：

int cmp_stu_byname(const void* p1, const void* p2) {strcmp(((Stu*)p1)->name, ((Stu*)p2)->name);//strcmp( (*((Stu*)p1)).name, (*((Stu*)p1)).name );
}
int cmp_stu_byage(const void* p1, const void* p2) {return ((Stu*)p1)->age - ((Stu*)p2)->age;/*return (*((Stu*)p1)).age - (*((Stu*)p1)).age;*/
}

4.3 结构体型数据排序后输出函数print_stu的实现

void print_stu(Stu* arr, int sz) {for (int i = 0; i < sz; i++) {printf("name:%s, age:%d\n", arr[i].name, arr[i].age);}
}

4.4 结构体型数据测试函数test_stu的实现

void test_stu() {struct Stu arr[3] = { {"zhangsan",20},{"lisi",19},{"wangwu",21} };int sz = sizeof(arr) / sizeof(arr[0]);printf("sorted by name:\n");bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_byname);print_stu(arr, sz);printf("\n");printf("sorted by age:\n");bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_byage);print_stu(arr, sz);
}

4.5 完整程序及运行结果

#include<stdio.h>
#include<string.h>
typedef struct Stu {char name[20];int age;
}Stu;
int cmp_stu_byname(const void* p1, const void* p2) {strcmp(((Stu*)p1)->name, ((Stu*)p2)->name);//strcmp( (*((Stu*)p1)).name, (*((Stu*)p1)).name );
}
int cmp_stu_byage(const void* p1, const void* p2) {return ((Stu*)p1)->age - ((Stu*)p2)->age;/*return (*((Stu*)p1)).age - (*((Stu*)p1)).age;*/
}
void print_stu(Stu* arr, int sz) {for (int i = 0; i < sz; i++) {printf("name:%s, age:%d\n", arr[i].name, arr[i].age);}
}
void test_stu() {struct Stu arr[3] = { {"zhangsan",20},{"lisi",19},{"wangwu",21} };int sz = sizeof(arr) / sizeof(arr[0]);printf("sorted by name:\n");bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_byname);print_stu(arr, sz);printf("\n");printf("sorted by age:\n");bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_byage);print_stu(arr, sz);
}
void bubble_sort(void* base, // 参数1：泛型指针接收待排序数组基址size_t sz,				 // 参数2：正数变量接收待排数据个数size_t width,            // 参数3：正数变量接收单个待排数据大小int(*cmp)(const void* p1,const void* p2)) {  // 参数4：函数指针变量接收待排数据大小比较函数地址// 确定趟数: // 对于sz个数，需排sz-1趟int i = 0;for (int i = 0; i < sz - 1; i++) {// 1趟排序内:// 假设该序列已经有序：int flag = 1;int j = 0;// 确定1趟内比较次数：// 对于第i趟，待排序数个数：sz-i个，需比较的数的对数：sz-1-i对for (j = 0; j < sz - 1 - i; j++) {// 比较相邻两个数据/元素：if (cmp((char*)base+j*width,(char*)base+(j+1)*width)>0) {// 交换两个元素Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);// 进入循环体发生交换<=>序列非有序，将标志重置为0：flag = 0;}}// 本趟未交换，则表示序列已经有序，终止后续趟数if (flag == 1) {break;}}
}
int main() {test_stu();return 0;
}

运行结果如下：