qsort(简单)

qsort是一个库函数，是一个基于快速排序算法的一个排序函数，是对数组中的元素进行排序，可以升序也可以降序。

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

qsort函数中有四个参数，第一个参数为我们需要排序的对象数组的首元素的地址（数组名），但是这里用的是 void* base，因为并不知道我们要排序的数组里面的元素是什么类型的，因此我们用一个void*base的指针来接受它。第二个参数为num，是我们需要排序的对象数组的元素个数。第三个参数是宽度，也就是我们的对象数组元素的大小。第四个参数是一个函数，这个函数是需要我们自己来进行写的，我们需要怎样的排序方法，函数的返回值为int，后面的函数的参数类型也是void*类型的，因为前面说到了我们并不知道对象数组里面存放的元素是什么类型的，并且这里的两个参数我们用const进行了修饰，只做交换，并不修改，我们的称第一个元素为e1，第二个元素为e2，返回值为int类型的，我们对e1和e2进行比较，当e1>e2时，我们返回一个大于0的数字1，当e1 == e2时，我们返回0，当e1

我们之前了解到的冒泡排序，我们这里简单的写一下，

#include
void bubbling(int arr[], int len)
{
	for (int i = 0; i < len; i++)
	{
		for (int j = 0; j < len - 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[] = { 4,7,2,5,1,3,8,10,9,6 };
	int len = sizeof(arr) / sizeof(arr[0]);
	bubbling(arr, len);
	for (int i = 0; i < len; i++)
	{
		printf("%d  ", arr[i]);
	}
	return 0;
}

我们会看到我们写的bubbling函数会将arr数组进行升序排序

那么我们了解到了sqort函数的基本用法，我们来模拟实现一下sqort函数，更深入的了解一下sqort函数是如何工作的。

void Swap(char* e1, char* e2, int width)
{
	for (int i = 0; i < width; i++)
	{
		char tmp = *e1;
		*e1 = *e2;
		*e2 = tmp;
		e1++;
		e2++;
	}
}
void my_qsort(void* base, int num, int width, int(*cmp)(void* e1, void* e2))
{
	for (int i = 0; i < num; i++)
	{
		for (int j = 0; j < num - 1 - i; j++)
		{
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
				Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
			}
		}
	}
}
int cmp(const void* e1, const void* e2)
{
	return (*(int*)e1 - *(int*)e2);
}
void my_print(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[] = { 4,7,2,5,1,3,8,10,9,6 };
	int len = sizeof(arr) / sizeof(arr[0]);
	my_qsort(arr, len, sizeof(arr[0]), cmp);
	my_print(arr, len);
	return 0;
}

我们看到也可以看到，我们模拟的qsort函数也可以将arr数组升序排列，当然我们也可以让其降序，在我们自己写的cmp函数中，我们将e1和e2的位置调换一下即可。

我们来说一说我们这个函数为什么要这样子写，

在我们自己写的my_qsort中，我们看到了cmp函数的参数是两个void*类型的，我们自己也不知道我们排列的对象数组里面存放的是什么类型的元素，因此我们将其强制转化为char*类型，这样的话base就为一个字节，当我们要排序的对象数组的元素类型不是char类型的时候，我们不知道是什么类型，这时候我们给其加上一个j*width，这个时候我们跳过的就是我们对象数组里面元素的字节大小了，因为witdh是元素的宽度(也就是元素的字节大小),这个时候我们刚好跳过了这个元素。

当然我们也可以用来为结构体进行排序

#include
#include 
#include 

struct stu
{
	char name[20];
	int age;
	double grade;
};
int cmp_name(const void* e1, const void* e2)
{
	return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
}
int cmp_age(const void* e1, const void* e2)
{
	return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}
int cmp_grade(const void* e1, const void* e2)
{
	if (((struct stu*)e1)->grade - ((struct stu*)e2)->grade)
	{
		return 1;
	}
	else if ((((struct stu*)e1)->grade - ((struct stu*)e2)->grade) == 0)
	{
		return 0;
	}
	else
	{
		return -1;
	}
}
int main()
{
	struct stu arr[3] = { {"zhangsan",20,63.5}, {"lisi",23,67.5},{"wangwu",22,59.0} };
	int len = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, len, sizeof(arr[0]), cmp_name);
	qsort(arr, len, sizeof(arr[0]), cmp_age);
	qsort(arr, len, sizeof(arr[0]), cmp_grade);
	printf("%s %s %sn", arr[0].name, arr[1].name, arr[2].name);
	printf("%d %d %dn", arr[0].age, arr[1].age, arr[2].age);
	printf("%.2lf %.2lf %.2lfn", arr[0].grade, arr[1].grade, arr[2].grade);
	return 0;
}

运行结果如下，