qsort介绍与实现

qsort

qsort 是 C 标准库中的一个通用排序函数，位于 <stdlib.h> 头文件中。它可以对任意类型的数组进行排序，使用的是快速排序（Quick Sort）算法的变种。 参数说明 base：指向要排序的数组的第一个元素的指针。由于是 void* 类型，所以可以指向任意类型的数组。 num：数组中元素的个数。 size：每个元素的大小（以字节为单位）。 compar：一个指向比较函数的指针，该比较函数用于确定元素之间的顺序。比较函数的原型必须是 int (*compar)(const void *, const void *)。

比较函数介绍 比较函数的具体比较方式,需要由使用人自己去实现. 其必须接受两个参数类型为const void*的参数,返回类型为int型 其比较原理在c++官网上可以查到,如下: 如果返回值小于 0，表示第一个参数所指向的元素小于第二个参数所指向的元素。 如果返回值等于 0，表示两个元素相等。 如果返回值大于 0，表示第一个参数所指向的元素大于第二个参数所指向的元素。 使用示例

#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<string.h> struct stu { char name[20]; int age; }; //以结构体中名字大小为依据进行排序 int cmp_stu_name(const void* e1, const void* e2) { //比较字符串大小用strcmp函数 //将e1,e2强转类型进行比较 //因为strcmp比较完后返回的结果与比较函数所需返回大小一致,所以可以直接返回strcmp比较完所得值 return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name); } int main() { struct stu arr[] = { {"zhangsan",18},{"wangwu",20} };//定义两个结构体变量,用于测试qsort函数 int sz = sizeof(arr) / sizeof(arr[0]); qsort(arr, sz, sizeof(arr[0]), cmp_stu_name); for(int i = 0;i<sz;i++) printf("%s %d", arr[i].name, arr[i].age); return 0; } 自我实现

qsort函数可以通过类似于冒泡排序的方式实现;

#include<stdio.h> #include<string.h> struct stu { char name[20]; int age; }; //比较函数的自我实现,通过strcmp来比较name大小 int cmp_stu_name(const void* e1, const void* e2) { return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name); } void swap(void* p1, void* p2, int size) { //由于类型未知,所以将传过来的数据对应的字节一一调换 for (int i = 0;i < size;i++) { char tmp = *((char*)p1 + i); *((char*)p1 + i) = *((char*)p2 + i); *((char*)p2 + i) = tmp; } } //width为传过来参数的大小 cmp为回调函数 void bubble_sort(void* base, int num, int width, int (*cmp) (void* e1, void* e2)) { //调用cmp_stu_name函数,如果返回值大于0,则交换顺序 int i = 0; int j = 0; for (i = 0;i < num;i++) { int flag = 1;//如果顺序调换,则数组还是乱序,值改为0;反正有序退出循环 for (j = 0;j < num;j++) { //为了能够比较任意类型的数据,将base强转为char*类型进行比较 if ((cmp((char*)base + j * width, (char*)base + (j + 1) * width)) > 0) { swap((char*)base + j * width, (char*)base + (j + 1) * width,width); } } } } void test() { struct stu arr[] = { {"zhangsan",18},{"lisi",20} }; int sz = sizeof(arr) / sizeof(arr[0]); //模仿qsort函数的参数 bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_name); for(int i = 0;i<sz;i++) printf("%s %d\n", arr[i].name, arr[i].age); } int main() { test(); return 0; }

比较函数与qsort处同理;在此具体要实现的是qsort的内部原理,要注意的是由于使用者传来的数据是未知的,所以要转为char*类型的数据,通过width宽度来找到数据,从而进行交换