0
0

玩转qsort——“C”

各位CSDN的uu们你们好呀，今天小雅兰的内容还是我们的深度剖析指针呀，上篇博客我们学习了回调函数这个知识点，但是没有写完，因为：小雅兰觉得qsort值得单独写出来！！！好啦，就让我们进入指针的世界吧

*qsort是一个库函数，是用来排序的库函数，使用的是快速排序的***方法 **

quicksort

我们先来复习一下之前所学习过的一种算法——冒泡排序

冒泡排序——“C”_认真学习的小雅兰.的博客-CSDN博客

#define _CRT_SECURE_NO_WARNINGS 1
#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 - 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]);
    }
}
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);
    //打印
    print_arr(arr, sz);
    return 0;
}

但是，这个算法最大的缺点就是只能排序整型，如果未来要排序浮点数呢？如果未来要排序一些字符串呢？结构体呢？那么，这个函数就搞不定了，仅仅能排序固定类型的数据

** qsort的好处：**

  • 现成的
  • 可以排序任意类型的数据

void**qsort(voidbase***,//指向了待排序数组的第一个元素**

** size_tnum,//待排序的元素个数**

** ** size_twidth,//每个元素的大小，单位是字节

** ** int(__cdeclcompare)(constvoid******elem1,constvoid***elem2)

** //函数指针**

** //指向一个函数，这个函数可以比较两个元素的大小**

** );**

qsort是可以排序任意类型的数据的

  1. 比较两个整数的大小，> < =
  2. 比较两个字符串，strcmp
  3. **比较两个结构体数据（学生：张三、李四），指定比较的标准，拿什么比较？ **

int a=10;

void * p=&a;

//void * ——无具体类型的指针，所以它可以接收任何类型的地址

**//p;//err void的指针不能使用解引用操作符**

//p++;//err

下面，我们来使用一下qsort函数：

#include<stdio.h>
#include<stdlib.h>
//qsort函数的使用者提供这个函数
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");
}
test1()
{
    int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    //使用qsort来排序整型数组，这里就要提供一个比较函数，这个比较函数能够比较2个整数的大小
    //qsort默认是排成升序的
    qsort(arr, sz, sizeof(arr[0]), cmp_int);
    print_arr(arr, sz);
}
int main()
{
    test1();
    return 0;
}

qsort这个库函数是不是很神奇呢？下面还有更加神奇的！！！

我们来测试一下qsort排序结构体数据

#include<stdio.h>
#include<stdlib.h>
//qsort函数的使用者提供这个函数
int cmp_int(const void* p1, const void* p2)
{
    return *(int*)p1 - *(int*)p2;
}
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(struct Stu* ps, int sz)
{
    int i = 0;
    for (i = 0; i < 3; i++)
    {
        printf("%d\n", ps[i].age);
    }
}
void test2()
{
    struct Stu s[] = { {"zhangsan",30},{"lisi",25 }, { "wangwu",50 } };
    int sz = sizeof(s) / sizeof(s[0]);
    //测试按照年龄来排序
    qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);
    print(s, sz);
}
int main()
{
    test2();
    return 0;
}


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
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(struct Stu *ps, int sz)
{
    int i = 0;
    for (i = 0; i < 3; i++)
    {
        printf("%s\n", ps[i].name);
    }
}
void test2()
{
    struct Stu s[] = { {"zhangsan",30},{"lisi",25},{"wangwu",50} };
    int sz = sizeof(s) / sizeof(s[0]);
    //测试按照名字来排序
    qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
    print(s, sz);
}
int main()
{
    test2();
    return 0;
}

qsort底层是快速排序，但是小雅兰还没有学习快速排序的思想，所以暂时还不能之间实现qsort，所以使用冒泡排序的思想来实现一个类似于qsort这个功能的冒泡排序函数bubble_sort

使用回调函数，模拟实现qsort（采用冒泡的方式）。

测试函数：

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

主函数：

int main()
{
    test3();
    return 0;
}

模拟实现的bubble_sort()函数：

//假设排序为升序
//希望这个bubble_sort函数可以排序任意类型的数据
void bubble_sort(void* base, size_t num, size_t width, int(*cmp)(const void* p1, const void* p2))
{
    //base 待排序数组的第一个元素
    //元素个数和元素个数的大小不可能是负数，所以是size_t类型
    //函数指针
    //要确定趟数
    size_t i = 0;
    for (i = 0; i < num - 1; i++)
    {
        //一趟冒泡排序的过程
        size_t j = 0;
        int flag = 1;//假设已经有序了
        //标记变量
        for (j = 0; j < num - 1 - i ; j++)
        {
            //两个相邻的元素比较
            //arr[j] arr[j+1]
            if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
            {
                //强制类型转换为char*
                //因为base为void类型，不能之间进行加减乘除，所以强制类型转换，但是又不能转换为int*，因为不一定就排序整型数组
                flag = 0;
                //交换
                Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
            }
        }
        if (flag == 1)
        {
            break;
        }
    }
}

在bubble_sort()函数中，调用了自定义的函数Swap，是用来交换元素的：

int cmp_int(const void* p1, const void* p2)//不知道要排序什么类型的数组,所以用void*
{
    return *(int*)p1 - *(int*)p2;
}
void Swap(char* buf1, char* buf2,int width)
{
    int i = 0;
    for (i = 0; i < width; i++)
    {
        char tmp = *buf1;
        *buf1 = *buf2;
        *buf2 = tmp;
        buf1++;
        buf2++;
    }
}

打印函数：

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

完整代码如下所示：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int cmp_int(const void* p1, const void* p2)//不知道要排序什么类型的数组,所以用void*
{
    return *(int*)p1 - *(int*)p2;
}
void Swap(char* buf1, char* buf2,int width)
{
    int i = 0;
    for (i = 0; i < width; i++)
    {
        char tmp = *buf1;
        *buf1 = *buf2;
        *buf2 = tmp;
        buf1++;
        buf2++;
    }
}
//假设排序为升序
//希望这个bubble_sort函数可以排序任意类型的数据
void bubble_sort(void* base, size_t num, size_t width, int(*cmp)(const void* p1, const void* p2))
{
    //base 待排序数组的第一个元素
    //元素个数和元素个数的大小不可能是负数，所以是size_t类型
    //函数指针
    //要确定趟数
    size_t i = 0;
    for (i = 0; i < num - 1; i++)
    {
        //一趟冒泡排序的过程
        size_t j = 0;
        int flag = 1;//假设已经有序了
        //标记变量
        for (j = 0; j < num - 1 - i ; j++)
        {
            //两个相邻的元素比较
            //arr[j] arr[j+1]
            if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
            {
                //强制类型转换为char*
                //因为base为void类型，不能之间进行加减乘除，所以强制类型转换，但是又不能转换为int*，因为不一定就排序整型数组
                flag = 0;
                //交换
                Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
            }
        }
        if (flag == 1)
        {
            break;
        }
    }
}
void print_arr(int arr[], int sz)
{
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
void test3()
{
    int arr[] = { 3,1,5,2,4,9,8,6,7,0 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
    print_arr(arr, sz);
}
int main()
{
    test3();
    return 0;
}

好啦，小雅兰玩转的qsort就到这里啦，这篇博客难度很大，确实花了小雅兰很多时间，未来还要继续加油呀！！！

标签： c语言 开发语言
本文转载自: https://blog.csdn.net/weixin_74957752/article/details/129272380
版权归原作者 认真学习的小雅兰. 所有， 如有侵权，请联系我们删除。
登录后发布评论

“玩转qsort——“C””的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

安全见闻 -- 二进制与网络安全的关系

如何在社媒平台上使用代理IP来保护帐号安全

Linux笔记---gcc/g++与编译链接

爬虫开发工具与环境搭建——使用Postman和浏览器开发者工具

【Docker容器】一、一文了解docker

实现鼠标悬停图片切换的动态交互

Hadoop在 IntelliJ IDEA 中打包并提交 MapReduce 程序

文章导航