C中qsort的应用
使用qsort的起因是锐格并不支持C++库文件，手敲排序又很麻烦。
介绍
void qsort(void *arr, size_t n, size_t size, int (*cmp)(const void *, const void *))
arr表示要排序的序列，可以是数组名或指针n表示arr中有多少待排序的元素size表示arr中单个元素的大小（如果是动态分配内存的序列要注意）cmp表示自定义的比较函数
cmp函数
int cmp(const void *a, const void *b) {
return;
}这里要注意的是，cmp入参的a和b，是arr中的元素，即如果arr是数组，则a、b表示指向数组中某个元素的指针，如果arr是二维数组（数组的数组），则a、b表示指向arr中某个数组的指针
列举一下有哪些情况会用到qsort
- 整数类：一维数组（动态分配内存的一维数组/指针）、简单二维数组（动态分配内存的二维数组/二维指针，m2）、复杂二维数组（mn）
- 字符串类：单一字符串、字符串数组
- 数据结构类：数据结构数组
注：以下所有排序均为升序（从小到大），若要降序排序，把cmp中a、b颠倒即可
1. 一维数组（动态分配内存的一维数组/指针）
int cmp(const void *a, const void *b) {
return *(int*)a - *(int*)b; /* a、b分别指向arr1/arr2中某个元素 */
}
int main()
{
int arr1[] = { 5, 8, 6, 1, -3, 0, 1, 4 };
qsort(arr1, sizeof(arr1) / sizeof(arr1[0]), sizeof(arr1[0]), cmp);
int *arr2 = (int*)calloc(8, sizeof(int));
arr2[0] = 5; arr2[1] = 8; arr2[2] = 6; arr2[3] = 1; arr2[4] = -3; arr2[5] = 0; arr2[6] = 1; arr2[7] = 4;
qsort(arr2, 8, sizeof(arr2[0]), cmp); /* 如果将8改成sizeof(arr2) / sizeof(arr2[0])，排序会失败 */
}一维数组的两种表示方式，第一种直接定义成数组，第二种动态分配内存（请忽略这笨拙的初始化方式...），之所以提动态分配内存，是因为c中指针是核心，这种动态分配内存的方式除了初始化，熟练之后确实比直接定义成数组要方便 两种定义方式对应的排序，是有细微差别的，如果把arr2的qsort第二个参数改成sizeof(arr2) / sizeof(arr2[0])，会报错，因为数组名arr1虽然可以等价为指针，但sizeof(arr1)的值是整个数组的大小，而sizeof(arr2)只是int*型指针arr2的大小，4个字节（32位计算机） 可能这里qsort的第二个参数更习惯于写成具体变量或者数字，但第三个参数，随着序列arr变得复杂，变成二维，这种写法便会再次出现问题，具体见二维数组的排序
2. 二维数组（动态分配内存的二维数组/二维指针）（维度为m*2）
int cmp1(const void *a, const void *b) {
int *m = (int*)a, *n = (int*)b; /* 此处为了看起来清晰一些，定义m、n来取代a、b，这里可以看到，入参的是一维指针类型，也就是之前所说的arr1的某个元素，即以为指针 */
if (m[0] != n[0]) {
return m[0] - n[0];
}
else {
return m[1] - n[1];
}
}
int cmp2(const void *a, const void *b) {
int *m = *(int**)a, *n = *(int**)b; /* 与上面不同的是，这里入参的是二维指针，即arr2入参，重要！！！ */
if (m[0] != n[0]) {
return m[0] - n[0];
}
else {
return m[1] - n[1];
}
}
int main()
{
int arr1[10][2] = { {1, 5}, {2, 3}, {0, 1}, {8, 3}, {1, 0}, {4, 8}, {3, 2}, {2, 9}, {2, 1}, {1, 0} };
qsort(arr1, 10, sizeof(arr1) / 10, cmp1); //qsort(arr1, 10, sizeof(int*), cmp1);
int **arr2 = (int**)calloc(10, sizeof(int*));
for (int i = 0; i < 10; i++) {
arr2[i] = (int*)calloc(2, sizeof(int));
arr2[i][0] = rand() % 9;
arr2[i][1] = rand() % 9;
}
qsort(arr2, 10, sizeof(int*), cmp2); /* 由于之前说过对指针sizeof的话，得到的大小是指针大小，而入参的是二维指针，而非二维数组，二维指针的元素为以为指针，因此这里的单个元素大小是以为int*的大小 */
qsort(arr2, 10, sizeof(int) * 2, cmp2); /* 单个元素大小也可以写成sizeof(int) * 2，因为arr2中每个元素都包含两个int型 */
}注： 这里首先需要说一下二维数组和动态分配内存的二维指针的本质区别，它们在使用时几乎没什么区别，但在内存中的存储形式确实不同的，通过int arr1[10][2]的方式定义的二维数组，二维数组所占用的1024个字节的内存空间是连续的，而动态分配内存则是先开辟出一块存放10个int型指针的内存，然后再分别对这10个int指针分别进行开辟内存，因此动态分配内存的二维指针的内存不是连续的，因此，二维数组的第一个元素是第一个一维数组的第一个元素（从值上看，指向第一个一维数组和指向第一个一维数组的第一个元素的指针是相等的，但含义上却不同），但二维指针的第一个元素，只能是第一个int*型指针
从上面可以看出，二维数组arr1和二维指针arr2虽然在本质上都是地址，但在qsort排序中cmp的写法是不同的 cmp1中，qsort把传入的arr1当做指向数组第一个元素的指针，arr1的第一个元素是arr1[0][0]，所以cmp1的两个参数a和b，是指向“arr1[i][0]”的指针，类型为int*型 cmp2中，qsort把传入的arr2当做指向数组第一个元素的指针，而arr2的第一个元素是一个指向整数数组的指针，所以cmp2的两个参数a和b，是指向“指向整形数组的指针”的指针，类型为int**型
写qsort(arr1, 10, sizeof(arr1) / 10, cmp1);时，第二个参数是元素个数，指10个一维数组，第三个参数与第二个参数对应，指一维数组的大小（注意是一维数组占内存的大小，而不是指向该一维数组的指针的大小，即不能写成sizoef(int)） 同时，写qsort(arr2, 10, sizeof(int), cmp2);时，第二个参数是元素个数，指10个int型元素，第三个参数是每个int型元素的大小
在写cmp函数时，必须有第一行定义m、n并进行赋值，这样不容易混乱，第一行定义完后，后面的内容完全可以写的一样 cmp1的第一行，传入的是指向arr1第一个元素arr1[i][0]的int型指针，但前面说过，指向arr1[i][0]的int型指针与指向arr1[i]的int型指针值是相同的，因此赋值之后的m和n可以当成指向arr1[i]的指针用 cmp2的第一行，传入的是指向arr2第一个元素arr2[i]的int型指针，赋值后的含义与cmp1的理解是相同的，因此后面的代码cmp1和cmp2通用
3. 二维数组（动态分配内存的二维数组/二维指针）（维度为m*n）
#define MAX 3 //这里用用定义，因为main函数中的数组维度无法传进cmp中，只能用宏定义或全局变量
int cmp1(const void *a, const void *b) {
int *m = (int*)a, *n = (int*)b;
for (int i = 0; i < MAX; i++) { //用循环进行
if (m[i] != n[i]) {
return m[i] - n[i];
}
}
}
int cmp2(const void *a, const void *b) {
int *m = *(int**)a, *n = *(int**)b;
for (int i = 0; i < MAX; i++) {
if (m[i] != n[i]) {
return m[i] - n[i];
}
}
}
int main()
{
int arr1[10][MAX] = { {1, 5, 3}, {2, 3, 1}, {0, 1, 0}, {8, 3, 1}, {1, 0, 2}, {4, 8, 5}, {3, 2, 2}, {2, 9, 6}, {2, 1, 7}, {1, 0, 9} };
qsort(arr1, sizeof(arr1) / sizeof(arr1[0]), sizeof(arr1[0]), cmp1);
int **arr2 = (int**)calloc(10, sizeof(int*));
for (int i = 0; i < 10; i++) {
arr2[i] = (int*)calloc(MAX, sizeof(int));
arr2[i][0] = rand() % 9;
arr2[i][1] = rand() % 9;
arr2[i][2] = rand() % 9;
}
qsort(arr2, 10, sizeof(int) * 2, cmp2);
qsort(arr2, 10, sizeof(int*), cmp2);
}m2实际上是mn的一种特殊形式，因此m2也可以使用mn的cmp函数，只是m2维度只有2，也可以直接用条件if返回 另外，由于mn的cmp中循环需要有终止条件，而终止条件的设定需要数组定义时的维度，此维度无法以参数的形式传进cmp，而在cmp中数组是以指针的形式存在的，sizeof也无法获取数组维度，因此只能通过宏定义或全局变量的形式将维度传入
4. 字符串（字符数组）
字符串实际上就是一个字符数组，因此排序跟以为数组没有什么本质差别，只是强制类型转换改成char*型即可
int cmp(const void *a, const void *b) {
return strcmp((char*)a, (char*)b); strcmp中参数为地址值，即指针，因此不用解引用
//return *(char*)a - *(char*)b; //与上一行等价
}
int main() {
char str1[] = "azsxdcfvg";
qsort(str1, strlen(str1), sizeof(char), cmp);
//char *str2 = (char*)"azsxdcfvg"; //不能用这种方式定义，会报莫名其妙的错
char *str2 = (char*)calloc(strlen("azsxdcfvg") + 1, sizeof(char));
strcpy(str2, "azsxdcfvg");
qsort(str2, strlen(str2), sizeof(char), cmp);
}定义字符串要么直接定义成字符数组，要么动态开辟内存，然后用strcpy进行拷贝，用指针直接指向字符串会报莫名其妙的错
5. 字符串数组
int cmp1(const void *a, const void *b) {
return strcmp((char*)a, (char*)b);
}
int cmp2(const void *a, const void *b) {
return strcmp(*(char**)a, *(char**)b);
}
int main() {
char str1[][10] = { "iosd", "adw", "werws", "sdf", "abc" }; //正统字符串数组
qsort(str1, sizeof(str1) / sizeof(str1[0]), sizeof(str1[0]), cmp1); //①
char *str2[] = { "iosd", "adw", "werws", "sdf", "abc" }; //字符串指针数组
qsort(str2, sizeof(str2) / sizeof(str2[0]), sizeof(char*), cmp2); //②
char **str3 = (char**)calloc(5, sizeof(char*)); //动态开辟的用于存放字符串的二维指针
for (int i = 0; i < 5; i++) {
str3[i] = (char*)calloc(10, sizeof(char));
}
strcpy(str3[0], "iosd");
strcpy(str3[1], "adw");
strcpy(str3[2], "werws");
strcpy(str3[3], "sdf");
strcpy(str3[4], "abc");
qsort(str3, 5, sizeof(char*), cmp2); //③
}①str1最普通的字符串数组，可以看做多维字符数组，qsort各参数写法与二维整数数组相同 ②str2为字符串指针数组，即存放指向字符串的指针的数组，第二个参数中sizeof(str2)表示数组大小，大小不是所有字符串字符个数之和，而是元素个数4，因为其存放的是指针，大小为固定的4，因此sizeof(str2[i]])(i=1,2,3,4)为固定值4，类比动态开辟内存的多维整数指针，传入cmp2的是一个类型为char**的二维地址 ③str3位动态开辟的用于存放字符串的二维指针，qsort写法与二维整数指针相同，同样可以使用cmp2
6. 数据结构数组
结合一个自拟的题目来讲一下结构体数组的快排有什么作用吧 题目：
给定一个字符串序列{ "acd", "fsfe", "aae", "sw", "servb", "fsvbs", "wg" }，对其进行排序，排序要求为：①根据字符串长度进行排序；②字符串长度相同时，根据字符串字符对应ASCII值进行排序
struct STR {
int len;
char *str;
};
int cmp(const void *a, const void *b) { //cmp的写法比较灵活，可以根据排序需要进行修改
struct STR *m = (struct STR*)a, *n = (struct STR*)b;
if (m->len != n->len) {
return m->len - n->len;
}
else {
return strcmp(m->str, n->str);
}
}
int main() {
char *str[8] = { "acd", "fsfe", "aae", "sw", "servb", "fsvbs", "wg" }; //题目给定的字符串序列
struct STR *arr = (struct STR*)calloc(8, sizeof(struct STR));
for (int i = 0; i < 7; i++) { //对结构体len和str进行赋值
arr[i].len = strlen(str[i]);
arr[i].str = (char*)calloc(10, sizeof(char));
strcpy(arr[i].str, str[i]);
}
qsort(arr, 7, sizeof(struct STR), cmp);
}用打印来看一下结果
这道题目本身其实在布建立结构体的情况下也可以做，建立结构体只是说明一种情况，在需要将不同的数据类型绑定在一起进行综合排序的时候，可以考虑先通过建立结构体进行绑定，再对结构体进行排序 再附一道例题https://leetcode-cn.com/problems/find-and-replace-in-string/，这道题目如果先将三个不同类型的序列进行绑定，然后倒序排序，在替换的时候会方便很多
总结
总的来说，多维数组qsort的写法主要分为两种
（1）普通数组的定义方式，如int arr[10][2]、char str[10][5]的方式定义的二维数组或字符串数组
qsort(arr, NUM, sizeof(arr) / NUM, cmp);
此写法中NUM为二维数组或字符串数组的维度（10），由于是最普通的定义方式，因此sizeof(数组名)的结果为数组占用内存大小，因此单个元素大小为sizeof(arr) / NUM
cmp第一行m、n赋值写法为
int cmp(const void *a, const void *b)
{
char *m = (int*)a, *n = (int*)b;
return ;
}（2）指针数组的定义方式，如int **arr = (int**)calloc(...)、char *str[10]的方式定义的指针数组
qsort(arr, NUM, sizeof(int*), cmp)此写法中NUM为指针数组的维度（10），第三个参数为数组中单个指针的大小
cmp第一行m、n赋值写法为
int cmp(const void *a, const void *b)
{
char *m = *(int**)a, *n = *(int**)b;
return ;
}
