您现在的位置是:首页 >其他 >模拟实现qsort函数(采用冒泡排序的方式)网站首页其他
模拟实现qsort函数(采用冒泡排序的方式)
前言:
之前我在C语言:指针详解【进阶】后篇中提到了
qsort函数
,qsort函数
作为一个库函数,在我们日常的代码编写中可能会用到,在上面提到的文章中我们也进行使用了这个函数,大家也了解了一些这个函数的使用方法,但我们作为学习者,我们不仅要会用,还要知道这个qsort函数
的原理,更要自己能够模拟实现一个qsort函数
来,这样才能对这个函数有更深刻的理解。
这里我们再次回顾一下qsort函数
的用法,我们不清楚的可以打开cplusplus.com的网站搜索一下qsort函数
进行查看
引文原版:
中文网页翻译:(尽量看原版更准确哦)
从引文来看,qsort函数
是一个可以排列任意类型数据的函数。
我们先从这个函数的参数来看:
这个函数一共有四个参数,一个
void*
类型的指针,两个size_t
类型的整型,一个返回类型为int
、函数参数为两个void*
类型的指针的函数指针。
这代表着在使用qsort函数
时,我们需要知道要排序的第一个元素的地址,要排序元素的个数,每个元素的大小,以及一个能比较两个元素的大小的函数。
注:
size_t 是无符号整型
这里我们先简单使用一下这个函数:(记得引用头文件)
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const int* p1, const int* p2)
{
return *p1 - *p2;
}
int main()
{
int arr[10] = { 7,6,1,2,8,9,3,5,0,4 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(int), cmp_int);
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
这个排序的原理可以类比一下一个简单的排序方法:冒泡排序。它与冒泡排序的底层排序思想可以看作是大致相似的。
这里简单实现一下冒泡排序:
#include <stdio.h>
void bubble_sort(int arr[], int sz)
{
for (int i = 0; i < sz; i++)
{
int flag = 1;
for (int j = 0; j < sz - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = 0;
}
}
//当flag等于1时,说明这一趟排序未发生交换,说明顺序已经排好了
if (flag)
break;
}
}
int main()
{
int arr[10] = { 7,6,1,2,8,9,3,5,0,4 };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz);
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
注:
由于qsort函数
的真正底层排序思想是:快速排序的方法,这里我就先用冒泡排序来模拟实现一下这个函数,后面有机会,我也会把快速排序的模拟实现讲解出来的。
实现思路:
对于qsort函数
的模拟实现来说,最难的部分是如何实现任意类型数据的排序,我们之前对于确定的数据进行排序时,往往可以用对应的方法进行比较两元素并进行交换来排序,但qsort函数
在使用时,设计这个函数的人在编写这个函数时并不确定这个函数将来要排列什么类型的数据,所以他在设计函数参数时不能限定函数传参传过来的数据类型,所以要把第一个函数参数设计成一个void*
类型的指针。
现在函数已经把要排序的第一个元素的地址传过来了,那接下来还要传要排序的元素个数,来确定排序的次数。
同时,由于第一个参数是void*
类型的,我们还要确定要排序元素的字节数,所以还要传每个元素的大小。
最后,由于不同类型的元素的比较形式不同,我们需要用不同的方法来比较传过来的数据,但是函数设计并不能预见所有的排序情况,这就需要使用者在使用qsort函数
时,自己编写一个能比较两个要传元素的大小的函数,再把这个函数的地址穿过来就行了。
看到这里,我们大致清楚了qsort函数
的设计思路,这里我们就简单的编写一个my_qsort函数
来模拟实现一下这个函数吧。
这里我们对函数内容编写时要注意,我们传过来的元素数据时各种各样的,但我们的函数参数的接受时是void*
的参数,我们如何知道我们访问几个字节就找到我们要排序的一个元素呢?
这时就需要使用到我们的第三个参数了,第三个参数接收的就是我们要排序的一个元素的大小(字节),我们只需要一次访问size
个字节的数据就可以找到每个要排序的元素了,这时需要将base
强制类型转换成char*
类型的指针再乘以size
就是完整的一个要排序的元素数据了。
现在我们需要进行相邻两个元素的比较,这里的比较就是使用者要传过来的函数指针,这里的比较函数要使用者自己编写。
注意:设计的比较函数要和库里给定的该比较函数模板格式要一致。
同时,相邻元素比较完后,如果不符合顺序就需要交换相邻两元素了,这里我们再设计一个my_swap函数
来进行交换:
对于要交换任意类型的数据,数据指针的接受也要设计成void*
类型的,同时要传递数据的字节大小来找到整个数据,然后在函数内部用一层for循环
来交换每个字节的数据就可以了。
代码实现:
void my_swap(void* p1, void* p2, size_t size)
{
size_t i = 0;
for (i = 0; i < size; i++)
{
char tmp = *((char*)p1 + i);
*((char*)p1 + i) = *((char*)p2 + i);
*((char*)p2 + i) = tmp;
}
}
这样我们的my_qsort函数
就设计完成了。
代码实现:
void my_swap(void* p1, void* p2, size_t size)
{
size_t i = 0;
for (i = 0; i < size; i++)
{
char tmp = *((char*)p1 + i);
*((char*)p1 + i) = *((char*)p2 + i);
*((char*)p2 + i) = tmp;
}
}
void my_qsort(void* base, size_t num, size_t size, int (*cmp)(const void*, const void*))
{
size_t i = 0;
size_t j = 0;
for (i = 0; i < num - 1; i++)
{
for (j = 0; j < num - i - 1; j++)
{
if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
{
my_swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
}
}
}
}
这里就举两个示例来感受一下:
示例一:(排列整型数据)
#include <stdio.h>
int cmp_int(const int* p1, const int* p2)//比较函数
{
return *p1 - *p2;
}
void my_swap(void* p1, void* p2, size_t size)
{
size_t i = 0;
for (i = 0; i < size; i++)
{
char tmp = *((char*)p1 + i);
*((char*)p1 + i) = *((char*)p2 + i);
*((char*)p2 + i) = tmp;
}
}
void my_qsort(void* base, size_t num, size_t size, int (*cmp)(const void*, const void*))
{
size_t i = 0;
size_t j = 0;
for (i = 0; i < num - 1; i++)
{
for (j = 0; j < num - i - 1; j++)
{
if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
{
my_swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
}
}
}
}
int main()
{
int arr[10] = { 7,6,1,2,8,9,3,5,0,4 };
int sz = sizeof(arr) / sizeof(arr[0]);
my_qsort(arr, sz, sizeof(int), cmp_int);
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
示例二:(排序字符数据)
#include <stdio.h>
#include <string.h>
int cmp_char(const char* p1, const char* p2)
{
return strcmp(p1, p2);
}
void my_swap(void* p1, void* p2, size_t size)
{
size_t i = 0;
for (i = 0; i < size; i++)
{
char tmp = *((char*)p1 + i);
*((char*)p1 + i) = *((char*)p2 + i);
*((char*)p2 + i) = tmp;
}
}
void my_qsort(void* base, size_t num, size_t size, int (*cmp)(const void*, const void*))
{
size_t i = 0;
size_t j = 0;
for (i = 0; i < num - 1; i++)
{
for (j = 0; j < num - i - 1; j++)
{
if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
{
my_swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
}
}
}
}
int main()
{
char arr[10] = {'c', 'f', 'w', 'a', 'd', 'k', 'o', 'z', 'e', 'n'};
int sz = sizeof(arr) / sizeof(arr[0]);
my_qsort(arr, sz, sizeof(char), cmp_char);
for (int i = 0; i < sz; i++)
{
printf("%c ", arr[i]);
}
return 0;
}
写到这里本篇关于 qsort函数的模拟实现(冒泡排序) 的文章就到此结束了,对于这个函数的模拟实现,下来还是要多加练习才能更好的掌握。
下一篇我就正式进入对字符串的研究进行深入了解,并讲解一系列关键的字符串函数和内存函数,和它们的模拟实现。
感兴趣的的小伙伴点点赞,点点关注,谢谢大家的阅读哦!!!
精彩不容错过,点点关注,后期不错过哦!?
你们的鼓励就是我的动力,欢迎下次继续阅读!!!???