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宽度来找到数据,从而进行交换