C语言-----qsort()函数

前面向大家介绍了冒泡排序，冒泡排序的核心思想是让数组中相邻的元素进行比较，这是一种常见的算法。但是冒泡排序有一个缺陷，就是冒泡排序只能对整型类型的数组进行操作。所以当我们要对其他类型进行排序时。例如：字符串类型的数组、结构体类型的数组。则冒泡排序此时就不起作用了，那我们要如何操作呢？

C语言为例帮我们解决这个问题，就创建了一个排任意数据类型的函数------qsort()函数。

1.qsort()函数

qsort()函数是C语言中的一个库函数，其包含在 <stdlib.h> 这个头文件中。它是C语言中的一个高级函数，可以帮助我们对任意类型的数组进行排序。

qsot()函数采用了自动快速排序的方式，当条件符合时，就会自动对所需要进行排序的数据进行排序。

那如何使用qsort()函数呢？

首先，我们要知道qsort()函数中有4个参数，形式如下

void qsort(void* base,size_t num,size_t size,int(*compare)(const void*p1,const void*p2))

我来为大家解释下这些参数的意义

1. void* base 是一个void* 类型的指针，其指向的是需要进行排序的数组中的首个元素。

2. size_t num 是指向数组的元素个数，也就是数组的大小。

3. size_t size 是指向数组中的元素的大小。

4. int(*compare)(const void*,const void*) 是一个指向两个需要比较元素的数组。

这个比较函数是有返回值,如下表

返回值	*p1-*p2
1	*p1-*p2>0
-1	*p1-*p2<0
0	*p1*p2==0

注意： 这里的*p1 ,*p2做差的位置不是固定的，我们要根据我们的需求来决定是*p1-*p2还是

*p2 - *p1。

2.qsort()的实际使用

2.1 qsort()实现对整型数组的排序

int main()
{
	int arr[5] = { 23,45,67,24,78 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), com);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

我们先应用qsort()这个函数，接下来就是重点了。

重点就是如何编写com这个比较函数。

首先我们知道com这个函数的返回值是int类型的。com的两个形参为 const void*。

根据此写出以下代码

我们首先可能会这样写

int com(const void* p1, const void* p2)
{
	if (*p1 - *p2 > 0)
	{
		return 1;
	}
	else if (*p1 - *p2 < 0)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

但这样是会报错的，因为p1和p1的类型是void*，无法直接进行解引用的。所以，首先，我们要对p1和p2进行强制类型转换，将其转换为int*型的。

此时我们可能会很疑惑，为什么偏偏是转换为int*的呢？而不是转换为其它类型的呢？

 这时我们就要清楚我们是qsort()的使用者，我们是以上帝视角来使用qsort()函数的。所以我们就很清楚的知道我们就很清楚的知道我们要排序的类型是int类型的，所以我们就将其转换为int*的，在对其进行解引用。

正确代码如下

int com(const void* p1, const void* p2)
{
	if (*(int*)p1 - *(int*)p2 > 0)
	{
		return 1;
	}
	else if (*(int*)p1 - *(int*)p2 < 0)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

也可以简化成一下代码

int com(const void* p1, const void* p2)
{
	return *(int*)p1 - *(int*)p2;
}

这里我们要根据自身需求去决定是p1-p2还是p2-p1。

完整代码

int com(const void* p1, const void* p2)
{
	return *(int*)p1 - *(int*)p2;
}
int main()
{
	int arr[5] = { 23,45,67,24,78 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), com);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	
	return 0;
}

2.2 qsort()实现对结构体数组的排序

我们先创建一个结构体

struct stu
{
	char name[100];
	int age;
};
int main()
{
	struct stu arr[3] = { {"zhangsan",18},{"lisi",54},{"laoba",25} };
	int sz = sizeof(arr) / sizeof(arr[0]);
}

接下来，我们就可以通过qsort()函数根据名字和年龄来排序 。

2.2.1 根据年龄来排

整体思路跟上面讲的对整形数组排序的思路是一样的。

但有一点需要注意的是，我们排序的是结构体数组，我们要使用结构体里面的某一类型数据时，要用到 -> 操作符。使用方法为 结构体指针->结构体变量名 。

代码如下

struct stu
{
	char name[100];
	int age;
};
int com_age(const void* p1, const void* p2)
{
	return ((struct stu*)p1)->age - ((struct stu*)p2)->age;
}
int main()
{
	struct stu arr[3] = { {"zhangsan",18},{"lisi",54},{"laoba",25} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]),com_age);
	return 0;
}

通过调试发现，结构体数组里面的会根据年龄来进行排序。

2.2.2 根据名字来排

由于我们定义name的类型为char，所以这时候比较字符串就要用到 strcmp() 函数，其包含在

头文件<string.h>中。

我们要知道strcmp()函数的比较方法。其实将相对应的字符转换称为ASCII值进行交换，知道遇到相对应的字符串不同时，哪个字符的ASCII值大，则其对应的字符串就大。

了解了这些，思路跟前面是差不多的。

代码如下

struct stu
{
	char name[100];
	int age;
};
int com_name(const void* p1, const void* p2)
{
	return strcmp(((struct stu*)p1)->name - ((struct stu*)p2)->name);
}
int main()
{
	struct stu arr[3] = { {"zhangsan",18},{"lisi",54},{"laoba",25} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]),com_name);
	return 0;
}

3.冒泡排序模拟qsort()函数

既然我们是用冒泡排序来模拟qsort()函数，那么冒泡排序的思维还是用得上的，也就是说基本框架还是不变的。

基本框架

void bubble_sort(void* base, size_t sz, size_t width, int (*com)(const void*p1,const void*p2))
{
for(i=0;i<sz-1;i++)
{
   for(j=0;j<sz-i-1;j++)
   {
      if()
    }
}
}

我们知道冒泡 排序的核心思想是让数组内相邻的元素进行比较，所以模拟qsort()时，依旧不变，只是获取两个相邻比较的元素方式变了，应为模拟qsort()函数时，bubble_sort 形参接收的是数组首元素的地址。所以if 里面不能直接使用数组里面的元素了。

因此，我们要换一个思维。

从上面的基本框架可知，bubble_sort 里面有一个比较函数的形参，而if 括号里面恰好是两个元素的比较，p1和p2也是数组里面前后的两个元素，一开始*p1是首元素，*p2是第二个元素，所以我们可以让比较汉书称为if 需要的表达式。

则if 里面com函数里面实参可以这样写，如下图

因为com函数里面的参数本来是const void*类型的，无法直接进行指针的加减运算，所以我们将其类型转换为char*的。

这时就有人疑惑了，我们要排序的数据类型是int型的，为什么不直接将其转换成int*呢？

首先我们要清楚指针类型的意义只是让指针进行加减整数运算时能过跳过几个字节。转换成int*，一次加1能跳过4个字节，如果我们要排序7个字节的元素，就会有可能出问题。

而char* 指针一次加1就跳过一个字节，这样，一个一个字节进行比较，能有更好的效果。

如下所示

if (com((char*)base+j*width,(char*)base+(j+1)*width)>0)

 比较完两个元素之后，我们就要进行交换。我们另写一个swap()函数完成此功能。

因为要比较的两个元素已经知道，直接搬到函数里面

	if (com((char*)base+j*width,(char*)base+(j+1)*width)>0)
	{
		swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
    }

如何将其互换也是一个重点。

因为是char* 类型的数据，加减整数1都只跳过一个字节。

思维是 因为数据是存在内存中的，所以只要将数据的内存进行互换，两个元素的值也就交换了。

所以将 需要比较的元素按一个一个空间来换。

仅仅知道交换是不够的，我们还要知道交换几个字节，所以也要将元素大小width传过去

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

到这里差不多就完成了，完整代码如下

int com(const void* p1, const void* p2)
{
	return *(int*)p1 - *(int*)p2;
}
swap(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}
void bubble_sort(void* base, size_t sz, size_t width, int (*com)(const void*p1,const void*p2))
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (com((char*)base+j*width,(char*)base+(j+1)*width)>0)
			{
				swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
		   }
		}
	}
}
void Print(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[5] = { 23,13,67,48,35 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz, sizeof(arr[0]), com);
	Print(arr, sz);
	return 0;
}

 

接着比较结构体

#include<stdio.h>
#include<stdlib.h>
void sort(int arr[], int sz)
{
	
	int i, j;
	for (i = 0; i < sz - 1; i++)
	{
		for (j = 0; j < sz - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
			}
		}
	}
}
void Swap(char *p1,char *p2,int wid)
{
	for (int i = 0; i < sz; i++)
	{
		char temp = *(p2 + i);
		*(p2 + i) = *(p1 + i);
		*(p1 + i) = temp;
	}
}
 
int cmp_int(const void* p1, const void* p2)
{
	return *(int*)p1 - *(int*)p2;
}
void bubble_sort(void *base,int sz,int width,int (*cmp)(const void *p1,const void *p2))
{
	
	for (i = 0; i < sz - 1; i++)
	{
		for (j = 0; j < sz - 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 test()
{
	int arr[] = { 3,12,35,8,9,6,59,0,8, };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
	for (int i = 0; i < sz; i++)
		printf("%d ", arr[i]);
}
int main()
{
	test();
	return 0;
}