首页 > 其他分享 >qsort函数

qsort函数

时间:2023-09-29 16:31:54浏览次数:48  
标签:arr const 函数 int void qsort cmp

(目录)

1.什么是qsort函数

我们以前学习过的一些排序算法,如冒泡、希尔、快排等等,它们速度有快有满,但是这些排序都只能排序一种类型的变量,如果想排序另一种变量就需要另写一个排序, 那么有没有什么排序是“万能的”呢,什么类型数据都能排的呢?

答案就是qsort函数

qsort函数实现了一种快速排序算法,对一个由n个元素组成的数组进行排序,每个元素的宽度为字节。参数base是一个指向要排序的数组基数的指针,qsort用排序后的元素覆盖这个数组。参数compare是一个指向用户提供的例程的指针,用于比较两个数组元素并返回一个指定它们之间关系的值。

这是qsort函数的官方定义: 在这里插入图片描述

这个函数有四个参数

  • 第一个参数base是待排数组的起始地址
  • 第二个参数num是数组的元素个数,也就是数组的大小
  • 第三个参数width是一个元素的大小,单位是字节,也就是一个元素所占大小
  • 第四个参数compare是一个函数指针,这个参数较为复杂,接下来我们展开讲

在排序中,比较整形或比较浮点型可以用大于,小于,等于;比较两个字符串可以用strcmp函数;但是如果比较两个结构体怎么比较,按照结构体中哪个元素进行比较呢?所以不同类型的元素应用不同的方法去比较

这也就是compare这个函数干的事,在这个函数里,我们自己写两个元素应该怎么比较 将compare这个函数指针传回qsort函数,qsort就会按照compare函数中比较的方法,对数组中元素进行比较

compare函数中,elem1指的是要比较的两个元素中第一个元素的地址,elem2是另一个要比较的元素的地址,因为这个函数官方在定义的时候,并不知道要比较什么类型的元素,所以用void*类型.

compare函数是有返回值的: 在这里插入图片描述

  • elem1小于elem2,返回负数
  • elem1大于elem2,返回正数
  • elem1等于elem2,返回0

按照comparer函数的定义,数组以递增的顺序进行排序。要按递减顺序对数组进行排序,颠倒comparer函数中 "大于 "和 "小于 "的含义。


2.实现一个qsort函数

有一个存放int类型变量的数组arr

int arr[10] = { 10,9,8,7,6,5,4,3,2,1 };

然后使用qsort函数

  • 第一个参数是数组名arr
  • 第二个参数是数组长度int size = sizeof(arr) / sizeof(arr[0]);
  • 第三个参数是一个元素的大小sizeof(arr[0])
  • 第四个参数是函数指针cmp_int

cmp_int函数中,因为传的参数是void*类型,并且待排数组是int类型的,所以在比较函数中,需要将void*类型的变量强制转换成int*类型的指针再进行解引用

如果是排升序,就按照cmp_int函数中参数的顺序将两个指针解引用后相减,否则就颠倒两个指针的顺序

代码如下:

#include <stdio.h>

int cmp_int(const void* e1, const void* e2)
{
	//排升序
	return *(int*)e1 - *(int*)e2;

	//排降序
	//return *(int*)e2 - *(int*)e1;
}

int main()
{
	int arr[10] = { 10,9,8,7,6,5,4,3,2,1 };
	int size = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, size, sizeof(arr[0]), cmp_int);
	
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);

	}
}

3.用qsort函数排序一个结构体

下面我们用qsort排序一个结构体 结构体如下:

struct stu
{
	int age;
	char name[10];
};

然后使用qsort函数,结构体中有整形和字符串两个元素,这两个元素都可以进行比较和排序

首先我们按照年龄来排序,比较年龄的函数命名为cmp_by_age,将两个void*类型的形参强转成struct stu*类型,访问它们的age元素并相减

int cmp_by_age(const void* e1, const void* e2)
{
	return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}

首先我们按照姓名来排序,比较年龄的函数命名为cmp_by_name,将两个void*类型的形参强转成struct stu*类型,访问它们的name元素,可以用strcmp比较字符串间的大小

int cmp_by_name(const void* e1, const void* e2)
{
	return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
}

完整代码:

#include <stdio.h>
#include <string.h>

struct stu
{
	int age;
	char name[10];
};

int cmp_by_age(const void* e1, const void* e2)
{
	return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}

int cmp_by_name(const void* e1, const void* e2)
{
	return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
}

int main()
{
	struct stu arr[3] = { {18,"jack"},{30,"andy"},{25,"ride"} };
	int size = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, size, sizeof(arr[0]), cmp_by_age); //按照年龄排序
	qsort(arr, size, sizeof(arr[0]), cmp_by_name); //按照姓名排序
	return 0;
}

4.模仿qsort的功能实现一个通用的冒泡排序

模仿qsort函数实现冒泡排序,改进后的冒泡排序的函数列表中应与qsort函数一样

void BubbleSort(void* base, size_t size,size_t width,int(*cmp)(const void* e1,const void*e2))

在以往的冒泡排序中,有两层循环,在两层循环中有一个比较两个数大小的if语句,在if语句中有一个交换语句 在改进型的冒泡中,也都是这些语句,只不过改进的是if语句中判断两个数大小和交换函数而已

在改进的冒泡排序中,比较两个元素的大小是调用额外定义出的cmp函数 但是怎么将两个待比较的元素传到cmp函数中是个问题,因为接收进来的数组是void*类型的,不知道元素具体是什么类型,无法用下标去访问所以只能将base强转成char*类型,通过指针的偏移量去访问每个元素,每两个元素中间隔着一个width字节的宽度,所以用(char*)base+j*width取出第一个元素的地址,用(char*)base+(j+1)*width取出第二个元素的地址

放到cmp函数中进行比较

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

紧接着如果两个元素需要进行交换,就要使用交换函数,还是因为不知到元素是什么类型的,所以还是一个字节一个字节得交换

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

	}
}

此时,模仿qsort函数实现冒泡排序就完成了,下面是完整代码:

#include<stdio.h>
#include <string.h>

struct stu
{
	int age;
	char name[10];
};

int cmp_by_age(const void* e1, const void* e2)
{
	return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}

int cmp_by_name(const void* e1, const void* e2)
{
	return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
}

int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}

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

	}
}

void BubbleSort(void* base, size_t size,size_t width,int(*cmp)(const void* e1,const void*e2))
{
	int i = 0;
	for (i = 0; i < size-1; i++)
	{
		int j = 0;
		for (j = 0; j < size - i - 1; j++)
		{
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width)>0)
			{
				swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}

void test1()
{
	int arr[10] = { 10,9,8,7,6,5,4,3,2,1 };
	int size = sizeof(arr) / sizeof(arr[0]);
	BubbleSort(arr, size, sizeof(arr[0]), cmp_int);
}

void test2()
{
	struct stu arr[3] = { {18,"jack"},{40,"andy"},{35,"mary"} };
	int size = sizeof(arr) / sizeof(arr[0]);
	BubbleSort(arr, size, sizeof(arr[0]), cmp_by_age);//按照年龄排序
	BubbleSort(arr, size, sizeof(arr[0]), cmp_by_name);//按照姓名排序
}

int main()
{
	test1();

	test2();
}

标签:arr,const,函数,int,void,qsort,cmp
From: https://blog.51cto.com/u_16237630/7650711

相关文章

  • 【代码片段】makefile 中通过 shell 函数执行 sed
    作者:张富春(ahfuzhang),转载时请注明作者和引用链接,谢谢!cnblogs博客zhihuGithub公众号:一本正经的瞎扯先上代码:(在macos上调试通过)#defineashellfunctiontosetdebugmodetoreleasemode#whenosismacbook,usegsedasseddefinefunction_sed_set_rel......
  • 前端 toFixed()函数
    toFixed()函数:可把Number四舍五入为指定小数位数的数字。toFixed()中的参数就是需要取的小数位数,0表示不留小数点VarNumber=3.1415926Number.toFixed(2);//输出3.14Number.toFixed(0);//输出3VarNumber=18.888;Number.toFixed(0);//输出19......
  • python基础:函数和参数
    一函数1函数的文档字符串函数内的第一条语句是字符串时,该字符串就是文档字符串,用于对函数进行说明利用文档字符串可以自动生成在线文档或打印版文档,建议在工作中习惯加入文档字符串,否则时间一长,自己可能都不知道函数是干嘛,更不用说其他人了如上,利用__doc__属性,可以输出函数......
  • Numba 库中的一个装饰器函数numba.jit
    numba.jit 是Numba库中的一个装饰器函数,用于实现即时编译(Just-In-TimeCompilation)的功能。它可以将Python函数转换为高性能的机器码,从而提供更快的执行速度。使用 numba.jit 装饰器可以将普通的Python函数转换为被Numba优化的函数。当使用 numba.jit 装饰器修饰一......
  • OI 超几何函数入门
    第一章定义超几何函数\[F(a_1,a_2\dotsa_n;b_1,b_2\dotsb_m;z)=\sum_{k\ge0}\frac{a_1^{\overline{k}}\dotsa_n^{\overline{k}}z^k}{b_1^{\overlinek}\dotsb_n^{\overlinek}k!}\]其中\(b_i\)不为非正的整数。举出若干简单例子:\[F(1;1;z)=e^z,F(1,1;1;z)=\frac{1}{1......
  • 无涯教程-JavaScript - CONCATENATE函数
    描述CONCATENATE函数将两个或多个文本字符串连接为一个字符串。在Excel2016中,CONCATENATE函数已被CONCAT函数替换。CONCATENATE函数仍可用于向后兼容。语法CONCATENATE(text1,[text2]...)争论Argument描述Required/Optionaltext1Thefirstitemtojoin.Theit......
  • 无涯教程-JavaScript - CONCAT函数
    描述Combinesthetextfrommultiplerangesand/orstrings,butitdoesn'tprovidethedelimiterorIgnoreEmptyarguments.Toincludedelimiters(suchasspacingorampersands(&)betweenthetextsyouwanttocombineandtoremoveemptyarguments......
  • 函数分类与使用
    函数:函数头和函数体。可以带参数,可以返回值。1.函数分类带参函数和无参函数;有返回值函数和无返回值函数;数值函数、日期与时间函数、逻辑函数、字符串函数、存储空间分配函数、文件函数、输入与输出函数等;系统函数和用户函数。2.系统函数和用户函数系统函数由C语言......
  • 标准输出函数printf()的使用
    1.printf()函数的来历和作用printf()函数是系统函数,标准输出函数,向显示器屏幕窗口输出数据。需要在程序文件的开始使用#include包含命令,包含stdio.h。2.printf()函数格式函数原型声明语句格式(包含在stdio.h头文件中):intprintf(<字符指针参数>,<形式参数表>);函数调用格式(......
  • 标准输入函数scanf()的使用
    1.scanf()函数的来历和作用标准输入函数scanf()也是系统函数,从标准输入设备键盘输入各种类型的数据,给程序中的变量赋值。在使用scanf()函数调用前,也要使用#include命令包含stdio.h。2.scanf()函数格式函数原型声明语句格式:intscanf(<字符指针参数>,<形式参数表>);函数调用......