指针专题（4）【qsort函数的概念和使用】

1.前言

上节我们学习了指针的相关内容，本节我们在有指针的基础的条件下学习一下指针的运用，那么废话不多说，我们正式进入今天的学习

2.回调函数

我们既然已经学习了指针的相关基础，那么我们此时就可以用指针来实现回调函数

而回调函数又是什么呢？

回调函数是一个通过函数指针调用的函数

如果我们把一个函数的地址作为参数传递给第二个函数，当第二个函数被用来调用它所指向的第一个函数的时候，此时第一个函数就被称为回调函数；

我们来举一个例子，这样就会更通俗易懂：假如有A和B两个函数，如果把A的地址传递给B，当B被用来调用A函数的时候，此时A函数就是回调函数；

我们需要注意：回调函数并不是由函数的实现方直接调用的，而是在特定的情况下通过另外一方去调用的，也就是说，回调函数是一种机制，用于对特定的事件进行响应；

上一节我们学习了计算器的代码编写，我们就可以使用回调函数的知识对代码进行修改和优化

我们在使用回调函数改造前，我们通常会这样编写代码：

int add(int a, int b)
{
	return a + b;
}
int sub(int a, int b)
{
	return a - b;
}
int mul(int a, int b)
{
	return a * b;
}
int div(int a, int b)
{
	return a / b;
}
int main()
{
    int x, y;
    int input = 1;
    int ret = 0;
    do
    {
        printf("*************************\n");
        printf("  1:add           2:sub  \n");
        printf("  3:mul           4:div  \n");
        printf("  0:exit                 \n");
        printf("*************************\n");
        printf("请选择：");
        scanf("%d", &input);
        switch (input)
        {
        case 1:
            printf("输⼊操作数：");
            scanf("%d %d", &x, &y);
            ret = add(x, y);
            printf("ret = %d\n", ret);
            break;
        case 2:
            printf("输⼊操作数：");
            scanf("%d %d", &x, &y);
            ret = sub(x, y);
            printf("ret = %d\n", ret);
            break;
        case 3:
            printf("输⼊操作数： ");
            scanf("%d %d", &x, &y);
            ret = mul(x, y);
            printf("ret = %d\n", ret);
            break;
        case 4:
            printf("输⼊操作数：");
            scanf("%d %d", &x, &y);
            ret = div(x, y);
            printf("ret = %d\n", ret);
            break;
        case 0:
            printf("退出程序\n");
            break;
        default:
            printf("选择错误\n");
            break;
        }
    } while (input);
    return 0;
}

此时的代码重复率非常高，代码非常冗余

我们若想要对代码进行优化，我们需要注意以下几点：

1.我们要把相似代码抽象成函数

2.我们学习了函数指针以后，我们知道了：函数的调用可以使用函数名来调用也可以使用函数指针来调用；我们可以通过参数的差异来计算不同的逻辑

有了这些理论基础我们就可以对代码进行修改了：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
int add(int a, int b)
{
	return a + b;
}
int sub(int a, int b)
{
	return a - b;
}
int mul(int a, int b)
{
	return a * b;
}
int div(int a, int b)
{
	return a / b;
}

void calc(int(*pf)(int, int))
{
    int x, y;
    int ret = 0;
    printf("输入操作数：");
    scanf("%d %d", &x, &y);
    ret = pf(x, y);
    printf("ret = %d\n", ret);
}
int main()
{
    int input = 1;
    do
    {
        printf("*************************\n");
        printf("  1:add           2:sub  \n");
        printf("  3:mul           4:div  \n");
        printf("  0:exit                 \n");
        printf("*************************\n");
        printf("请选择：");
        scanf("%d", &input);
        switch (input)
        {
        case 1:
            calc(add);
            break;
        case 2:
            calc(sub);
            break;
        case 3:
            calc(mul);
            break;
        case 4:
            calc(div);
            break;
        case 0:
            printf("退出程序\n");
            break;
        default:
            printf("选择错误\n");
            break;
        }
    } while (input);
    return 0;
}

我们这个方法就是把一个函数的地址传递给了另外一个函数，然后通过另外一个函数用函数指针去调用要使用的函数

3.qsort函数

我们刚才学习了回调函数，我们现在接着来学习一个和回调函数逻辑差不多的函数：qsort函数

qsort函数是一个用来排序的函数，它是一个库函数，可以直接拿来排序，其底层原理使用的是快速排序的方式

我们之前说过：函数排序的底层方式有很多，大致包括：选择排序、插入排序、冒泡排序、快速排序、希尔排序等

我们先来思考一下qsort函数为什么被设计出来呢？它的存在相比较其他的函数有什么优势呢？

我们首先将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;
            }
        }
    }

}
void print_arr(int arr[], int sz)
{
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main(void)
{
    //冒泡排序，排序为升序
    int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    bubble_sort(arr, sz);
    print_arr(arr, sz);
    return 0;
}

写完代码以后我们可以发现冒泡排序的局限性：因为冒泡排序数据传入的时候已经确定了类型，冒泡排序只能排序一种类型的数据，如果排序的是整型，则无法排序字符串、结构体数据等；如果要用冒泡排序排序字符串有需要重新创造一个函数，这样就会导致代码重复率高，代码冗杂等问题

此时我们就可以了解一下qsort函数，qsort函数可以排序任意类型的数据，我们来看一下qsort函数的使用方法：

我们通过上图可以知道，qsort函数使用需要包含头文件<stdlib.h>，而且qsort函数的使用需要4个变量：

1.void* base，该变量是一个指针变量，指针指向的是待排序数组的第一个元素

2.size_t num，该变量表示的是待排序数组里面的元素个数

3.size_t size，该变量表示的是待排序数组里面每个元素的大小

4.int (*compar)(const void*, const void*)，该变量是一个函数指针，该函数指向一个函数，这个函数的功能是用来比较两个元素的大小。这个概念有点抽象，我们逐步理解：

刚才我们编写了冒泡排序的代码，假设我们需要在原冒泡排序代码的基础上改造冒泡排序。让它能够排序任意类型的数据，我们来思考一下哪些地方需要修改？

我们在两个数据的比较方式这里不能直接用大于号或者小于号比较，只有整型元素可以直接用>、<比较，字符串、结构体等元素是不能用>、<比较的，而是使用strcmp函数等其他方法比较

所以要想比较所有类型的数据，我们比较的代码就需要修改：

此时我们就不能直接比较，应该要把比较两个元素的方法封装成一个函数，然后把函数的地址传递给排序函数。如果传递的是整型比较函数的地址，那么就按照整型的比较方式比较；如果传递的是字符比较函数的的地址，那么就按照字符串的比较方式比较......

其实这种方法就是qsort的比较方法， qsort函数的第四个变量指向的就是两个元素的比较函数，所以我们要传入两个元素比较函数的地址，这里的传入需要我们自己实现，因为qsort函数的实现者并不知道要排序的数据的类型，只有qsort函数的使用者知道要排序的数据的类型，所以需要我们自己提供两个元素的比较函数，然后把比较函数的地址传给qsort函数，qsort函数内部在比较的时候就会调用这个函数；

那么知道了qsort函数的原理，我们来写一串代码使用qsort函数排序整型数据：

我们要想用qsort函数排序整型数据，那么我们需要自己完成整型数据比较的函数，并将函数地址传给qsort函数：

我们可以看到，第四个变量的形式是：int (*compar)(const void*, const void*)

所以我们在写代码的时候就需要按照以上的形式来确定变量的类型，这样qsort函数才能顺利接收到函数

我们可以看到，compare函数的两个参数的类型都是const void*，此时p1中存放的是第一个要比较元素的地址，p2中存放的是第二个要比较元素的地址，如果p1指向的元素大于p2指向的元素，那么将返回一个大于0的数字；如果p1指向的元素小于p2指向的元素，那么将返回一个小于0的数字；如果p1指向的元素等于于p2指向的元素，那么将返回一个等于0的数字；

如果要对两个元素进行比较，不能够直接解引用，因为p1和p2两个变量的类型是void* ，是没有具体类型的，我们不能直接解引用，也不能进行+-整数的运算。此时我们就需要强制类型转换，转换完以后再进行解引用

有了这些理论基础，我们此时就可以写出代码如下：

int cmp_int(const void* p1, const void* p2)
{
    if (*(int*)p1 > *(int*)p2)
        return 1;
    else if (*(int*)p1 == *(int*)p2)
        return 0;
    else
        return -1;
}

现在我们就可以完成全代码的书写了：

void print_arr(int arr[], int sz)
{
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int cmp_int(const void* p1, const void* p2)
{
    if (*(int*)p1 > *(int*)p2)
        return 1;
    else if (*(int*)p1 == *(int*)p2)
        return 0;
    else
        return -1;
}

void test01()
{
    int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    qsort(arr, sz, sizeof(arr[0]), cmp_int);
    print_arr(arr, sz);
}

int main(void)
{
    test01();
    return 0;
}

代码运行成功，编写成功

如果我们再仔细思考一下，我们可以发现比较函数的代码可以简化：

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

我们可以直接让两个变量解引用的值做差，也可以完成该函数的功能，并且代码量更少，更加简洁

如果我们需要对元素进行降序比较，我们修改代码也同样很方便，我们只需要让后面的元素减去前面的元素就可以实现降序的功能：

void print_arr(int arr[], int sz)
{
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

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

void test01()
{
    int arr[] = { 5,8,7,6,9,4,3,2,1,0 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    qsort(arr, sz, sizeof(arr[0]), cmp_int);
    print_arr(arr, sz);
}

int main(void)
{
    test01();
    return 0;
}

既然我们刚才已经学习了使用qsort函数排序整型数据，我们接着来用qsort函数排序一下结构体

我们知道，结构体是不能直接用>、<号来比较的，我们先来定义一个结构体：

struct Stu
{
    char name[20];
    int age;
};

我们定义了一个学生的结构体，结构体成员为学生的姓名和年龄，我们若是要对结构体进行排序，那么我们就有两种排序方法：

1.我们可以通过年龄来排序

2.我们可以通过姓名来排序

我们先来创建一个数组用于存储结构体数据：

    struct Stu arr[3] = { {"zhangsan",20},{"lisi",35},{"wangwu",18} };

1.我们先写用姓名来排序的代码：

要想通过姓名来排序，我们需要使用到strcmp函数：

strcmp 是按照对应字符串的字符的ASCII码值进行比较的函数

我们发现strcmp的返回值非常适合我们自己写的比较函数，所以我们可以写出代码如下：

int cmp_stu_by_name(const void* p1, const void* p2)
{
    return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}

我们先要对p1、p2强制类型转换为结构体类型，再通过结构体成员访问操作符->来找到姓名，再使用strcmp函数进行比较

通过这些，我们就可以很轻易的写出代码：

struct Stu
{
    char name[20];
    int age;
};

int cmp_stu_by_name(const void* p1, const void* p2)
{
    return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}

void print_arr(struct Stu arr[], int sz)
{
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        printf("%s ", arr->name);
        arr++;
    }
    printf("\n");
}

void test02()//结构体
{
    struct Stu arr[3] = { {"zhangsan",20},{"lisi",35},{"wangwu",18} };
    int sz = sizeof(arr) / sizeof(arr[0]);
    qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);
    print_arr(arr, sz);
}




int main(void)
{
    test02();
    return 0;
}

2.接下来我们再来按年龄排序

（代码相似度很高，逻辑差不多，所以不作详解，请自主思考解题过程谢谢）

struct Stu
{
    char name[20];
    int age;
};



int cmp_stu_by_age(const void* p1, const void* p2)
{
    return (((struct Stu*)p1)->age - ((struct Stu*)p2)->age);
}

void print_arr(struct Stu arr[], int sz)
{
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr->age);
        arr++;
    }
    printf("\n");
}

void test02()//结构体
{
    struct Stu arr[3] = { {"zhangsan",20},{"lisi",35},{"wangwu",18} };
    int sz = sizeof(arr) / sizeof(arr[0]);
    qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_age);
    print_arr(arr, sz);
}




int main(void)
{
    test02();
    return 0;
}

模拟实现qsort函数

刚才我们学习了qsort函数的概念以及使用，现在我们来模仿qsort函数来实现一个冒泡排序的函数，这个函数可以排列任意类型的数据

因为我们要接受任意类型的数据，所以我们接受参数的临时变量的类型就不能是int，我们就需要将变量类型改成void* ，可以用来接收任意类型的数据

此时函数的参数就可以直接修改成qsort函数里的参数：

void bubble_sort(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2));

我们可以不用修改趟数只需要改变比较数据的方式

            if (cmp()>0)

那么此时cmp函数里面应该存入什么参数呢？我们应该存入arr[j]和arr[j+1]的地址，此时我们不能直接用&找到地址，我们应该用什么方法来取到它们的地址呢？

如果我们要找到下标为0和下标为1处的地址，我们知道下标为0处的地址就是base，下表为1处的地址就为base处的地址跳过width个字节，因为base是void* 类型的地址，不能进行+-操作，所以此时我们就需要把base转换成char* 类型的变量，然后再+width

所以arr[j]处的地址就为 (char*)base+j*width,arr[j+1]处的地址就为 (char*)base+(j+1)*width

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

此时我们交换的具体代码也需要改变，我们封装一个函数Swap，用于交换

我们需要往Swap函数里面传入3个参数：

Swap(cmp((char*)base + j * width, (char*)base + (j + 1) * width), width);

有了这些理论基础，我们就能很轻易的写出代码如下：

结尾

本节我们学习了指针的相关运用，加强了对指针的理解，下一节是指针的最后一节，谢谢您的浏览！！！