C语言冒泡排序法和amp;Qsort函数和自定义实现八大排序:二
目录
冒泡排序原理
是一种较简单的排序算法,依次比较相邻元素,如果顺序错误则进行调换(A ~ Z,或数字),算法的核心在于依次比较,依次调换位置
冒泡排序升序:
如:3,1,4,2
升序后:1,2,3,4
第一批比较:
3>1,所以1和3互换:1,3,4,2
3<4,所以3和4位置不变
4>2,所以4和2互换:1,3,2,4
第一批比较完毕,调换了3次。此时最大数4已经放在了最末尾,所以4不再进行比较排序。
第二批比较:
1<3,所以1和3位置不变
3>2,所以2和3交换:1,2,3,4
到此,其实结果已经出来了,但是根据冒泡排序原理:
第一批是将4放在了末尾,第二批是将3放在了倒数第二位。所以还剩下1和2没有排序。
第三批比较:
1<2:所以1和2位置不变。
从简单的1,2,3,4序列进行冒泡排序的理解。
我们可以得知:n个数的第一批进行n-1次比较排序。
(所以最外层是n-1次循环)
-
for(int i =1; i<n; i )
-
{
-
-
}
对于内层分析:
第一批:n-1次比较循环
第二批:n-2次比较循环
...
第i批:n-i次比较循环
-
for(int i=1;i<n;i )
-
{
-
-
for(int j=0;j<n-1-i;j )/*j从0开始,因为数组下标从0开始*/
-
{
-
if (num[j] < num[j 1])
-
{
-
int temp = num[j];
-
num[j] = num[j 1];
-
num[j 1] = temp;
-
}
-
}
-
-
}
-
//为什么是n-1-i?
j的范围
j从0开始:数组下标从0开始
进行第i次循环:n-i
因为是num[j]和num[j 1]进行比较,所以要保证 j 1 不越界
所以j 1<n-i
j<n-1-i
冒泡排序代码
-
-
-
void print(int* parr)
-
{
-
int i = 0;
-
for (i = 0; i < 10; i )
-
{
-
printf("%d ", *(parr i));
-
}
-
}
-
void Bubble_Sort(int num[], int n)
-
{
-
int flag = 1;
-
for (int i = 0; i < N-1; i )//有10个元素,则循环9次
-
{
-
for (int j = 0; j < N - 1 - i; j )//N-1表示末端元素下标,因为后续有j 1,所以j不取等
-
{
-
if (num[j] > num[j 1])//从0号元素开始,相邻进行比较
-
{
-
int temp = num[j];
-
num[j] = num[j 1];
-
num[j 1] = temp;
-
flag = 0;
-
}
-
}
-
if(flag) break;
-
}
-
}
-
-
int main()
-
{
-
//相邻两个元素进行比较,大的放后面。n个元素比较n-1次
-
int arr[N] = { 12,33,4,57,9,100,123,32,87,98 };
-
-
printf("原数顺序:>");
-
print(arr);
-
-
Bubble_Sort(arr, N);
-
-
printf("\n冒泡排序后顺序:>");
-
print(arr);
-
-
return 0;
-
}
如果要进行降序的冒泡排序,只需要把if中的大于号改成小于号即可:
-
void Reverse_Bubble(int num[], int n)
-
{
-
for (int i = 1; i < N; i )//有10个元素,则循环9次
-
{
-
for (int j = 0; j < N - 1 - i; j )//N-1表示末端元素下标,因为后续有j 1,所以j不取等
-
{
-
if (num[j] < num[j 1])//从0号元素开始,相邻进行比较
-
{
-
int temp = num[j];
-
num[j] = num[j 1];
-
num[j 1] = temp;
-
}
-
}
-
}
-
}
库函数中的Qsort函数
qsort函数(quick sort)C语言编译器函数库自带的排序函数;
包含在C 标准库 - <stdlib.h>中。
对一维数组、二维数组、字符串、结构体、结构体中的字符串等等进行快速排序。
qsort函数原型
各个参数的说明
base:将首元素的地址传给qsort函数,确定开始排序的位置。
num:排序元素的个数。
size:排序的元素的(大小),单位是字节。由于qsort函数可以排序大部分类型的数据,输入数据类型,将void*强制类型转化为int*或char*等,由此导致了qsort函数的普适性。
自定义compar函数:你需要告诉qsort函数,你需要如何进行比较,进行升序排列还是降序排列,如何自定义一个compar函数即可。用来比较待排序数据中两个元素的大小。
返回值:
1、后一个元素更大:返回值小于0
2、两个元素一样大:返回值等于0
3、前一个元素更大:返回值大于0
qsort函数使用示例1(数字排列):>
-
-
-
-
int arr[] = { 2, 3, 6, 5, 4, 1 };//要排序的数组
-
int sz = sizeof(arr) / sizeof(arr[0]);//数组元素个数
-
-
int compare(const void* a, const void* b)
-
{
-
return (*(int*)a - *(int*)b);
-
}
-
-
int main()
-
{
-
int n;
-
qsort(arr, sz, sizeof(int), compare);
-
for (n = 0; n < 6; n )
-
printf("%d ", arr[n]);
-
-
return 0;
-
}//输出结果:> 1 2 3 4 5 6
-
//如果需要降序,只需将compare函数中return改为b-a的形式即可
qsort函数使用示例2(结构体成员按照序号排列&按照名字排列):>
-
-
-
struct Stu
-
{
-
char name[20];
-
int num;
-
};
-
int sort_by_num(const void* a, const void* b)//使用const增加常属性,防止比较的数据被改变
-
{
-
return ((struct Stu*)a)->num - ((struct Stu*)b)->num;
-
}
-
int sort_by_name(const void* a, const void* b)
-
{
-
return strcmp(((struct Stu*)a)->name, ((struct Stu*)b)->name);
-
}
-
int main()
-
{
-
struct Stu s[] = { {"一号",1},{"四号",4},{"三号",3},{"五号",5},{"二号",2}};
-
int sz = sizeof(s) / sizeof(s[0]);
-
printf("排序前:>\n");
-
for (int i = 0; i < sz; i )
-
printf("%s %d ", s[i].name, s[i].num);
-
//按照序号排序
-
qsort(s, sz, sizeof(s[0]), sort_by_num);
-
printf("\n按照序号排序后:>\n");
-
for (int i = 0; i < sz; i )
-
printf("%s %d ", s[i].name, s[i].num);
-
//按照名字排序(a~z)
-
qsort(s, sz, sizeof(s[0]), sort_by_name);
-
printf("\n按照序号排序后:>\n");
-
for (int i = 0; i < sz; i )
-
printf("%s %d ", s[i].name, s[i].num);
-
}
Qsort函数自定义实现
模仿qsort函数的原型,自定义一个通用的冒泡排序bubble_sort:
1、自定义bubble_sort函数
2、自定义compare函数(下面简化为cmp函数)
3、交换函数Swap(使用空瓶、异或操作符)
1、先定义出一个void bubble_sort函数,四个参数
2、自定义的函数体
//与冒泡排序原理相似,唯一的区别在于上述冒泡排序函数功能单一
int i = 0;
for (i = 0; i < sz - 1; i )
{
int j = 0;
for (j = 0; j < sz - 1 - i; j )
{if(表达式大于0)
{
//条件满足则进行交换
Swap(参数);}
}
}
3、if语句内的条件、Swap函数的参数
数据处理:
对于一个数组两个元素比较即: arr[ j ] 与 arr[ j 1 ]
在指针中就是: *( arr j ) 与 *( arr j 1)
参照自定义函数写成: *(base j) 与 *(base j 1)
由于是void函数,类型大小用size表示,size表示类型大小(字节)
所以最终表述为: (*base) j*size 与 (*base) (j 1)*size
补充一下细节:
- 比较两个元素,传入两个元素的地址给cmp函数
- char是1byte,可以随意改变访问的跨度
- 加上一个元素所占字节就可以跳到下一个元素
- 所以用char*base表示首地址,由于是函数参数是void*
- 所以强制类型转换(char*)base表示数据首地址
if语句:将两个数据放入cmp函数中,判断返回值是否大于0
Swap函数:交换两个指针变量即可,下列代码用空瓶实现(优化可以用^进行交换)
-
void Swap(char* bu1, char* bu2, int sz)
-
{
-
int i = 0;
-
for (i = 0; i < sz; i )
-
{
-
char tmp = *bu1;
-
*bu1 = *bu2;
-
*bu2 = tmp;
-
bu1 ;
-
bu2 ;
-
}
-
}
-
void bubble_sort(
-
void* base,//第一个元素地址
-
int sz, //元素个数
-
int size, //元素类型(大小)
-
int(*cmp)(const void* a, const void* b)//自定义函数compare
-
)
-
{
-
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*size,(char*)base (j 1)*size) > 0)
-
{
-
//条件满足则进行交换
-
Swap((char*)base j * size, (char*)base (j 1) * size,size);
-
}
-
}
-
}
-
}
代码看起来好像很复杂,是因为要交换的元素书写比较复杂,理解如下:
if ( cmp(参数1,参数2) > 0 )
Swap(参数1,参数2)
最后,只需要将qsort函数注释掉,用bubble_sort函数进行实现即可,代码如下
自定义类似Qsort函数代码
-
//头文件引入
-
-
-
//函数声明
-
void Swap(char* bu1, char* bu2, int sz);
-
int cmp_int(const void* a, const void* b);
-
int cmp_by_num(const void* a, const void* b);
-
int cmp_by_name(const void* a, const void* b);
-
void bubble_sort(void* base, int sz, int size, int(*cmp)(const void* a, const void* b));
-
//结构体声明
-
struct Stu
-
{
-
char name[20];
-
int num;
-
};
-
-
//主函数
-
int main()
-
{
-
int arr[] = { 2, 3, 6, 5, 4, 1 };//要排序的数组
-
int sz_arr = sizeof(arr) / sizeof(arr[0]);
-
//要排序的结构体成员
-
struct Stu s[] = { {"一号",1},{"四号",4},{"三号",3},{"五号",5},{"二号",2} };
-
int sz_s = sizeof(s) / sizeof(s[0]);
-
printf("排序前的数组>\n");
-
for (int i = 0; i < sz_arr; i )
-
printf("%d ", arr[i]);
-
printf("\n排序前的结构体成员>\n");
-
for (int i = 0; i < sz_s; i )
-
printf("%s %d ", s[i].name, s[i].num);
-
//开始排序
-
bubble_sort(arr, sz_arr, sizeof(arr[0]), cmp_int);
-
bubble_sort(s, sz_s, sizeof(s[0]), cmp_by_num);
-
-
printf("\n排序后的数组:>\n");
-
for (int i = 0; i < sz_arr; i )
-
printf("%d ", arr[i]);
-
printf("\n按序号排序后的结构体成员>\n");
-
for (int i = 0; i < sz_s; i )
-
printf("%s %d ", s[i].name, s[i].num);
-
bubble_sort(s, sz_s, sizeof(s[0]), cmp_by_name);
-
printf("\n按字母名字排序后的结构体成员>\n");
-
for (int i = 0; i < sz_s; i )
-
printf("%s %d ", s[i].name, s[i].num);
-
-
}
-
-
//交换两个数据的函数
-
void Swap(char* bu1, char* bu2, int sz)
-
{
-
int i = 0;
-
for (i = 0; i < sz; i )
-
{
-
char tmp = *bu1;
-
*bu1 = *bu2;
-
*bu2 = tmp;
-
bu1 ;
-
bu2 ;
-
}
-
}
-
-
//自定义int compare函数
-
int cmp_int(const void* a, const void* b)
-
{
-
return (*(int*)a - *(int*)b);
-
}
-
int cmp_by_name(const void* a, const void* b)
-
{
-
return strcmp(((struct Stu*)a)->name, ((struct Stu*)b)->name);
-
}
-
int cmp_by_num(const void* a, const void* b)
-
{
-
return ((struct Stu*)a)->num - ((struct Stu*)b)->num;
-
}
-
-
//自定义sort函数
-
void bubble_sort(
-
void* base,//第一个元素地址
-
int sz, //元素个数
-
int size, //元素类型(大小)
-
int(*cmp)(const void* a, const void* b)//自定义函数compare
-
)
-
{
-
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 * size, (char*)base (j 1) * size) > 0)
-
{
-
//条件满足则进行交换
-
Swap((char*)base j * size, (char*)base (j 1) * size, size);
-
}
-
}
-
}
-
}
期待你的点赞加关注啦,第一篇博客收工!
oh yeah~
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhghfgeg
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13