qsort函数

1.qsort函数是什么

1.1qsort函数的原型

2.qsort函数的使用

2.1使用qsort函数排序整型数据

2.2使用qsort排序结构数据

3.qsort函数的模拟实现

1.qsort函数是什么

很多小伙伴们都没有听说过qsort这个函数，qsort函数是C语言标准库中的一个排序函数，那么我们在使用它的时候就要在代码前包含它的头文件<stdlib.h>。它的底层逻辑快速排序算法。快速排序是一种高效的排序算法，其平均和最坏情况下的时间复杂度分别为O(n log n)和O(n^2)，但通过合理的选取中间元素作为基准（pivot），可以使得最坏情况的发生概率大大降低。它的功能其实就是将各种数据来排序。

1.1qsort函数的原型

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

这个很长很长的代码其实就是它的原型了，那这些传给它的参数都是什么呢？

base：指向要排序的数组的第一个元素的指针。
nmems：由 base 指向的数组中元素的个数。
size：数组中每个元素的大小（以字节为单位）。
compar：一个比较函数，用来比较两个元素的大小。这个函数需要返回一个负数、零或正数，分别表示第一个参数小于、等于或大于第二个参数。

由于函数的声明是void类型，所以它不会返回任何值。

比较函数compar的原型通常为：

int (*compar)(const void *p1, const void*p2)

比较函数的返回类型是int，那它应该返回什么值呢？

根据qsort函数接收的参数规则来讲，p1大于p2返回一个大于0的数字，等于则返回0，小于则返回-1，在vs的编译环境下，大于0的数通常被用1来代替。

2.qsort函数的使用

使用qsort函数时，需要注意以下几点：
1.base必须是void*类型的指针，这意味着qsort可以排序任何类型的数组，只要该类型能够转换为void*。
2.nmemb和size必须是指向数组大小和元素大小的有效指针。
3.compar函数必须是按照元素类型定义的正确比较函数。
qsort函数的使用非常灵活，它可以排序基本数据类型的数组，如整数、浮点数等；也可以排序复杂数据类型的数组，如结构体数组；甚至可以排序字符串数组。

2.1使用qsort函数排序整型数据

#include<stdio.h>
#include<stdlib.h>

void print_arr(int arr[], int sz)
{
	int i = 0;
	for (; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}
int comar_int(const void* p1, const void* p2)
{
	return *(int*)p1 - *(int*)p2;  
}
void test()
{
	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), comar_int);
	print_arr(arr, sz);
	printf("\n");

}
int main ()
{
    test();
    return 0;
}

结果为：

这里就完成了对整型数组arr的从小到大的排序。可qsort函数的能力可远不及此。

2.2使用qsort排序结构数据

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
struct Stu
{
	char name[20];
	int age;
};
int cmp_sty_by_name(const void* p1, const void* p2)
{
	return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
//使用了strcmp库函数根据ASCII码值来比较
}
int cmp_sty_by_age(const void* p1, const void* p2)
{
	return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age;
}

void test2()
{
	struct Stu arr[] = { {"zhangsan", 20}, {"lisi", 30}, {"wangwu", 15} };
	int sz = (sizeof(arr) / sizeof(arr[0]));
	qsort(arr, sz, sizeof(arr[0]), cmp_sty_by_name);
	for (int i = 0; i < sz; i++)
	{
		printf("%s ", arr[i].name);
	}
	printf("\n");
}
void test3()
{
	struct Stu arr[] = { {"zhangsan", 20}, {"lisi", 30}, {"wangwu", 15} };
	int sz = (sizeof(arr) / sizeof(arr[0]));
	qsort(arr, sz, sizeof(arr[0]), cmp_sty_by_age);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i].age);
	}
}
int main()
{
	//test();
	test2();
	test3();
	return 0;
}

结果为：