了解qsort,以及模拟实现
- 🎑情境引入
- 🎈qsort
- 📖qsort的头文件
- 📄开场
- 🔑qsort的参数
- 🤔为什么可以对任意类型排序呢?
- 📜参数
- 参数①
- 参数②
- 参数③
- 最难的参数④
- 🎃qsort应用实例
- 🌳比较整形/浮点型
- 🌴比较结构体的整形
- 🌵比较结构体的字符串
- 💡想成为一名优秀的程序猿,需要加点难度---- 模拟实现
- 🎈冒泡排序模拟实现
- ✏普通版本的冒泡排序
- 📄重点来了
- 🎉先对比较进行转换
- 🎐该决解的问题已经解决,那开始实现----比较
- 🎉最后一步交换的实现
- 🩸问题解决开始实现----交换
- 🛠冒泡排序模拟实现qsort完整代码
- 🎈插入排序实现qsort
- 🎠原版插入排序
- ✨关键处分析
- 结束语
🎑情境引入
struct student
{char name[10];int age;
};
你是否有过这样的经历,在对结构体成员进行排序,需要写几个排序,而感到不耐烦呢。
就比如对上面的结构体数组排序,既要对成员name排序,又要对成员age排序。
看了这篇博客,你就可以告别大段落式的排序啦。
qsort表示它很强,它来拯救你了~~❤
qsort强在哪呢?
强在它可以对任意类型的排序(存储结构需要限定–顺序存储)
也就是说qsort只能对顺序存储的结构进行排序。
顺序存储结构有:1.数组,2.在堆区开辟一段连续的空间
🎈qsort
📖qsort的头文件
#include<stdlib.h>
📄开场
qsort底层原理是快排,但在这篇博客中不讲快排,而是讲冒泡排序,以及插入排序去模拟qsort的功能。
为啥还要讲插入排序呢,如果你想对单链表进行排序的话,qsort是不能达到目的的,对于单链表的排序,需要用插入排序的思想进行排序。
通过插入排序模拟qsort,再对存储复杂数据的单链表排序的时候,会轻松很多。
🔑qsort的参数
size_t 是 unsigned int 重命名后的类型名
🤔为什么可以对任意类型排序呢?
主要是在设置函数参数的时候,使用的是void*。
void* 有个特点,叫“有容乃大”。
void* 可以接收任意类型的指针
同样的任意类型的指针也可以接收void*
在void* 修饰的变量接收任意类型的指针的情况下,该变量是不能进行任何操作的。
因为对指针进行操作是看指针的类型,该变量的类型是void* 。
因为void类型大小是不确定的(vs下0,linux下1)。
那么对该变量进行*或者加减整数操作是没有意义的
指针类型的意义不记得的点这
那如何解决呢?只需要通过强制类型转换即可。
📜参数
参数①
对于参数①
void* base
通过void* 就能够推测一些东西了。void*是指针,是用来接收地址的。
那么在调用qsort的时候,第一个实参一定是个地址。这样理解是没错的,也确实如此。
实参传①就是你想要排序数组的起始地址(或者在堆区开辟空间的起始地址)
参数②
对于参数②
size_t num
,表示你需要排序的数组有多少个元素个数
参数③
对于参数③
size_t size
,表示待排序数组元素的大小(单位是字节)
为什么需要传元素的大小呢?也很好理解,我们需要对不同类型的元素进行排序,不同的类型,所占空间的大小是不同的,如果不传元素的大小,qsort又怎么能对不同类型元素进行排序呢?所以必须传。
最难的参数④
参数④
int (*compar)(const void*, const void*))
这也是我们能够比较任意类型的关键!
有人看到这个参数感觉头皮发麻,不知道这是啥。先来分析一下。
我们先把中间部分换个形式int fun (const void*, const void*))
这是啥?这是一个函数!
函数名是fun
形参为(const void*, const void*)
返回类型为int
在回过头来分析int (*compar)(const void*, const void*))
,那这是什么?这是指针,因为操作符*,并且与()优先结合,所以是指针。
再结合上面所说,这个指针指向的是一个函数。
有人可能难以理解指向的是函数,那我再说说,请问函数有地址吗?答案是有的。
在多说几嘴,函数名也是可以直接表示函数的地址,也可以不用&。
已经知道函数是有地址的了,那指针去指向一个函数,也就没什么问题的了。看下面这段话,再去理解一番。
看这个表达式
int* p
。
p指向谁?如果你不知道怎么看的话,把指针名p和*去掉,剩下的就是指针指向某个变量的类型。也就是说p将来指向的是一个int类型的变量(不考虑强制类型转换)
那么再回过头来看
int (*compar)(const void*, const void*))
,把指针名compar
和*
去了,剩下的是int (const void*, const void*))
这是一个函数。按照上面的理解,该指针在将来是指向一个函数的,那么现在应该能理解指针为啥指向函数了吧
综上所述,参数④是一个函数指针,该指针指向了一个函数,该函数的形参为
(const void*, const void*)
,该函数的返回类型为int
。
接着分析,既然知道了参数④是一个函数指针,是指针,那么传参的时候肯定是需要传地址,传谁的地址?传函数的地址!
换句话说,如果我们想要使用qsort函数,那么我们需要一个形参一致,返回类型一致的函数,这个函数是需要使用qsort的人自己去实现的。因为只有使用qsort的人才知道自己想要比较什么,比较元素的类型又是什么。
那这个函数的返回值又有什么含义呢。
比较的两个元素分别e1,e2。
如果e1大于e2,返回一个大于0的数
如果e1小于e2,返回一个小于0的数
如果e1等于e2,返回0
那使用qsort的人去实现的这个函数作用是什么?是比较方法,不同的类型比较的方式是不同的!如果是数与数之间的比较,做差即可。如果是字符之间的比较呢?做差就不适合了,需要使用
strcmp
。
讲了这么多,相信你应该有所了解,或许还不太理解,也没关系,通过下面的实例来理解上面我所说的!
🎃qsort应用实例
主函数
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct S //定义一个结构体类型
{char name[10];int age;
};
int main()
{test1();test2();return 0;
}
🌳比较整形/浮点型
数与数之间的比较做差即可。
返回值也就是这个差值。
写的时候注意要强制类型转换,转换成什么类型的指针取决于你想要比较的元素类型,比较的是int类型就int*,比较的是float类型就float*
int int_cmp(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;//e1-e2排的是升序//降序的话,需要将e1,e2换个位置
}
void test1()
{int arr[10] = { 5, 2, 1, 3, 4, 6, 9, 8, 7, 10 };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), int_cmp);//arr是数组的地址,sz是数组元素的个数//sizeof(arr[0]),元素所占空间的大小//int_cmp,是函数的地址,该函数是使用qsort的人去实现int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}
🌴比较结构体的整形
在对结构体排序的时候,需要注意的是 ()
(struct S*)e1->age
这样写是不行的,需要将(struct S*)e1
当作一个整体去使用,需要加上 ()
写成((struct S*)e1)->age
int age_cmp(const void* e1, const void* e2)
{return ((struct S*)e1)->age - ((struct S*)e2)->age;
}
void test2()
{struct S s[] = { {"Zhang",40},{"Wang",20},{"Lisi",60} };//对结构体初始化int sz = sizeof(s) / sizeof(s[0]);//求数组的元素个数qsort(s, sz, sizeof(s[0]), age_cmp);//sizeof(s[0]),一个元素的大小//age_cmp,函数的地址。int i = 0;for (i = 0; i < sz; i++){printf("%s %d\n", s[i].name, s[i].age);}
}
🌵比较结构体的字符串
对一些字符串函数不了解的点这
这里还是要强调一下,注意 ()
strcmp()本身也是有个括号的。
strcmp的返回值:大于返回一个大于0的数,小于返回小于0的数,等于返回0。
写的时候可以先从里面的写起
先把(struct S*)e1)->name, ((struct S*)e2)->name
写出来,然后在复制粘贴到strcmp()
的()里。
int name_cmp(const void* e1, const void* e2)
{return strcmp(((struct S*)e1)->name, ((struct S*)e2)->name);
}
void test2()
{struct S s[] = { {"Zhang",40},{"Wang",20},{"Lisi",60} };int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), name_cmp);int i = 0;for (i = 0; i < sz; i++){printf("%s %d\n", s[i].name, s[i].age);}
}
💡想成为一名优秀的程序猿,需要加点难度---- 模拟实现
🎈冒泡排序模拟实现
冒泡排序比较简单,这里就不再赘述如何来的了。
通过与普通版本的冒泡排序,对比去实现qsort的功能
✏普通版本的冒泡排序
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;}}}
}
模拟实现的函数可以对着qsort的去写
这个比较容易void Bubble_sort2(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
📄重点来了
冒泡排序中最主要的两个步骤是 比较 + 交换。
if (arr[j] > arr[j + 1])//比较{//交换int tmp = arr[j];arr[j] = arr[j + 1]; arr[j + 1] = tmp; }
🎉先对比较进行转换
友情提示,需要对指针类型的意义要有所了解才能理解
不了解的点击"我"
base
的类型是void*
上面有铺垫过,void*
不可直接使用,需要通过强制类型转换。那转换成什么呢?转换成int*
合适吗?
显然不合适,这样写,那我们如何实现比较任意类型的呢?
回归本源,内存的基本单位是字节,不管是哪种类型的元素,元素所占空间的大小肯定是可以确定的。
那我们可以这样:以字节为单位去偏移,虽然每一次偏移的步长只有1个字节,但只要我们知道了,一个元素所占空间的大小有n个字节。
那从当前位置向后偏移n次,不就是n个字节嘛?不就能够在内存中取到一个元素的吗?
这样一理,
base
需要强制类型转换为char*
,那类型的大小如何得知呢?不正是我们的参数③–>size_t size吗
或许你还没理解,用图带你理解一下。
那现在还有一个问题那如何取到每一个元素呢?
数组与指针访问是互通的(操作符之间可以互用),不了解点"我"
原先的是这样写的
if (arr[j] > arr[j + 1])
(指针类型是int*
)我们是不是可以借鉴一下呢?
arr[j]
等价于*(arr+j)
arr+j
的含义是以arr
为起始地址+j
向后偏移j*4
个字节和我们写的(char*)base+size
(含义是以base
为起始地址向后偏移size
个字节)
相比,不就少了什么不就少了j*
吗,那我们这样写(char*)base+size*j
和上面arr+j
所表达的意思不就一样了吗?
还有一种理解,我们已经知道
(char*)base+size
表示的是第一个元素(是以base为起始地址的第一个元素)那第二个元素不就是(char*)base+size + (char*)base+size
,第三个元素是(char*)base+size + (char*)base+size + (char*)base+size
,那第j个元素不就是(char*)base+size * j
吗?
怎么理解方便就怎么选择。
元素每一个元素能够取出来了,那该如何比较呢?
轮到我们所写的比较函数出场了。比较方法的函数已经有了,我们只需要传参即可。这样调用的函数又被称为回调函数
哪种调用呢? 以指针的形式去调用函数,这个函数就被称为回调函数
这里的指针可以不用解引用,直接当作函数来使用。
为什么可以这样呢?还记得上面有说过,函数名就表示函数的地址, 这个地址不就是指针吗?那这个指针不就是函数名吗?函数调用是函数名(参数),这样一换不就是 指针(参数) 吗
🎐该决解的问题已经解决,那开始实现----比较
if ( cmp((char*)base + j * width, (char*)base + (j + 1) * width) )
我这样写对吗?答案是不对,还少了点东西。我们这个函数返回值是一个整数,并不是 大于,小于,等于! 要加上判断
if ( cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0 )
或许有人会有疑问,为什么在对比较函数中,传参只需要传地址,就可以比较两个元素的大小。
这是指针类型的作用,指针的类型决定了解引用(*)能够操作多大的空间。
比较函数是使用者实现的,对应的元素类型也是明确的,在接收地址后,根据强制类型转换后的类型,进行解引用操作,可以取到对应的元素内容,那也就能完成比较。
🎉最后一步交换的实现
交换步骤先来看原冒泡的实现
//交换int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;
按照上面已经有的经验,想要实现对任意类型元素的交换,我们仍然只能通过强制类型转换为
char*
以字节为单位去实现。
如果你曾经有模拟实现过strcpy的话,那现在这个问题对你来说很容易就能完成的。
没有模拟过的话,且听我分析。
交换是两个元素互换,交换实现的步骤是以字节为单位,一个字节一个字节的交换,循环的条件应该是很容易想到的,什么时候交换完成了呢?当一个元素中最后一个字节交换后就完成了一次交换。
这里有一堆的字符串函数等着你来模拟实现,其中有两个是挺有难度的噢,快点“我”~
整个想法有了,也可以开始实现了。如果我们把这一“动作”封装成函数是不是更显得"高大上"呢?也确实可以这样实现,而且也美观。
函数名为Swap
形参和返回类型是什么呢?
返回类型容易考虑我们不需要返回类型。
那形参是啥?比较的是两个元素,这两个肯定需要传过去。
再加上我们是以字节为单位进行交换的,那结束的条件也需要传,结束条件就是我们元素的大小。
讲到这那已经可以开始实现了。
🩸问题解决开始实现----交换
//函数调用(交换两个元素,以及元素的大小)
Swap( (char*)base + j * width ,(char*)base + (j + 1) * width ,width );//函数实现,选择哪种循环都行。
void Swap(char* e1,char* e2, int width)
{int i = 0;for(i=0;i<width;i++){char tmp = *e2;*e2 = *e1;*e1 = tmp;e1++;e2++;}
}
🛠冒泡排序模拟实现qsort完整代码
void Swap(char* e1, char* e2, int width)
{int i = 0;for (i = 0; i < width; i++){char tmp = *e2;*e2 = *e1;*e1 = tmp;e1++;e2++;}
}
void Bubble_sort2(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
{int i = 0;for (i = 0; i < sz - 1; i++){int 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);}}}
}
同样可以来测试一下
int int_cmp(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}
void test1()
{int arr[] = { 2,5,3,1,9,6,4,8,7,10 };int sz = sizeof(arr) / sizeof(arr[0]);Bubble_sort2(arr, sz, sizeof(arr[0]), int_cmp);print(arr, sz);
}struct S
{char name[10];int age;
};
int struct_name_cmp(const void* e1, const void* e2)
{return strcmp(((struct S*)e1)->name, ((struct S*)e2)->name);
}int struct_age_cmp(const void* e1, const void* e2)
{return ((struct S*)e1)->age - ((struct S*)e2)->age;
}
void test2()
{struct S s[] = { {"Zhang",40},{"Li",20},{"Wang",50} };int sz = sizeof(s) / sizeof(s[0]);//Bubble_sort2(s, sz, sizeof(s[0]), struct_name_cmp);Bubble_sort2(s, sz, sizeof(s[0]), struct_age_cmp);int i = 0;for (i = 0; i < sz; i++){printf("%s %d\n", s[i].name, s[i].age);}
}
int main()
{//test1();test2();return 0;
}
对结构体年龄排序
对结构体姓名排序
对数组排序
🎈插入排序实现qsort
🎠原版插入排序
void Insert(int* arr, int sz)
{int i = 1;for (i = 1; i < sz; i++){int t = arr[i];//待插入的元素int j = i - 1;while (j >= 0 && t < arr[j]){//交换arr[j + 1] = arr[j];j--;}arr[j + 1] = t;}
}
int main()
{int arr[10] = { 5,2,3,8,9,4,7,1,10,6 };int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;Insert(arr, sz);for (i = 0; i < 10; i++){printf("%d ", arr[i]);}return 0;
}
✨关键处分析
插入排序需要注意的是这两个表达式
int t = arr[i];
和arr[j + 1] = t;
为了达到实现任意类型的排序,肯定不能这样写。
那我是这样处理的:
为了存储插入的元素,你需要空间,需要多大根据元素的类型的大小。
我首先想到的是用动态内存函数,通过malloc
开辟空间来存储要插入的元素。地址的类型需要设置为char*
另外如何实现赋值这一过程呢?
如果写过strcpy
的模拟实现那应该也能够想到,我们可以通过Copy
函数进行拷贝,就相对于完成了一次赋值。
一些函数的模拟实现写一遍,自己有更深的理解,很容易能想到,多去模拟实现这些函数也能提升自己代码能力。
点"我“,即可找到那些模拟的字符串函数
void Swap(char* e1, char* e2, int width)
{int i = 0;for (i = 0; i < width; i++){char tmp = *e2;*e2 = *e1;*e1 = tmp;e1++;e2++;}
}
void Copy(char* e1, const char* e2, int width)
{while (width){*e1 = *e2;e1++;e2++;width--;}
}void Insert2(void* base, int num, int size, int(*cmp)(const void* e1, const void* e2))
{int i = 1;char* t = (char*)malloc(size);if(NULL==t)//检测开辟是否成功{perror("malloc");return;}for (i = 1; i < num; i++){//拷贝赋值Copy(t, (char*)base + size * i, size);int j = i - 1;//比较while (j >= 0 && cmp(t, (char*)base + size * j) < 0){//交换Swap((char*)base + size * (j + 1), (char*)base + size * j, size);j--;}//拷贝赋值Copy((char*)base + size * (j + 1), t, size);}//对堆区开辟的空间释放free(t);//指针置为空,避免野指针t=NULL}
测试
int struct_name_cmp(const void* e1, const void* e2)
{return strcmp(((struct S*)e1)->name, ((struct S*)e2)->name);
}int struct_age_cmp(const void* e1, const void* e2)
{return ((struct S*)e1)->age - ((struct S*)e2)->age;
}int cmp_int(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}
void test2()
{struct S s[] = { {"Zhang",40},{"Li",20},{"Wang",50} };int sz = sizeof(s) / sizeof(s[0]);Insert2(s, sz, sizeof(s[0]), struct_name_cmp);Insert2(s, sz, sizeof(s[0]), struct_age_cmp);int i = 0;for (i = 0; i < sz; i++){printf("%s %d\n", s[i].name, s[i].age);}
}void test1()
{int arr[10] = { 5,2,3,8,9,4,7,1,10,6 };int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;Insert2(arr,sz,sizeof(int),cmp_int);for (i = 0; i < 10; i++){printf("%d ", arr[i]);}
}
int main()
{//test1();test2();return 0;
}
结束语
看完之后,还等什么呢,快点自己模拟实现一下属于你的qsort吧~