C语言快排函数qsort的使用与实现

淩亂°似流年 2024-03-30 15:53 112阅读 0赞

## 1.参数讲解 ##

qsort是C语言的快排函数，头文件\#include<stdlib.h>一共包含四个参数。

qsort(a,n,sizeof(a[0]),cmp);

我们直接拿代码来举例子：

#include<stdio.h>
    #include<stdlib.h>
    int cmp(const void* e1, const void* e2)
    {
        return *(int*)e1 - *(int*)e2;
    }
    int main()
    {
        int arr[] = { 22,1,3,44,33,9 };
        int sz = sizeof(arr) / sizeof(arr[0]);
        qsort(arr, sz, sizeof(arr[0]), cmp);
        int i = 0;
        for (i = 0; i < sz; i++)
        {
            printf("%d ", arr[i]);
        }
        return 0;
    }

运行结果：

![cca36a37d00f371505312acf598a2135.png][]

这里我们会发现一个特别的参数cmp，那么cmp的作用是什么呢？

int cmp(const void* e1, const void* e2)
    {
        return *(int*)e1 - *(int*)e2;
    }

cmp是比较e1,e2大小的，就是将arr中传来两个数字来通过做差来比较其大小，**cmp函数的返回值，<0(不进行置换)，>0(进行置换)，0(不进行置换)。**

#include<stdio.h>
    #include<stdlib.h>
    int cmp(const void* e1, const void* e2)
    {
        //return *(int*)e1 - *(int*)e2;
        return *(int*)e2 - *(int*)e1;
    }
    int main()
    {
        int arr[] = { 22,1,3,44,33,9 };
        int sz = sizeof(arr) / sizeof(arr[0]);
        qsort(arr, sz, sizeof(arr[0]), cmp);
        int i = 0;
        for (i = 0; i < sz; i++)
        {
            printf("%d ", arr[i]);
        }
        return 0;
    }

运行结果：

![872aa6ef27c4ec93b72fe080e660b256.png][]

1.  ## 结构体、字符串等排序使用 ##

**结构体数据：**

#include<stdio.h>
    #include<stdlib.h>
    struct Stu
    {
        char name[20];
        int age;
    };
    int cmp_stu_by_age(const void* e1, const void* e2)
    {
        return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
    }
    
    void test1()
    {
        struct Stu s1[3] = { {"zhangsan",22},{"lishi",11},{"wanger",33} };
        int sz = sizeof(s1) / sizeof(s1[0]);
        qsort(s1, sz, sizeof(s1[0]), cmp_stu_by_age);
    }
    int main()
    {
        test1();
        return 0;
    }

运行结果：

![75b081ae136d7ea26055e9f6af1aaba4.png][]

**结构体字符：**

对字符串是如何比较大小的呢？字符是以ASCLL值在内存中存储的，所以关于字符的比较，就是字典序的比较，而字典序的比较就需要一个函数strcmp。

int cmp_stu_by_name(const void* e1, const void* e2)
    {
        return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
    }
    void test1()
    {
        struct Stu s1[3] = { {"zhangsan",22},{"lishi",11},{"wanger",33} };
        int sz = sizeof(s1) / sizeof(s1[0]);
        //qsort(s1, sz, sizeof(s1[0]), cmp_stu_by_age);
        qsort(s1, sz, sizeof(s1[0]), cmp_stu_by_name);
    }

运行结果：

![040de9658f7375be40dc89d7049d50b4.png][]

## 3.自主实现sqort ##

struct Stu
    {
        char name[20];
        int age;
    };
    int cmp_stu_by_age(const void* e1, const void* e2)
    {
        return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
    }
    int cmp_stu_by_name(const void* e1, const void* e2)
    {
        return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
    }
    void swap(char* buf1, char* buf2, size_t width)
    {
        size_t i = 0;
        while (i < width)
        {
            char tmp = *buf1;
            *buf1 = *buf2;
            *buf2 = tmp;
            buf1++;
            buf2++;
            i++;
        }
    }
    void bubble_sort(void* base, size_t sz, size_t width, int(*cmp)(const void* e1, const void* e2))
    {
        size_t i = 0;
        for (i = 0; i < sz - 1; i++)
        {
            size_t 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);
            }
        }
    }
    void test1()
    {
        struct Stu s1[3] = { {"zhangsan",22},{"lishi",11},{"wangeeeeeer",33} };
        int sz = sizeof(s1) / sizeof(s1[0]);
        bubble_sort(s1, sz, sizeof(s1[0]), cmp_stu_by_age);
        //bubble_sort(s1, sz, sizeof(s1[0]), cmp_stu_by_name);
    }
    int main()
    {
        test1();
        return 0;
    }

运行结果：

![f4c06ccaf636092ad307d07de8df30f2.png][]

![318955c7d8a3849aea2563b93af57904.png][]

[cca36a37d00f371505312acf598a2135.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c90f219a340d493c8b70b12996bb32be.png
[872aa6ef27c4ec93b72fe080e660b256.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/46c35b143896476da096f3027d351e42.png
[75b081ae136d7ea26055e9f6af1aaba4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6f8e262433b445a2866a6bdd6347dc2c.png
[040de9658f7375be40dc89d7049d50b4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fed8ffebd521422b8cfb3255f46f6d44.png
[f4c06ccaf636092ad307d07de8df30f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/37fd9757a8f342c88de4abb2e5015cbe.png
[318955c7d8a3849aea2563b93af57904.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/707d5a53f65847e992b986a4afd8e926.png