作者主页:paper jie的博客_CSDN博客-C语言,算法详解领域博主
本文作者:大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。
本文录入于《C语言》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造,将C语言基础知识一网打尽,希望可以帮到读者们哦。
其他专栏:《系统解析C语言》《算法详解》《C语言-语法篇》
内容分享:本期将用代码生撸C语言中的qsort函数实现冒泡排序,各位看官姥爷快搬好小板凳坐好叭。
-------- 不要998,不要98,只要一键三连,三连买不了吃亏,买不了上当
前言
在之前的文章中我们讲了简单冒泡排序的实现(不熟悉可以去回顾回顾http://t.csdn.cn/OI3hN),冒泡排序就是多种排序中的一种简单排序。核心思想就是相邻的元素两两比较,每一对都要比较,符合要求就交换位置,不断重复,直到没有元素需要比较。接下来我们将会了解C语言的库函数qsort,它也可以实现冒泡排序,而且比我们之前写的完善多了,可以适用于不同类型。
冒泡排序的实现
冒泡排序的核心思想是让相邻的元素两两比较,每一对都要比较,符合要求就交换位置,不断重复,直到没有元素需要比较
算法思想的实现:假设数组内有n个数随机排放。1.在数组初始状态下, 我们将整个数组设为排序范围,范围为数组下标为0-n-1的数。 2.从下标为0的数开始,两两相邻的数比较,如果前一个数大于后一个数,则进行交换。交换后再和后一个数进行比较,一直比较到最后一个数,这样最大的数就被排到到最后了。 3.前面为第一趟排序,我们需要进行n-1趟排序,假设第一次排序标记为0,标记数为i,每过一趟i+1,那么每次排序需要两两比较的次数为 n-1-i。4排序到没有元素可以排序后则排序完成。
下面的代码就是我们自己实现的冒泡排序,我们通过用i控制它的趟数,j控制它每一趟交换多少组来实现了升序。但是这里还有一个很大的问题:它只能对int类型的数据进行排序,换成其他的就不行了。那有没有什么可以让它可以用于不同的类型数据呢?
#include <stdio.h>
void bubble_sort(int* arr, int sz)
{
int i = 0;
int j = 0;
for (i = 0; i < sz - 1; i++)
{
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;
}
}
}
}
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
qsort函数
qsort函数的定义
qsort函数是C语言库中的一个函数,它的功能就是对不同的数据类型进行降序或者升序排序,就是相当于冒泡排序。不了解它也没关系,我们可以去 qsort - C++ Reference (cplusplus.com) 上查询qsort函数。
我们通过文档可以发现:qsort有4个参数,第一个参数就是数组的首地址,第二参数是数组的元素,第三个参数是元素的大小,第四个参数是一个函数指针,它是用来比较待排序中的两个元素的,它的返回值就是这两个元素相减,>0的话,qsort函数就交换两个元素。这个函数指针指向的函数需要使用者自己设计,因为设计者不知道你要排序的是什么类型的。需要引用头文件是stdlib.h。
qsort函数的使用
这里我们就以int数组,和结构体数组为例:
整型数组为例:
#include <stdio.h>
#include <stdlib.h>
//整型数组 - 例
int compar_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
int main()
{
//数组
int arr[10] = { 10,9,8,7,6,5,4,3,2,1 };
//元素个数
int sz = sizeof(arr) / sizeof(arr[0]);
//传参
qsort(arr, sz, sizeof(arr[0]), compar_int);
//打印
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
结构体数组为例:
#include <stdio.h>
#include <stdlib.h>
//整型数组 - 例
struct Stu
{
char name[20];
int age;
};
int compar_int(const void* e1, const void* e2)
{
return ((struct Stu*)e1)->age - ((struct Stu*)e2) -> age;
}
int main()
{
//数组
struct Stu s[] = { {"zhngsan",34},{"lishi",25},{"wangwu", 20}};
//元素个数
int sz = sizeof(s) / sizeof(s[0]);
//传参
qsort(s, sz, sizeof(s[0]), compar_int);
}
qsort函数的模拟实现
这里还是以int类型数组举例:文章来源:https://www.toymoban.com/news/detail-494069.html
#include <stdio.h>
int compar_int(const void*e1, const *e2)
{
return *(int*)e1 - *(int*)e2;
}
//交换函数
//通过char类型加上width来跳过元素
//char+width(类型的大小)刚好是一个类型的大小
void swap(char *e1, char *e2, int width)
{
int i = 0;
for (i = 0; i < width; i++)
{
//每一次循环交换一个字节控制的空间的内容
//循环完width次彻底交换两个元素
char tmp = *e1;
*e1 = *e2;
*e2 = tmp;
e1++;
e2++;
}
}
//模拟函数
void bublle_sort(void* base, int sz, int width, int (*compar)(const void*, const void*))
{
int i = 0;
int j = 0;
for (i = 0; i < sz - 1; i++)
{
for (j = 0; j < sz - 1 - i; j++)
{
//如果compar函数大于0 就交换
if (compar((char*)base + j * width, (char*)base + (j+1)*width)>0)
{
//交换函数实现
swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
}
}
}
}
int main()
{
int arr[10] = { 10,9,8,7,6,5,4,3,2,1 };
int sz = sizeof(arr) / sizeof(arr[0]);
//模拟qsort函数
bublle_sort(arr, sz, sizeof(arr[0]), compar_int);
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
return 0;
}
总结
这就是qsort函数的使用和模拟,我们通过使用和模拟发现,qsort函数它非常的巧妙,不由的让我们感叹写出这些代码的人脑子怎么长的,不过我相信只要我们一直学习下去,总有一天我们也有写出这种代码的可能性,与君共勉!文章来源地址https://www.toymoban.com/news/detail-494069.html
到了这里,关于用代码生撸qsort函数来实现冒泡排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!