【C语言】轻松模拟实现qsort函数-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C语言】轻松模拟实现qsort函数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【C语言】轻松模拟实现qsort函数,0基础C语言,c语言,学习,c++,算法,开发语言

君兮_的个人主页

勤时当勉励岁月不待人

C/C++ 游戏开发

Hello,米娜桑们，这里是君兮_，我们今天接着上回更新的内容，讲讲我们如何模拟实现自己的qsort函数， 废话不多说，我们开始今天的内容。

qsort函数的使用方法及细节

关于这方面的内容已经在上篇博客中具体介绍了，这里不再缀叙，感兴趣的话可以跳转以下博客链接：
带你玩转库函数qsort

模拟实现qsort函数

好了，我们知晓了qsort函数，那我们应该怎么模拟实现呢？

之前我们讲过，qsort函数与冒泡排序及其相似，两者不同的地方在于qsort函数除了能过排序整形数据还能排序其他类型的数据，由这个思路我们可以先写出以下的代码：

void bubble_sort(void* base, int num, int size, int (*cmp)(const void*, const void*))
{
    int i = 0;
    for (i = 0;i < num - 1; i++)
    {
        int j = 0;
        for (j = 0; j < num - 1 - i; j++)
        {
            if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
            {
                swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
            }
        }
    }
}

上面的代码与冒泡排序类似，我想大家有疑问的就是这一部分了

if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
            {
                swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
            }

那么这一块到底是什么意思呢？我们来逐步分析一下。
1.首先，需要说明的是，这个swap函数是由我们自己定义的，它的目的就是为了实现两个数据一个字节一个字节的交换。

swap函数

1.1
该函数所需传入的三个参数分别为数组中某个数据，下一个数据，以及该类型数据所占字节的大小size。比如传入一个int类型的数据，当j=0时传入的数据分别就是首元素，第二个元素，以及int类型数据所占字节的大小4
1.2
我们从base传入类型它是一个void数据，也就是空类型，那么如果想使用它就得把它强制转换成你想要的类型，这里的char也可以是int，double等等。
1.3
这里char*的主要原因在于，一个char型数据的大小是一个字节，也就是最通用的，我们qsort函数的目的是实现各种数据的排序，比如这里如果有一个结构体占20个字节，而你却在这里使用double，一个数据就占8个字节，那么你要怎样通过跳过字节的方式指向下一个元素呢？所以char最合适
1.4
我们想通过j遍历这个数组中的每一个元素再比较大小来实现排序的问题，但是每种数据类型所占字节大小又不同，我们该如何做呢？
这时，我们想到了，既然char是最小的只占一个字节，当我们想模拟某种数据+1时，只需要把char类型数据跳过对应模拟数据的size个字节不就行啦？而我们又可以通过 j 的循环来实现遍历每个数据，也就有下面这段代码

(char*)base + j * size
(char*)base + (j+1) * size//跳过对于size个字节的数据指向所需排序类型的下一个元素

有了上面的解释，我想大家应该明白swap的目的以及各种参数设置的原因了，下面我们来实现一下：

//交换函数
void swap(char* p1, char* p2, int size)
{
    int i = 0;
    char* tmp = 0;
    for (i = 0; i < size; i++)
    {
        tmp = *p1;//由于不是交换地址而是交换存放的内容因此需要解引用
        *p1 = *p2;
        *p2 = tmp;
        p1++;
        p2++;
    }
}

一个字节一个字节的进行交换，当交换完这次的就跳到下一个字节继续交换，直到把该种数据所占字节全部交换完毕

2.讲完了上面的swap函数，我们再来讲讲上面的判断条件

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

通过swap中传入参数的解释，这段代码就非常好理解了，这其实就是比较前一个数据和后一个数据的大小，也就是我们实现排序升降序排列的地方，我们在之前的qsort函数中讲过

void qsort(void* base, //指向了需要排序的数组的第一个元素
          size_t num, //排序的元素个数
          size_t size,//一个元素的大小，单位是字节
           int (*cmp)(const void*, const void*)//函数指针类型 - 这个函数指针指向的函数，能够比较base指向数组中的两个元素
          );

对于开发来说，我们只需要设计一个能够进行排序各种类型数据的程序，我们并不知道用户到底需要排序哪种数据，所以，对于qsort函数来说，最后一个传入的函数指针是需要用户自己来编写用来告诉我们的代码它到底需要排序哪种数据的
而我们这里的cmp函数，就是上面定义中的这个函数指针，它的返回类型是int 。为啥是int？我们结合具体的例子来讲。
到这里，我们的模拟qsort实现基本就完成了，下面来通过例子告诉大家具体使用方法

模拟qsort函数实战

逻辑上我们的qsort函数是行得通的，下面我们来通过实际的例子来试试

1.整型数据使用模拟qsort排序

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

结果
很好的实现了我们的要求
我们现在具体来聊聊函数指针

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

上面qsort定义中是一个函数指针，我们现在这里直接定义一个函数并把该函数的地址传入即可，如上代码
它把传入的两个void型指针强制转换为int型，并通过解引用让两个指针指向的数据相减然后返回结果 ，那么此时的结果无非就三种情况
p1>p2,返回一个大于0的数
p1=p2，返回0
p1<p2，返回一个小于0的数
这个函数通过返回值的正负来判断是否需要交换
返回一个大于0的数，说明前一个元素大于后一个元素，就交换两者的位置
返回一个小于或等于0的数，不发生变化
注意：这里的p1指向前一个数，而p2指向后一个数，这样通过不断比较交换就可以实现我们的升序排序了
同时，这里也就解释了我们这个函数指针为啥返回值是int型了

那如果我们想实现降序，是不是只需要将p1-p2改成p2-p1就行了？
返回一个大于0的数，说明后一个元素大于前一个元素，就交换两者的位置
返回一个小于或等于0的数，不发生变化

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

【C语言】轻松模拟实现qsort函数,0基础C语言,c语言,学习,c++,算法,开发语言

没啥问题

2.自定义结构体使用qsort排序

其他数据类型与整型如出一辙，我们现在就来讲讲结构体数据怎样通过qsort实现排序
注意，如果结构体中有多个类型的数据，由于我们模拟qsort排序的是数组中的数据，使用时传入的数据必须是相同类型的
也就是说，对于结构体的排序，你必须确定使用结构体中的哪个元素来进行比较排序，而不是一起排序。
代码如下：
首先介绍的是通过结构体中的年龄来排序

//测试qsort排序结构体数据
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 test2()
{
    struct Stu arr[] = { {"zhangsan", 20}, {"lisi", 50},{"wangwu", 15} };
    int sz = sizeof(arr) / sizeof(arr[0]);
    int i = 0;
    bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_by_age);
    for (i = 0; i < sz; i++)
    {
        printf("%s %d ", arr[i].name, arr[i].age);
    }
}
int main()
{
    test2();
    return 0;
}

我们首先定义了一个结构体，里面有两个元素分别为名字和年龄
然后我们定义了一个结构体数组，并初始化了三个元素进去

struct Stu arr[] = { {"zhangsan", 20}, {"lisi", 50},{"wangwu", 15} };

之后我们依然计算了该数组的大小，并通过计算首元素的大小计算出数组中每个元素所占的字节
最后，我们可以看出，这时是在通过结构体里的第二个元素也就是年龄的大小进行排序

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

这里我们通过把p1，p2转换成结构体指针的类型并且通过"->"操作符指向了结构体中age这个元素来比较大小
【C语言】轻松模拟实现qsort函数,0基础C语言,c语言,学习,c++,算法,开发语言

通过名字比较大小排序
其他与上面一致，这次我们通过名字来比较大小并排序
代码如下：

/测试qsort排序结构体数据
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 test3()
{
    struct Stu arr[] = { {"zhangsan", 20}, {"lisi", 50},{"wangwu", 15} };
    int sz = sizeof(arr) / sizeof(arr[0]);
    int i = 0;
    bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);
    for (i = 0; i < sz; i++)
    {
        printf("%s %d ", arr[i].name, arr[i].age);
    }
}
int main()
{
    test3();
    return 0;
}

结果如下

【C语言】轻松模拟实现qsort函数,0基础C语言,c语言,学习,c++,算法,开发语言

这里我们简单介绍一下字符串比较大小的规则

字符串比较大小规则

对于两个字符串比较大小，其实就是比较对应位置字符ASCLL码值的大小，如果相同位置的ASCLL值相同，就比较下一个位置，直到出现不同为止。
比如上面这段代码的比较，在首元素上分别是'l','w','z'，其中‘l’ASCLL码值最小，排在首位，'w'ASCLL码值居中，'z'ASCLL码值最大，排在最后，这就是出现上面结果的原因。