C++ qsort函数排序

本章重点：

1.能够正确的理解qsort函数各个参数的含义，并能够正确的使用qsort函数进行各类型排序。

2.重点掌握qsort函数中的参数cmpar——自定义比较函数的地址。借此进一步理解回调函数。 3.学习以冒泡排序思想模拟实现qsort函数。

一、qsort排序函数

1、函数功能特点

//头文件:#include<stdlib.h>
void qsort(void* base, size_t num, size_t size,int (*compar)(const void*, const void*));

注：因为qsort可以对任意类型数据排序，所以待排数据的起始类型可以是任意类型，C语言中可以用void*接收任意类型的地址。

2、函数参数

3、比较函数

qsort之所以可以对任意类型的数据排序正是因为传入的比较函数是相对自定义的：

对于比较函数 int compar(const void *p1,const void *p2)

（1）比较整数：

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

1、如果compar返回值小于0（< 0），即*(MyType*)p1 < *(MyType*)p2那么p1所指向元素会被排在p2所指向元素的前面,也就是升序 。

2、如果compar返回值等于0（= 0），即*(MyType*)p1 = *(MyType*)p2那么p1所指向元素与p2所指向元素的顺序不确定。

3、如果compar返回值大于0（> 0），即*(MyType*)p1 > *(MyType*)p2那么p1所指向元素会被排在p2所指向元素的后面,也是升序。

所以为了方便理解我们可以简单这样认为：对于qsort函数如果compar函数的返回值<0(不进行置换)，>0(进行置换)，0(不进行置换)。

即：

return *(MyType*)p1 - *(MyType*)p2;——qsort升序排序

return *(MyType*)p2 - *(MyType*)p1;——qsort降序排序

对于具体qsort函数内部具体是怎么进行置换或排序的我们不必关心。（内部实现为快排思想）

（2）比较字符串：

int compareMyType(const void* p1, const void* p2)
{
	return strcmp((MyType *) p1, (MyType *) p2);
}

同理：

return strcmp((MyType*)p1,(MyType*)p2);——qsort升序排序

return strcmp((MyType*)p2,(MyType*)p1);——qsort降序排序

（3）比较结构体

与上述思想类似，比较结构体时需要具体情况具体分析。

4、测试qsort排序

（1）测试qsort函数排序整形

#include<stdio.h>
#include<stdlib.h>
//输出函数
void print(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}
//比较函数
int compar(const void* e1, const void* e2)
{
	return *((int*)e1) - *((int*)e2);//升序
	//return *((int*)e2) - *((int*)e1);//降序
}
int main()
{
	int arr[] = { 3,5,2,6,8,1,9,0,4,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//arr-数据起始地址
	//sz-数据元素个数
	//sizeof(arr[0])-数据元素的大小
	//compar-比较函数指针
	qsort(arr, sz, sizeof(arr[0]), compar);
	print(arr, sz);
	return 0;
}

（2）测试qsort函数排序结构体