网站主机选择与优化,wordpress 知更鸟 公告,有哪些可以免费推广的网站,哪些网站做企业招聘不要花钱文章目录 一、冒泡排序二、qsort排序1. qsort使用指南2.回调函数3. qsort函数的模拟实现 一、冒泡排序
冒泡排序的核心思想就是#xff1a;两两相邻的元素进行比较和交换。 现在#xff0c;我们想编写一个函数#xff0c;使它能够运用冒泡排序的原理#xff0c;由小到大排… 文章目录 一、冒泡排序二、qsort排序1. qsort使用指南2.回调函数3. qsort函数的模拟实现 一、冒泡排序
冒泡排序的核心思想就是两两相邻的元素进行比较和交换。 现在我们想编写一个函数使它能够运用冒泡排序的原理由小到大排好一个乱序的整形数组。例如假如输入5、2、1、10、9、7、3、4、8、6能输出1、2、3、4、5、6、7、8、9、10。如果画图分许这个排序过程的每一步 看经过第一轮的两两比较较大的数排到右边这样最大的10就来到了最右边。 而经过第二次排序第二大的9就能来到倒数第二个位置。
像这样继续排序这个数组的大小是10经过9次10-1次排序就能完成1到10的排序。 知道了原理在代码层面编写这样的函数就非常简单了
void bubble_Sort(int* p ,int sz)
{
for(int turn1 ; turnsz-1 ; turn)//要排n个数字就需要进行n-1轮排序for(int i0 ; isz-1 ; i)if(p[i] p[i1]){int tmp p[i];p[i] p[i1];p[i1] tmp;}
}当然为了节省运行时间我们还可以进行一点优化假如这个数组在第一趟排序后就已经有序了它就可以直接停止而没必要再排序好多次。
void bubble_Sort(int* p ,int sz)
{
for(int turn1 ; turnsz-1 ; turn)
{int flag 1;//假设这一次已经有序了for(int i0 ; isz-1 ; i){if(p[i] p[i1]){flag 0;//发生了交换说明这一次还不是有序int tmp p[i];p[i] p[i1];p[i1] tmp;}}if(flag1)break;//这一次没有发生交换说明已经有序了可以退出函数了
}
}这样整个程序就是
#includestdio.h
void bubble_Sort(int* p ,int sz)
{
for(int turn1 ; turnsz-1 ; turn)
{int flag 1;for(int i0 ; isz-1 ; i){if(p[i] p[i1]){flag 0;int tmp p[i];p[i] p[i1];p[i1] tmp;}}if(flag1)break;
}
}int main()
{
int arr[10]{0};
for(int i0 ; i10 ; i)scanf(%d,arr[i]);
bubble_Sort(arr, sizeof(arr)/sizeof(arr[0]));
for(int i0 ; i10 ; i)printf(%d ,arr[i]);
return 0;
}结果也是非常的成功~
二、qsort排序
1. qsort使用指南
冒泡排序只能用来排序整型数字而且写起来太麻烦了。如果我们有了一组数据想要直接快速按某种方式排序该怎么办呢 乂~C语言提供了一个库函数qsort可以按照你想要的方式排序各种类型的数据使用它需要包含头文件stdlib.h 在链接https://legacy.cplusplus.com/reference/clibrary/中我们可以查到
借助翻译 不理解也没关系简言之qsort函数的语法形式是
void qsort(void* base, size_t num, size_t size, int(*compar)(const void*,const void*));其中
base指针指向的是待排序数据中的第一个元素num是待排序数据的个数size是待排序数据中的每一个元素的字节大小compar是一个函数指针这个函数用来比较base指向的数据中任意两个元素的大小 注意compar函数需要使用者自己提供也就是要自己提供比较数据的方式。这个函数有两个参数也就是要比较的两个元素需要返回一个整型数。
不要着急我们先来个简单的栗子用qsort函数排序一个整型乱序数组
#includestdlib.h
#includestdio.h
int compar_int(const void* p1, const void* p2)
{
return ( *(int*)p1 - *(int*)p2 );
//p1和p2一开始是void*指针但是实际上他们指向的都是整型数据所以要(int*)强制类型转换
}int main()
{
int arr[] {5,2,1,10,9,7,3,4,8,6};//待排序数组
int sz sizeof(arr)/sizeof(arr[0]);
qsort(arr, sz, sizeof(int), compar_int);
//arr第一个元素的地址
//sz元素个数
//sizeof(int)每个元素的字节大小
//compar_int用来比较的函数的地址
for(int i0 ; isz ; i)printf(%d ,arr[i]);
return 0;
}很完美的结果。 但我们不禁思考这个qsort函数是怎么依靠compar函数实现交换和排序的呢 其实qsort函数每次比较compar函数的两个参数这两个指针参数指向的是任意的元素依靠compar函数的返回值判断是否要交换
返回值为负就把p1指向的元素放在p2指向的元素后面返回值为0不交换返回值为正就把p1指向的元素放在p2指向的元素前面。
这里“前”指的是数组下标较大的位置“后”是下标较小的位置
所以上面的程序能实现由小到大的排序而如果你想由大到小排只需要把compar_int里的return ( *(int*)p1 - *(int*)p2 );改为return ( *(int*)p2 - *(int*)p1 );就可以了 不光是整型如果我们想把一个字符数组按照ASCII的大小排序也可以使用qsort函数
#includestdlib.h
#includestdio.h
int compar_char(const void* p1, const void* p2)
{
return ( *(char*)p1 - *(char*)p2 );
//p1和p2一开始是void*指针但是实际上他们指向的都是字符型数据所以要(char*)强制类型转换
}int main()
{
char arr[] {b,t,m,a,a,x};//待排序数组
int sz sizeof(arr)/sizeof(arr[0]);
qsort(arr, sz, sizeof(char), compar_char);
for(int i0 ; isz ; i)printf(%c ,arr[i]);
return 0;
}2.回调函数
回调函数的概念很简单它就是一个通过函数指针调用的函数。 如果你把函数的地址作为参数传递给另一个函数当这个指针被用来调用其所指向的函数时被调用的函数就是回调函数了。回调函数不是由该函数的实现方直接调用的而是在特定的条件下由另一方调用的用于对该条件进行响应。
3. qsort函数的模拟实现
首先我要说的是后期我们还会学习到很多的函数他们都有不同的功能但我们不仅要学会使用他们还应该学会模拟实现这些函数。所谓模拟实现是创造一个自己的函数传递原函数相同的参数也要能达到原函数的效果。今天我们也应该学会模拟实现qsort函数。定义一个函数void Mine_qsort(void* base, size_t num, size_t size, int(*compar)(const void*,const void*));这就是我模拟实现的qsort函数。 而具体交换思路呢可以分为比较、交换两步运用了回调函数的概念和冒泡排序的思想。
#includestdio.h
int compar_int(const void* p1, const void* p2)
{
return (*(int*)p1 - *(int*)p2);
}void swap(const void* p1, const void* p2)
{
int tmp *((int*)p1);
*((int*)p1) *((int*)p2);
*((int*)p2) tmp;
}void Mine_qsort(void* base, size_t num, size_t size, int(*compar)(const void*,const void*))
{
for(int turn1 ; turnnum-1 ; turn)for(int i0 ; inum-1 ; i)if(compar( (int*)basei, (int*)basei1 ) 0)swap( (int*)basei, (int*)basei1 );
}int main()
{
int arr[]{2,6,4,10,5,3,1,8,7,9};
Mine_qsort(arr, sizeof(arr)/sizeof(arr[0]), sizeof(int), compar_int);
for(int i0 ; i10 ; i)printf(%d ,arr[i]);
return 0;
}这样我们就模拟实现了qsort函数 然鹅我的代码只能排序整型数组如果要排序其他类型数据也可以采用另外一种通法一个字节一个字节地交换这样能突破不同数据类型大小不同的限制。感兴趣的各位可以自行研究~
欲知后事如何且听下回分解~
本篇完感谢阅读
