模拟实现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函数
- 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指向数组中的两个元素
);
- 。为啥是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定义中是一个函数指针，我们现在这里直接定义一个函数并把该函数的地址传入即可，如上代码- ，那么此时的结果无非就三种情况
- 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;
}
- 没啥问题
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这个元素来比较大小
- 通过名字比较大小排序
- 其他与上面一致，这次我们通过名字来比较大小并排序
- 代码如下：
/测试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;
}
- 结果如下
- 这里我们简单介绍一下字符串比较大小的规则
字符串比较大小规则
- 对于两个字符串比较大小，其实就是比较对应位置字符ASCLL码值的大小，如果相同位置的ASCLL值相同，就比较下一个位置，直到出现不同为止。
比如上面这段代码的比较，在首元素上分别是'l','w','z'，其中‘l’ASCLL码值最小，排在首位，'w'ASCLL码值居中，'z'ASCLL码值最大，排在最后，这就是出现上面结果的原因。
总结
-
今天的内容到这里就结束了，其中我们介绍了模拟qsort函数的实现，不妨自己动手使用一下，只有自己动手才能真正的理解并且学会哦！
-
好了，如果你有任何疑问欢迎在评论区或者私信我提出，大家下次再见啦！