【C语言进阶】qsort函数详解以及它的模拟实现-创新互联

目录
  • 一、qsort函数介绍
  • 二、qsort函数参数介绍
    • 2.1:void* base
    • 2.2:size_t num
    • 2.3:size_t size
    • 2.4:int(* compar)(const void *,const void *)
  • 三、实际应用
    • 3.1:利用qsort函数对整型数组排序
    • 3.2:利用qsort函数对结构体数组排序
  • 四、利用冒泡排序模拟实现qsort函数
    • 4.1:冒泡排序
    • 4.2:模拟实现qsort函数
    • 4.3:实际应用
      • 4.3.1:利用bulle_sort函数对整型数组排序:
      • 4.3.2:利用bulle_sort函数对结构体数组排序:

创新互联建站专业为企业提供海城网站建设、海城做网站、海城网站设计、海城网站制作等企业网站建设、网页设计与制作、海城企业网站模板建站服务,10余年海城做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。一、qsort函数介绍

qsort是一个库函数,可以对任意数据类型的数组进行排序。它的底层是通过快速排序来实现的
cplusplus网站中对qsort函数的解释如下:
在这里插入图片描述
qsort的函数声明:

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

qsort函数的参数:

  • void* base
  • size_t num
  • size_t size
  • int(*compar)(const void*,const void*)

qsort函数的返回值:
qsort函数的返回值void

二、qsort函数参数介绍2.1:void* base

 参数base的类型是void*(空指针),说明base是一个指针,它指向待排序数组的第一个元素,换言之:base存放的是待排序数组的首元素地址

补充:void*类型介绍:
void*是无具体指向的指针类型,任何类型变量的地址都可以存放到void型指针变量里面,这可以说是void*变量的一个优点。当然它也有一个致命的缺点:void*指针不能解引用。

为什么base的类型是void*呢?
 回到base的用途,base是用来存放待排序数组首元素的地址,既然存放的是地址,那首先base一定是一个指针类型,那为什么是void型的指针呢?这就要回到qsort函数设计的初衷,qsort函数希望实现对任何类型的数组都可以排序,这就包括:整型数组、字符数组、结构体数组等等,既然面对的排序对象是各种类型的数组,那数组首元素的类型一定也是各种各样的,比如:对整型数组进行排序,数组首元素就是整型;对字符数组排序,数组首元素就是字符型。既然数组首元素的类型可能有多种,那数组首元素的地址一定也是各种各样的,可能是整型的地址,可能是字符的地址,等等。此时就要求base能够存放各种类型的地址,因此就让basevoid*型。void*变量就可以存放各种类型的地址。假如:让baseint*型,当待排序的是字符数组,字符数组的首元素是一个字符,字符的地址就不能存到int*的变量里。

2.2:size_t num

num中存的是待排序数组的元素个数,他的类型是size_tsize_t其实就是把unsigned int重命名的得到的。

2.3:size_t size

size中存的是数组中每个元素的大小(以字节为单位)。

2.4:int(* compar)(const void *,const void *)

compar是一个函数指针类型,所谓函数指针就是可以指向一个函数,里面存放的是函数的地址。

compar到底指向什么函数呢?
 compar是英文单词compare(比较)的缩写,所以顾名思义,compar是比较的意思,说明它指向一个比较函数。

什么是比较函数?
 要实现对数组元素的排序,那一定要对数组里面的元素进行逐一比较,而对于不同类型的数组来说,它们的比较方法也有所不同。比如:整型数组可以比较它们元素之间的大小关系,而字符数组则有专门的字符串比较函数strcmp,如果是一个结构体数组,一个结构体里面有不同的数据,我们就可以按照不同的标准进行排序。就像对一群人进行排序,可以按照年龄排,也可以按照身高排等等。此时就需要用户自己确定一个排序的标准,用函数封装起来,然后把这个函数的地址传给qsort函数用函数指针compar来接收。

对比较函数的要求:
 形参compar已经规定了它所指向的函数类型是:int (const void*,const void).即:所指向的比较函数有两个void*类型的参数,函数的返回值是int型。

比较函数的参数、返回值的意义:
int compar (const void* p1, const void* p2);
 其中两个void*类型的参数p1p2用来存放数组中待比较的两个元素的地址。如果compar函数的返回值小于0,会把p1指向的元素排到p2指向的元素前面;如果返回值等于0,不会改变p1p2指向的元素位置;如果返回值大于0,会把p1指向的元素排到p2指向的元素后面。

三、实际应用3.1:利用qsort函数对整型数组排序
int comper(const void* e1, const void* e2)
//comper函数是用户自己写的,我们自己当然知道要排序的元素类型是什么
//我们就可以利用强制类型转化来实现对e1和e2的比较
{return *(int*)e1 - *(int*)e2;//void*类型不能直接解引用
}
//*(int*)e1 - *(int*)e2<0
//说明e1指向的元素比e2指向的元素小,此时刚好返回一个小于0的数,qsort就会把e1指向的元素排在e2指向的元素前面
//*(int*)e1 - *(int*)e2>0
//说明e1指向的元素比e2指向的元素大,此时刚好返回一个大于0的数,qsort就会把e2指向的元素排到e1指向的元素前面

int main()
{int arr[10] = {9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), comper);//利用库函数qsort来排序
	int i = 0;
	for (i = 0; i< sz; i++)
	{printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}
//结果:
0 1 2 3 4 5 6 7 8 9
3.2:利用qsort函数对结构体数组排序

按照年龄排序:

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

//根据名字比较
int comper_age(const void* e1, const void* e2)
{return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}

int main()
{struct Stu arr[3] = {{"zhangsan",100},{"lisi",20},{"wangwu",3} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;

	//排序前打印
	for (i = 0; i< sz; i++)
	{printf("%s %d   ", arr[i].name, arr[i].age);
	}
	printf("\n");

	//根据年龄进行排序
	qsort(arr, sz, sizeof(arr[0]), comper_age);

	
	//排序后打印
	for (i = 0; i< sz; i++)
	{printf("%s %d   ", arr[i].name, arr[i].age);
	}
	printf("\n");
	return 0;
}
//结果:
zhangsan 100   lisi 20   wangwu 3
wangwu 3   lisi 20   zhangsan 100

按照名字进行排序:

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

//按照名字比较
int comper_name(const void* e1, const void* e2)
{return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e1)->name);//名字是字符串,所以名字的比较要用到字符串比较 函数strcmp
}

int main()
{struct Stu arr[3] = {{"zhangsan",100},{"lisi",20},{"wangwu",3} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;

	//排序前打印
	for (i = 0; i< sz; i++)
	{printf("%s %d   ", arr[i].name, arr[i].age);
	}
	printf("\n");

	//按照年龄进行排序
	qsort(arr, sz, sizeof(arr[0]), comper_name);

	
	//排序后打印
	for (i = 0; i< sz; i++)
	{printf("%s %d   ", arr[i].name, arr[i].age);
	}
	printf("\n");
	return 0;
}
//结果:
zhangsan 100   lisi 20   wangwu 3
lisi 20   wangwu 3   zhangsan 100
四、利用冒泡排序模拟实现qsort函数4.1:冒泡排序

 关于冒泡排序的详细讲解可以参考我的这篇文章:初级C语言之【数组】里面详细介绍了冒泡排序

//冒泡排序函数
void bulle_sort(int* arr , int sz)//这里形参已经写死了,只能排整型数组
{int i = 0;
	//趟数
	for (i = 0; i< sz - 1; i++)
	{//一趟冒泡的过程
		int j = 0;
		for (j = 0; j< sz-1-i; j++)
		{	if (arr[j] >arr[j + 1])
			{		int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

int main()
{int arr[10] = {9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bulle_sort(arr,sz);
	int i = 0;
	for (i = 0; i< sz; i++)
	{printf("%d ", arr[i]);
	}
	return 0;
}
//结果:
0 1 2 3 4 5 6 7 8 9

缺陷1:
 用来接收待排序数组首元素地址的指针arr已经被写死了,是int*型,说明只能对整型数组进行排序

缺陷2:
在这里插入图片描述
 缺陷2如上图所示,红色方框框起来的部分只适用于对整数之间的大小关系进行比较,然后交换

4.2:模拟实现qsort函数
//利用冒泡排序模拟实现qsort

void Swap(char* ele1, char* ele2,int width)
{int i = 0;
	for (i = 0; i< width; i++)
	{char tmp = *ele1;
		*ele1 = *ele2;
		*ele2 = tmp;
		ele1++;
		ele2++;
	}
}

void bulle_sort(void* arr , size_t sz,size_t width,int(*comper)(const void*e1,const void*e2))
//第一个参数 - 用来接收待排序数组的首元素地址,可能会排序各种数组,所以形参数组用void*来接收
//第二个参数 - 用来接收数组元素个数
//第三个参数 - 用来接收数组元素的宽度

{size_t i = 0;
	//趟数
	for (i = 0; i< sz - 1; i++)
	{//一趟冒泡的过程
		size_t j = 0;
		for (j = 0; j< sz-1-i; j++)
		{	if (comper((char*)arr+j*width,(char*)arr+(j+1)*width)>0)
			//把arr强转为char*,arr就可以正常使用
			//char类型指针+1只会跳过一个字节
			//+j*width表示跳过j个元素
			{		//交换
				//由于这里的数组名已经被转为char类型的指针
				//所以要交换数组中的元素,就只能一个字节一个字节进行交换
				Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width);
				//前两个参数是待交换元素的地址,第三个参数是元素的宽度
			}
		}
	}
}

 这里说的利用冒泡排序来实现qsort函数,仅仅是实现了qsort函数可以对任意类型的数组进行排序这一特点,并不是说实现qsort函数的底层原理,qsort的底层是通过快速排序来实现的。
 因此,为了使改变之后的冒泡函数能够对任意类型的数组进行排序,原本冒泡排序函数的参数就要发生改变,和qsort函数一样,新的冒泡排序函数也要有以下4个参数:

  • void* arr
  • size_t sz
  • size_t width
  • int(*comper)(const void*e1,const void*e2)

arr用来接收待排序数组首元素的地址,sz用来接收待排序数组的元素个数,width用来接收数组中每个元素的大小(单位是字节),comper用来接收比较函数的地址。参数的改变解决了原冒泡排序函数的缺陷1。
 接下来要解决原冒泡排序函数的缺陷2,缺陷2的主要问题在于它的普适性不够强,首先要对交换的判断条件,即if后面的判断语句做出改变,让他能够比较任意两个类型的数据,这时,比较函数就发挥作用了,我们只需要把待比较的两个元素地址传给比较函数,由比较函数来判断它们之间的关系
 新的问题又出现了,comper函数的形参需要接收两个待比较元素的地址,这里的待比较元素一定是当前待排序数组里面的元素,但是待排序数组的首元素地址是用空指针(void*)来接收的,无法直接使用,这意味着现在无法通过数组首元素的地址,顺藤摸瓜去访问数组中的元素。这里问题的关键就是空指针无法使用,那我们就想到把空指针进行强制类型转化,把空指针变成有具体指向的指针不就可以正常使用了,问题又出现了,有那么多的指针类型,到底把空指针强转成什么类型的指针呢???答案是:把空指针强转成字符指针(char*)。这里是因为,字符指针+1仅跳过一个字节,我们可以通过改变加数的数值,使指针指向任意内存空间,这也就意味着强转后的arr指针可以存放任意内存单元的地址,并且可通过地址去访问内存中的数据。

  • (char*)arr+j*width

 这里先把arr指强制类型转化成char*类型,这里的加数是:j*width。其中width表示当前数组中每个元素的大小(单位是字节),这里的+j*width就是跳过j*width个字节,由于width是一个元素的字节,所以+j*width也就意味着跳过了j个元素,此时(char*)arr+j*width就表示下标为j的元素的地址。

  • (char*)arr+(j+1)*width

 同理(char*)arr+(j+1)*width就表示下标为j+1的元素的地址。

 此时就可以把待比较的两个元素的地址传给用户自己写的comper函数了,通过comper函数的返回值来判断这两个元素是否要交换。

 到这里缺陷2中的问题只解决了一半,即:只把交换的判断条件做了修改,增强了交换判断条件的普适性,使其可以对任意类型的数组中的元素进行比较。具体的交换步骤还没有修改,当前的交换步骤仅仅适用于整型数据。根据经验,对两个变量进行交换,需要创建一个中间变量,比如:交换两个整型变量,需要创建一个整形的中间变量;交换两个字符型变量,需要创建一个字符型的中间变量……可见,对于不同类型的数据元素,在交换时创建的中间变量的类型也是不同的,由于无法预知要交换数据的类型,所以也无法提前确定中间变量的类型。这里的解决方案是:一个字节一个字节的交换,这样中间变量的类型就能确定下来了,即为char型。不同的数据类型对应着不同的字节数,但是它们都是由字节组成,我们有了数组中每个元素的字节大小时,就可以写一个循环,从元素的首个字节开始,一个字节一个字节的交换,直到最后一个字节。这里我们写了一个交换函数Swap

  • void Swap(char* ele1, char* ele2,int width)

 Swap函数有三个参数,ele1ele2分别用来接收待交换的两个元素的地址,width用来接收数组中每个元素的大小(单位是字节)。

void Swap(char* ele1, char* ele2,int width)
{int i = 0;
	for (i = 0; i< width; i++)
	{char tmp = *ele1;
		*ele1 = *ele2;
		*ele2 = tmp;
		ele1++;
		ele2++;
	}
}

 到此,原来冒泡排序中的两个缺陷已经被成功地解决,经过改造后的冒泡函数bulle_sort就可以对任意类型数组进行排序。

4.3:实际应用4.3.1:利用bulle_sort函数对整型数组排序:
//利用冒泡排序模拟实现qsort

//交换函数
void Swap(char* ele1, char* ele2,int width)
{int i = 0;
	for (i = 0; i< width; i++)
	{char tmp = *ele1;
		*ele1 = *ele2;
		*ele2 = tmp;
		ele1++;
		ele2++;
	}
}
//改造后的冒泡排序函数
void bulle_sort(void* arr , size_t sz,size_t width,int(*comper)(const void*e1,const void*e2))
//第一个参数 - 用来接收待排序数组的首元素地址,可能会排序各种数组,所以形参数组用void*来接收
//第二个参数 - 用来接收数组元素个数
//第三个参数 - 用来接收数组元素的宽度
{size_t i = 0;
	//趟数
	for (i = 0; i< sz - 1; i++)
	{//一趟冒泡的过程
		size_t j = 0;
		for (j = 0; j< sz-1-i; j++)
		{	if (comper((char*)arr+j*width,(char*)arr+(j+1)*width)>0)
			//把arr强转为char*,arr就可以正常使用
			//char类型指针+1只会跳过一个字节
			//+j*width表示跳过j个元素
			{		//交换
				Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width);
				//前两个参数是待交换元素的地址,第三个参数是元素的宽度
			}
		}
	}
}
//比较函数
int comper_int(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}
//主函数
int main()
{int arr[10] = {9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bulle_sort(arr, sz, sizeof(arr[0]), comper_int);//调用bulle_sort来排序
	int i = 0;
	for (i = 0; i< sz; i++)
	{printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}
//结果:
0 1 2 3 4 5 6 7 8 9
4.3.2:利用bulle_sort函数对结构体数组排序:

按照年龄排序:

//利用冒泡排序模拟实现qsort

//交换函数
void Swap(char* ele1, char* ele2,int width)
{int i = 0;
	for (i = 0; i< width; i++)
	{char tmp = *ele1;
		*ele1 = *ele2;
		*ele2 = tmp;
		ele1++;
		ele2++;
	}
}
//改造后的冒泡排序函数
void bulle_sort(void* arr , size_t sz,size_t width,int(*comper)(const void*e1,const void*e2))
//第一个参数 - 用来接收待排序数组的首元素地址,可能会排序各种数组,所以形参数组用void*来接收
//第二个参数 - 用来接收数组元素个数
//第三个参数 - 用来接收数组元素的宽度
{size_t i = 0;
	//趟数
	for (i = 0; i< sz - 1; i++)
	{//一趟冒泡的过程
		size_t j = 0;
		for (j = 0; j< sz-1-i; j++)
		{	if (comper((char*)arr+j*width,(char*)arr+(j+1)*width)>0)
			//把arr强转为char*,arr就可以正常使用
			//char类型指针+1只会跳过一个字节
			//+j*width表示跳过j个元素
			{		//交换
				Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width);
				//前两个参数是待交换元素的地址,第三个参数是元素的宽度
			}
		}
	}
}
//声明一个结构体
struct Stu
{char name[20];
	int age;
};

//按照年龄进行比较
int comper_age(const void* e1, const void* e2)
{return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}

//主函数
int main()
{struct Stu arr[3] = {{"zhangsan",100},{"lisi",20},{"wangwu",3} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;

	//排序前打印
	for (i = 0; i< sz; i++)
	{printf("%s %d   ", arr[i].name, arr[i].age);
	}
	printf("\n");

	//按照年龄进行排序
	bulle_sort(arr, sz, sizeof(arr[0]), comper_age);
	
	//排序后打印
	for (i = 0; i< sz; i++)
	{printf("%s %d   ", arr[i].name, arr[i].age);
	}
	printf("\n");
	return 0;
}
//结果:
zhangsan 100   lisi 20   wangwu 3
wangwu 3   lisi 20   zhangsan 100

按照名字排序:

//利用冒泡排序模拟实现qsort

//交换函数
void Swap(char* ele1, char* ele2,int width)
{int i = 0;
	for (i = 0; i< width; i++)
	{char tmp = *ele1;
		*ele1 = *ele2;
		*ele2 = tmp;
		ele1++;
		ele2++;
	}
}
//改造后的冒泡排序函数
void bulle_sort(void* arr , size_t sz,size_t width,int(*comper)(const void*e1,const void*e2))
//第一个参数 - 用来接收待排序数组的首元素地址,可能会排序各种数组,所以形参数组用void*来接收
//第二个参数 - 用来接收数组元素个数
//第三个参数 - 用来接收数组元素的宽度
{size_t i = 0;
	//趟数
	for (i = 0; i< sz - 1; i++)
	{//一趟冒泡的过程
		size_t j = 0;
		for (j = 0; j< sz-1-i; j++)
		{	if (comper((char*)arr+j*width,(char*)arr+(j+1)*width)>0)
			//把arr强转为char*,arr就可以正常使用
			//char类型指针+1只会跳过一个字节
			//+j*width表示跳过j个元素
			{		//交换
				Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width);
				//前两个参数是待交换元素的地址,第三个参数是元素的宽度
			}
		}
	}
}
//声明一个结构体
struct Stu
{char name[20];
	int age;
};


//按照名字比较
int comper_name(const void* e1, const void* e2)
{return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);//名字是字符串,所以名字的比较要用到字符串比较 函数strcmp
}

//主函数
int main()
{struct Stu arr[3] = {{"zhangsan",100},{"lisi",20},{"wangwu",3} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;

	//排序前打印
	for (i = 0; i< sz; i++)
	{printf("%s %d   ", arr[i].name, arr[i].age);
	}
	printf("\n");

	//按照名字进行排序
	bulle_sort(arr, sz, sizeof(arr[0]), comper_name);
	
	//排序后打印
	for (i = 0; i< sz; i++)
	{printf("%s %d   ", arr[i].name, arr[i].age);
	}
	printf("\n");
	return 0;
}
//结果:
zhangsan 100   lisi 20   wangwu 3
lisi 20   wangwu 3   zhangsan 100

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站标题:【C语言进阶】qsort函数详解以及它的模拟实现-创新互联
标题URL:http://scyanting.com/article/dshiis.html