qsort:我很强，了解一下（详解过程）

🎑情境引入

struct student
{
    char name[10];
    int age;
};

你是否有过这样的经历，在对结构体成员进行排序，需要写几个排序，而感到不耐烦呢。
就比如对上面的结构体数组排序，既要对成员name排序，又要对成员age排序。
看了这篇博客，你就可以告别大段落式的排序啦。
qsort表示它很强，它来拯救你了~~❤

qsort强在哪呢？
强在它可以对任意类型的排序（存储结构需要限定–顺序存储）
也就是说qsort只能对顺序存储的结构进行排序。
顺序存储结构有：1.数组，2.在堆区开辟一段连续的空间

🎈qsort

📖qsort的头文件

#include

📄开场

qsort底层原理是快排，但在这篇博客中不讲快排，而是讲冒泡排序，以及插入排序去模拟qsort的功能。

为啥还要讲插入排序呢，如果你想对单链表进行排序的话，qsort是不能达到目的的，对于单链表的排序，需要用插入排序的思想进行排序。

通过插入排序模拟qsort，再对存储复杂数据的单链表排序的时候，会轻松很多。

🔑qsort的参数

size_t 是 unsigned int 重命名后的类型名

🤔为什么可以对任意类型排序呢？

主要是在设置函数参数的时候，使用的是void*。
void* 有个特点，叫“有容乃大”。
void* 可以接收任意类型的指针
同样的任意类型的指针也可以接收void*

在void* 修饰的变量接收任意类型的指针的情况下，该变量是不能进行任何操作的。

因为对指针进行操作是看指针的类型，该变量的类型是void* 。
因为void类型大小是不确定的（vs下0，linux下1）。
那么对该变量进行*或者加减整数操作是没有意义的
指针类型的意义不记得的点这

那如何解决呢？只需要通过强制类型转换即可。

📜参数

参数①

对于参数①void* base 通过void* 就能够推测一些东西了。void*是指针，是用来接收地址的。
那么在调用qsort的时候，第一个实参一定是个地址。这样理解是没错的，也确实如此。
实参传①就是你想要排序数组的起始地址（或者在堆区开辟空间的起始地址）

参数②

对于参数②size_t num，表示你需要排序的数组有多少个元素个数

参数③

对于参数③ size_t size，表示待排序数组元素的大小（单位是字节）
为什么需要传元素的大小呢？也很好理解，我们需要对不同类型的元素进行排序，不同的类型，所占空间的大小是不同的，如果不传元素的大小，qsort又怎么能对不同类型元素进行排序呢？所以必须传。

最难的参数④

参数④ int (*compar)(const void*, const void*))这也是我们能够比较任意类型的关键！
有人看到这个参数感觉头皮发麻，不知道这是啥。先来分析一下。
我们先把中间部分换个形式int fun (const void*, const void*))
这是啥？这是一个函数！
函数名是fun形参为(const void*, const void*)返回类型为int
在回过头来分析int (*compar)(const void*, const void*))，那这是什么？这是指针，因为操作符*，并且与()优先结合，所以是指针。
再结合上面所说，这个指针指向的是一个函数。

有人可能难以理解指向的是函数，那我再说说，请问函数有地址吗？答案是有的。

在多说几嘴，函数名也是可以直接表示函数的地址，也可以不用&。

已经知道函数是有地址的了，那指针去指向一个函数，也就没什么问题的了。看下面这段话，再去理解一番。

看这个表达式 int* p 。
p指向谁？如果你不知道怎么看的话，把指针名p和*去掉，剩下的就是指针指向某个变量的类型。也就是说p将来指向的是一个int类型的变量（不考虑强制类型转换）

那么再回过头来看int (*compar)(const void*, const void*))，把指针名compar 和 *去了，剩下的是 int (const void*, const void*))这是一个函数。按照上面的理解，该指针在将来是指向一个函数的，那么现在应该能理解指针为啥指向函数了吧

综上所述，参数④是一个函数指针，该指针指向了一个函数，该函数的形参为(const void*, const void*)，该函数的返回类型为int。

接着分析，既然知道了参数④是一个函数指针，是指针，那么传参的时候肯定是需要传地址，传谁的地址？传函数的地址！

换句话说，如果我们想要使用qsort函数，那么我们需要一个形参一致，返回类型一致的函数，这个函数是需要使用qsort的人自己去实现的。因为只有使用qsort的人才知道自己想要比较什么，比较元素的类型又是什么。

那这个函数的返回值又有什么含义呢。
比较的两个元素分别e1,e2。
如果e1大于e2，返回一个大于0的数
如果e1小于e2，返回一个小于0的数
如果e1等于e2，返回0

那使用qsort的人去实现的这个函数作用是什么？是比较方法，不同的类型比较的方式是不同的！如果是数与数之间的比较，做差即可。如果是字符之间的比较呢？做差就不适合了，需要使用strcmp。

讲了这么多，相信你应该有所了解，或许还不太理解，也没关系，通过下面的实例来理解上面我所说的！

🎃qsort应用实例

主函数

#include
#include
#include
struct S   //定义一个结构体类型
{
    char name[10];
    int age;
};
int main()
{
    test1();
    test2();
    return 0;
}

🌳比较整形/浮点型

数与数之间的比较做差即可。
返回值也就是这个差值。
写的时候注意要强制类型转换，转换成什么类型的指针取决于你想要比较的元素类型，比较的是int类型就int*，比较的是float类型就float*

int int_cmp(const void* e1, const void* e2)
{
    return *(int*)e1 - *(int*)e2;
    //e1-e2排的是升序
    //降序的话，需要将e1,e2换个位置
}
void test1()
{
    int arr[10] = { 5, 2, 1, 3, 4, 6, 9, 8, 7, 10 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    qsort(arr, sz, sizeof(arr[0]), int_cmp);
    //arr是数组的地址，sz是数组元素的个数
    //sizeof(arr[0])，元素所占空间的大小
    //int_cmp，是函数的地址，该函数是使用qsort的人去实现
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

🌴比较结构体的整形

在对结构体排序的时候，需要注意的是 ()
(struct S*)e1->age这样写是不行的，需要将(struct S*)e1 当作一个整体去使用，需要加上 ()
写成((struct S*)e1)->age

int age_cmp(const void* e1, const void* e2)
{
    return ((struct S*)e1)->age - ((struct S*)e2)->age;
}
void test2()
{
    struct S s[] = { {"Zhang",40},{"Wang",20},{"Lisi",60} };
    //对结构体初始化
    int sz = sizeof(s) / sizeof(s[0]);
    //求数组的元素个数
    qsort(s, sz, sizeof(s[0]), age_cmp);
   //sizeof(s[0])，一个元素的大小
   //age_cmp，函数的地址。
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        printf("%s %d\n", s[i].name, s[i].age);
    }
}

🌵比较结构体的字符串

对一些字符串函数不了解的点这

这里还是要强调一下，注意 ()
strcmp()本身也是有个括号的。
strcmp的返回值：大于返回一个大于0的数，小于返回小于0的数，等于返回0。
写的时候可以先从里面的写起
先把(struct S*)e1)->name, ((struct S*)e2)->name写出来，然后在复制粘贴到strcmp()的()里。

int name_cmp(const void* e1, const void* e2)
{
    return strcmp(((struct S*)e1)->name, ((struct S*)e2)->name);   
}
void test2()
{
    struct S s[] = { {"Zhang",40},{"Wang",20},{"Lisi",60} };
    int sz = sizeof(s) / sizeof(s[0]);
    qsort(s, sz, sizeof(s[0]), name_cmp);
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        printf("%s %d\n", s[i].name, s[i].age);
    }
}

💡想成为一名优秀的程序猿，需要加点难度---- 模拟实现

🎈冒泡排序模拟实现

冒泡排序比较简单，这里就不再赘述如何来的了。
通过与普通版本的冒泡排序，对比去实现qsort的功能

✏普通版本的冒泡排序

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 - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])//比较
			{
			    //交换
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

模拟实现的函数可以对着qsort的去写
这个比较容易 void Bubble_sort2(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))

📄重点来了

冒泡排序中最主要的两个步骤是 比较 + 交换。

		if (arr[j] > arr[j + 1])//比较
		{
		    //交换
			int tmp = arr[j];
			arr[j] = arr[j + 1];			
			arr[j + 1] = tmp;	
		}

🎉先对比较进行转换

友情提示，需要对指针类型的意义要有所了解才能理解
不了解的点击"我"

base的类型是void*上面有铺垫过，void*不可直接使用，需要通过强制类型转换。那转换成什么呢？转换成int*合适吗？

显然不合适，这样写，那我们如何实现比较任意类型的呢？

回归本源，内存的基本单位是字节，不管是哪种类型的元素，元素所占空间的大小肯定是可以确定的。

那我们可以这样：以字节为单位去偏移，虽然每一次偏移的步长只有1个字节，但只要我们知道了，一个元素所占空间的大小有n个字节。

那从当前位置向后偏移n次，不就是n个字节嘛？不就能够在内存中取到一个元素的吗？

这样一理，base需要强制类型转换为char*，那类型的大小如何得知呢？不正是我们的参数③–>size_t size吗

或许你还没理解，用图带你理解一下。

那现在还有一个问题那如何取到每一个元素呢？

数组与指针访问是互通的(操作符之间可以互用)，不了解点"我"

原先的是这样写的if (arr[j] > arr[j + 1]) (指针类型是int*)我们是不是可以借鉴一下呢？
arr[j]等价于*(arr+j)
arr+j的含义是以arr为起始地址+j向后偏移j*4个字节和我们写的(char*)base+size（含义是以base为起始地址向后偏移size个字节）
相比，不就少了什么不就少了j*吗，那我们这样写(char*)base+size*j和上面arr+j所表达的意思不就一样了吗？

还有一种理解，我们已经知道(char*)base+size表示的是第一个元素（是以base为起始地址的第一个元素）那第二个元素不就是(char*)base+size + (char*)base+size，第三个元素是(char*)base+size + (char*)base+size + (char*)base+size，那第j个元素不就是 (char*)base+size * j 吗？

怎么理解方便就怎么选择。

元素每一个元素能够取出来了，那该如何比较呢？

轮到我们所写的比较函数出场了。比较方法的函数已经有了，我们只需要传参即可。这样调用的函数又被称为回调函数

哪种调用呢？ 以指针的形式去调用函数，这个函数就被称为回调函数

这里的指针可以不用解引用，直接当作函数来使用。
为什么可以这样呢？还记得上面有说过，函数名就表示函数的地址， 这个地址不就是指针吗？那这个指针不就是函数名吗？函数调用是函数名(参数),这样一换不就是 指针(参数) 吗

🎐该决解的问题已经解决，那开始实现----比较

if ( cmp((char*)base + j * width, (char*)base + (j + 1) * width) )

我这样写对吗？答案是不对，还少了点东西。我们这个函数返回值是一个整数，并不是 大于，小于，等于！ 要加上判断

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

或许有人会有疑问，为什么在对比较函数中，传参只需要传地址，就可以比较两个元素的大小。

这是指针类型的作用，指针的类型决定了解引用(*)能够操作多大的空间。

比较函数是使用者实现的，对应的元素类型也是明确的，在接收地址后，根据强制类型转换后的类型，进行解引用操作，可以取到对应的元素内容，那也就能完成比较。

🎉最后一步交换的实现

交换步骤先来看原冒泡的实现

	    //交换
		int tmp = arr[j];
		arr[j] = arr[j + 1];
		arr[j + 1] = tmp;

按照上面已经有的经验，想要实现对任意类型元素的交换，我们仍然只能通过强制类型转换为char*以字节为单位去实现。

如果你曾经有模拟实现过strcpy的话，那现在这个问题对你来说很容易就能完成的。

没有模拟过的话，且听我分析。
交换是两个元素互换，交换实现的步骤是以字节为单位，一个字节一个字节的交换，循环的条件应该是很容易想到的，什么时候交换完成了呢？当一个元素中最后一个字节交换后就完成了一次交换。

这里有一堆的字符串函数等着你来模拟实现，其中有两个是挺有难度的噢，快点“我”~

整个想法有了，也可以开始实现了。如果我们把这一“动作”封装成函数是不是更显得"高大上"呢？也确实可以这样实现，而且也美观。
函数名为Swap形参和返回类型是什么呢？
返回类型容易考虑我们不需要返回类型。
那形参是啥？比较的是两个元素，这两个肯定需要传过去。
再加上我们是以字节为单位进行交换的，那结束的条件也需要传，结束条件就是我们元素的大小。
讲到这那已经可以开始实现了。

🩸问题解决开始实现----交换

//函数调用（交换两个元素，以及元素的大小）
Swap( (char*)base + j * width ,(char*)base + (j + 1) * width ,width );

//函数实现，选择哪种循环都行。
void Swap(char* e1,char* e2, int width)
{
	int i = 0;
	for(i=0;i<width;i++)
	{
		char tmp = *e2;
		*e2 = *e1;
		*e1 = tmp;
		e1++;
		e2++;
	}
}

🛠冒泡排序模拟实现qsort完整代码

void Swap(char* e1, char* e2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *e2;
		*e2 = *e1;
		*e1 = tmp;
		e1++;
		e2++;
	}
}
void Bubble_sort2(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		for (j = 0; j < sz - 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 int_cmp(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
void test1()
{
	int arr[] = { 2,5,3,1,9,6,4,8,7,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Bubble_sort2(arr, sz, sizeof(arr[0]), int_cmp);
	print(arr, sz);
}

struct S
{
	char name[10];
	int age;
};
int struct_name_cmp(const void* e1, const void* e2)
{
	return strcmp(((struct S*)e1)->name, ((struct S*)e2)->name);
}

int struct_age_cmp(const void* e1, const void* e2)
{
	return ((struct S*)e1)->age - ((struct S*)e2)->age;
}
void test2()
{
	struct S s[] = { {"Zhang",40},{"Li",20},{"Wang",50} };
	int sz = sizeof(s) / sizeof(s[0]);
	//Bubble_sort2(s, sz, sizeof(s[0]), struct_name_cmp);
	Bubble_sort2(s, sz, sizeof(s[0]), struct_age_cmp);

	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s  %d\n", s[i].name, s[i].age);
	}
}
int main()
{
	
	//test1();
	test2();

	return 0;
}

对结构体年龄排序

对结构体姓名排序

对数组排序

🎈插入排序实现qsort

🎠原版插入排序

void Insert(int* arr, int sz)
{
	int i = 1;
	for (i = 1; i < sz; i++)
	{
		int t = arr[i];//待插入的元素
		int j = i - 1;
		while (j >= 0 && t < arr[j])
		{
			//交换
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = t;
	}
}
int main()
{
	int arr[10] = { 5,2,3,8,9,4,7,1,10,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	Insert(arr, sz);
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

✨关键处分析

插入排序需要注意的是这两个表达式int t = arr[i];和arr[j + 1] = t;为了达到实现任意类型的排序，肯定不能这样写。

那我是这样处理的：

为了存储插入的元素，你需要空间，需要多大根据元素的类型的大小。
我首先想到的是用动态内存函数，通过malloc开辟空间来存储要插入的元素。地址的类型需要设置为char*

另外如何实现赋值这一过程呢？
如果写过strcpy的模拟实现那应该也能够想到，我们可以通过Copy函数进行拷贝，就相当于完成了一次赋值。

一些函数的模拟实现写一遍，自己有更深的理解，很容易能想到，多去模拟实现这些函数也能提升自己代码能力。
点"我“，即可找到那些模拟的字符串函数

void Swap(char* e1, char* e2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *e2;
		*e2 = *e1;
		*e1 = tmp;
		e1++;
		e2++;
	}
}
void Copy(char* e1, const char* e2, int width)
{
	while (width)
	{
		*e1 = *e2;
		e1++;
		e2++;
		width--;
	}
}

void Insert2(void* base, int num, int size, int(*cmp)(const void* e1, const void* e2))
{
	int i = 1;
	char* t = (char*)malloc(size);
	if(NULL==t)//检测开辟是否成功
	{
	     perror("malloc");
	     return;
	}
	for (i = 1; i < num; i++)
	{
		//拷贝赋值
		Copy(t, (char*)base + size * i, size);

		int j = i - 1;
		//比较
		while (j >= 0 && cmp(t, (char*)base + size * j) < 0)
		{
			//交换
			Swap((char*)base + size * (j + 1), (char*)base + size * j, size);
		
			j--;
		}
		//拷贝赋值
		Copy((char*)base + size * (j + 1), t, size);
	}
	//对堆区开辟的空间释放
	free(t);
	//指针置为空，避免野指针
	t=NULL

}

测试

int struct_name_cmp(const void* e1, const void* e2)
{
	return strcmp(((struct S*)e1)->name, ((struct S*)e2)->name);
}

int struct_age_cmp(const void* e1, const void* e2)
{
	return ((struct S*)e1)->age - ((struct S*)e2)->age;
}


int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
void test2()
{
	struct S s[] = { {"Zhang",40},{"Li",20},{"Wang",50} };
	int sz = sizeof(s) / sizeof(s[0]);
	Insert2(s, sz, sizeof(s[0]), struct_name_cmp);
	Insert2(s, sz, sizeof(s[0]), struct_age_cmp);

	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s  %d\n", s[i].name, s[i].age);
	}
}

void test1()
{
	int arr[10] = { 5,2,3,8,9,4,7,1,10,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	Insert2(arr,sz,sizeof(int),cmp_int);
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	//test1();
	test2();
	return 0;
}

结束语

看完之后，还等什么呢，快点自己模拟实现一下属于你的qsort吧~