目录
一. 冒泡排序
(1)什么是冒泡排序
(2)代码实现
(3)局限
二.qsort函数排序
注意事项:
(2)在实现我们的compare函数时函数的参数必须和库里qsort函数的参数的类型一致.
(3)记得将需要比较的数据将void类型转换类型.
三 模拟实现qsort
(1)void jiaosqort(void* target,int sz, int width,int (*compare)(void* e1,void* e2));
(2)void swap(char* e1,char* e2,int width);
一. 冒泡排序
在我们对一组数据进行排序处理的话,我们有很多的排序的方法,其中冒泡排序是最基础的排序的算法,下面我来向大家介绍这种排序算法.
(1)什么是冒泡排序
冒泡排序就是将两个相邻的数据进行比较排序.
下面我将列举一个列子:
看这串数据,我们用冒泡的思想模拟冒泡排序的逻辑,进行两两排序,
先将9-0进行比较 9>0 那么9 就和 0交换位置
然后比较交换过的9 和 1 结果也是将9 和 0的位置交换
通过这样循环的操作我们就将这一串数据中的最大的元素排到了最后的位置---这称为一趟冒泡排序.
每一次冒泡排序将剩下数据的最大值排到了末尾,所以在冒泡排序结束我们就实现了数据排序.
假设总共有n个数据那么需要几趟冒泡排序呢,答案很简单就是n-1.
下面是代码实现:
(2)代码实现
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> int main() { int a[] = { 0,5,4,8,9,3,4 }; int n = sizeof(a) / sizeof(a[0]); for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (a[j] < a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } for (int i = 0; i < n; i++) { printf("%d ", a[i]); } return 0; }这串代码就实现了数据的从大到小的排序了.
这里是因为已经有了i组的数据放到了正确的位置就需要减去i.
(3)局限
冒泡排序它很容易理解但是因为他是套用了两层循环我们可以计算得到他的时间复杂度是n的平方,
在有些的情况下它处理数据的时间并不够理想.
所以下面我将会介绍库函数中的一个排序函数qsort函数他的时间复杂度优于冒泡排序.
二.qsort函数排序
这个qsort函数是怎么样的函数?
我们知道在使用函数时我们要知道他处于的头文件和函数的参数.
下面我们就来查找一下这个函数的头文件和参数.
我们可以看到这个排序函数的参数有四个,其中还有一个函数指针的参数.
我们来逐一分析这个函数的参数
第一个参数当然就是我们要进行比较的数据的地址,比如我们想要比较一个数组的元素的话,我们第一个参数就要传入这个数组的地址
我们来看函数的第二个参数,这个参数的含义代表的时要比较的数据的个数,
第三个参数表示的是传入每个数据所占用字节的大小,
第四个参数是最重要的函数参数我们来着重来研究一下这个参数.
我们可以看到这个参数是一个函数,这个函数的返回值是一个int值,函数的参数是不知道void的指针.
我们来看这张图片
在指针的学习的过程中我们知道void类型的指针不能直接进行运算
并且这个函数的设计者并不确定我们即将比较的数据是什么类型的,所以只有使用者才知道我们要进行比较的数据的类型
所以传入void类型的指针是最合理的选择
我们从上面的图片知道这个compare函数的内容应该怎么使用,我们需要根据我们需要比较的数据类型来设计我们的compare函数 并且返回正确的值.
下面我将给出整型数组比较的示例:
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> int compare(const void* e1, const void* e2) { return *((int*)e1) - *((int*)e2); } int main() { int a[] = { 0,5,4,8,9,3,4 }; int n = sizeof(a) / sizeof(a[0]); /*for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (a[j] < a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } }*/ qsort(a, n, sizeof(a[0]), compare); for (int i = 0; i < n; i++) { printf("%d ", a[i]); } return 0; }注意事项:
(1)在使用qsort函数需要包含<stdlib.h>的头文件.
(2)在实现我们的compare函数时函数的参数必须和库里qsort函数的参数的类型一致.
(3)记得将需要比较的数据将void类型转换类型.
在了解上面的知识后有人就会好奇这个qsort函数的时间复杂度又是多少呢>>>n*log2n
这里2是以二为底的意思,
下面我们来用冒泡来模拟实现一下qsort函数.
三 模拟实现qsort
#include<stdio.h> void swap(char* e1,char* e2,int width) { char temp; for(int i=0;i<width;i++) { temp=*e1; *e1=*e2; *e2=temp; e1++; e2++; } } int compare(void* e1,void* e2) { return *((int*)e2)-*((int*)e1); } void jiaosqort(void* target,int sz, int width,int (*compare)(void* e1,void* e2)) { for(int i=0;i<sz-1;i++) { for(int j=0;j<sz-1-i;j++) { if(compare((char* )(target+j*width),(char*) (target+(j+1)*width))>0) { swap((char* )(target+j*width),(char*)target+(j+1)*width,width); } } } } int main() { int a[]={0,5,2}; int sz=sizeof(a)/sizeof(a[0]); jiaosqort(a,sz,sizeof(a[0]),compare); for(int i=0;i<sz;i++) { printf("%d ",a[i]); } return 0; }我来逐步讲解这个代码
(1)void jiaosqort(void* target,int sz, int width,int (*compare)(void* e1,void* e2));
这个是我们函数的主体的内容,他在内部使用了冒泡排序的算法来对数据进行数据的排序,
我们来看函数的这个部分
他和我们冒泡排序的这里是相同的:
只不过我们要处理的数据不仅仅是整形的数据就需要进行修改,我们看到我们在这个qsort的函数传参的时候我们传入了width的数据这里表示的就是每个数据的大小,
这里就能实现访问相邻的两两数据
(2)void swap(char* e1,char* e2,int width);
这里实现的是数据位置的交换
这里我们知道数据的字节大小所以我们就可以每个每个字节进行交换,这样我们就可以实现了不同数据类型的值的交换了.
以上就是今天排序的所有内容,大家可以自己试着使用这个库函数,也可以想想遇到特殊的数据类型怎么传函数参数,比如结构体.
谢谢大家的观看!!!