今天主要讲解一下qsort函数的使用，以及通过冒泡排序来模拟qsort函数

---

Bubble_sort

冒泡排序

先来看段简单的冒泡排序（升序）代码：

#include<stdio.h>
void Bubble_sort(int* arr, int sz)
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		for (j = 0; j < sz - i - 1; j++)
		{
			if (*(arr + j) > *(arr + j + 1))
			{
				int tmp = *(arr + j);
				*(arr + j) = *(arr + j + 1);
				*(arr + j + 1) = tmp;
			}
		}
	}
}
int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Bubble_sort(arr, sz);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

        想象一下，如果数组本身的数据排序就是升序，没有必要再去排序，但对于这种冒泡排序岂不是也要在排一遍，不够优化。

冒泡排序优化

#include<stdio.h>
void Bubble_sort(int* arr, int sz)
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int flag = 1;//假设数组是升序
		int j = 0;
		for (j = 0; j < sz - i - 1; j++)
		{
			if (*(arr + j) > *(arr + j + 1))
			{
				int tmp = *(arr + j);
				*(arr + j) = *(arr + j + 1);
				*(arr + j + 1) = tmp;
				flag = 0;//数组不是升序
			}
		}
		if (flag == 1)
		{
			break;
		}
	}
}
int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Bubble_sort(arr, sz);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

        这样是不是效率就提高了不少呢？

 

        但是

 

       有没有思考过这样一个问题，这样的冒泡排序再怎么优化只能实现对整形数组的排序，（形参接收类型为int*）对其他的类型却无法实现排序?

        对于qsort函数来说，这都不是问题，她说：“我可以排序任意类型的数据~”。

---

qsort的使用

void*类型

        先看一下qsort类型函数是如何定义的

第一个参数：数组首元素地址

第二个参数：需要排序的长度

第三个参数：每个元素的类型大小（单位：字节）

第四个参数：函数指针——比较函数,e1和e2是需要比较的两个元素的地址

        为什么会出现void*的指针呢？

 

        viod*是无类型指针，可以接收任意类型的数据，但是要注意，对于void*指针，不能进行解引用操作，也不能+1-1操作，需要进行强制类型转换，例如我传入一个整形，如下代码

int* a = (int*)e1;

        创建一个整形指针来存放强制转换后的指针。

 

        这第四个参数是什么意思呢？

 

        qsort函数可以排序任意类型的数据，但是，她也不知道你要让他排什么类型的数据，因为不同类型的数据比较的方法不一样，（整形数据，大于小于号就可以比较，那对于结构体呢？）所以这个时候，就引入了第四个参数——函数指针，这个比较函数需要自己设计，此函数返回类型是int，规定若返回于一个大于零的数就按降序排序，若返回一个小于零的数就按升序排序

还是有点懵？继续往下看~

qsort实现各种类型排序

        为了便于理解，比较函数写成以下形式：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int cmp_int(const void* _a, const void* _b)
{
	int* a = (int*)_a;
	int* b = (int*)_b;
	return *a - *b;
}
int cmp_char(const void* _a, const void* _b)
{
	char* a = (char*)_a;
	char* b = (char*)_b;
	return strcmp(a, b);
}
int cmp_double(const void* _a, const void* _b)
{
	double* a = (double*)_a;
	double* b = (double*)_b;
	return *a > *b ? 1 : -1;
}
int main()
{
	int in[] = { 2,5,6,4,8,7,1,3 };
	char ch[] = "helloworld";
	double dou[] = { 5.6,5.2,7.2,5.6,4.8,9.1,4.2 };
	int size_in = sizeof(in) / sizeof(in[0]);
	int size_ch = sizeof(ch) / sizeof(ch[0]);
	int size_dou = sizeof(dou) / sizeof(dou[0]);
	qsort(in, size_in, sizeof(in[0]), cmp_int);
	qsort(ch, size_ch, sizeof(ch[0]), cmp_char);
	qsort(dou, size_dou, sizeof(dou[0]), cmp_double);
	//打印整形
	int i = 0;
	for (i = 0; i < size_in; i++)
	{
		printf("%d ", in[i]);
	}
	printf("\n");
	//打印字符串
	for (i = 0; i < size_ch; i++)
	{
		printf("%c", ch[i]);
	}
	printf("\n");

	//打印浮点数
	for (i = 0; i < size_dou; i++)
	{
		printf("%lf ", dou[i]);
	}
	printf("\n");
	return 0;
}

这里可以明显体现出不同类型之间的不同比较方式。

当然比较函数也可做如下调整，看起来更简洁~

int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
int cmp_char(const void* e1, const void* e2)
{
	return strcmp((char*)e1, (char*)e2);
}
int cmp_double(const void* e1, const void* e2)
{
	return *(double*)e1 > *(double*)e2 ? 1 : -1;
}

 

接下来看一下结构体类型的比较

实际上也是整形、字符、字符串...等类型的比较。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct stu
{
	char name[30];
	int age;
};
int cmp_struct(const void* e1, const void* e2)
{
	return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
}
int main()
{
	struct stu s[] = {{"Franz Liszt",36},{"F.F.Chopin",45},{"Johann Sebastian Bach",35}};
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), cmp_struct);
	return 0;
}

想知道qsort内部是如何运作的吗？

往下走~

---

Bubble_sort模拟实现qsort

        这回我们试试通过改造冒泡排序来实现qsort函数

#include<stdio.h>
int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
void Swap(size_t width, char* e1,char* e2)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *e1;//以最小单位一个一个字节的交换
		*e1 = *e2;
		*e2 = tmp;
		e1++;//两地址加加，向后访问，直到到达此类型大小为止
		e2++;
	}
}
void Bubble_sort(void* base, size_t sz, size_t width, int(*cmp)(const void* elem1, const void* elem2))
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int flag = 1;//假设数组是升序
		int j = 0;
		for (j = 0; j < sz - i - 1; j++)
		{
			if (cmp_int((char*)base + j * width, (char*)base + (j + 1) * width) > 0)//找到交换的起始位置地址
			{//这里用char类型是因为不知道这个函数会传入什么类型，所以就用char类型，char类型可以一个一个字节的访问
				//乘上每个元素的大小（width）就可以跳过该类型的大小
				Swap(width, (char*)base + j * width, (char*)base + (j + 1) * width);
				flag = 0;//数组不是升序
			}
		}
		if (flag == 1)
		{
			break;
		}
	}
}
int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

解释说明都在代码注释里啦~