企业集团网站建设方案,成都微信公众号制作,wordpress free,要建设企业网站冒泡排序是一种简单的排序算法#xff0c;它重复地走访过要排序的数列#xff0c;一次比较两个元素#xff0c;如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换#xff0c;也就是说该数列已经排序完成。1.冒泡排序关于冒泡排序我们在讲…冒泡排序是一种简单的排序算法它重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。1.冒泡排序关于冒泡排序我们在讲初阶数组时讲到过现在再来复习一下1.1.核心思想冒泡排序的核心思想是通过比较相邻元素的大小将较大的元素交换到右边从而使序列中的最大元素逐渐“浮”到最右端最小元素“沉”到最左端。例排序前int arr[10] { 8,5,6,2,3,1,4,9,7,10 };排序后int arr[10] { 1,2,3,4,5,6,7,8,9,10 };1.2代码实现如何使用代码来实现冒泡排序呢首先得确定排序的趟数和一趟排序的次数可以先来分析一下因此冒泡排序的趟数设置就是整个数组总长-1因此循环变量的限制条件就为数组总长-1关于冒泡排序一趟中排序的次数需要再设置一个循环变量但是这个循环变量的限制条件决定了一趟中排序的次数根据上面的演示第一趟排序的次数是9第二次是8第三次为7.....以此类推每进行一趟排序一趟中排序的次数就减一因此在控制排序次数的循环变量的限制条件为总长减1再减趟数代码演示#include stdio.h
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;}}}
}void print_arr(int arr[], int sz)
{int i 0;for (i 0; i sz; i){printf(%d , arr[i]);}printf(\n);
}int main()
{int arr[] { 5,4,8,9,7,6,3,2,1,10 };//使用冒泡排序的算法来排序int sz sizeof(arr) / sizeof(arr[0]);printf(排序前:);print_arr(arr, sz);bubble_sort(arr, sz);//打印printf(排序后:);print_arr(arr, sz);return 0;
}这样写就可以实现冒泡排序但是有一点上面写的代码只能排序整型数组如果要排序字符、结构体...就不能适用了因此我们来学习一个新的排序方式2.qsprt排序qsort函数是一个用于对数组快速排序的函数它是C标准库中的一个函数可以对任何类型的数组进行排序。qsort的底层使用的是快排的算法。函数原型为void qsort(void* base, size_t nitems, size_t size, int (*compar)(const void*, const void*));其中base指向要排序的数组nitems是数组中元素的个数size是每个元素的大小compar是比较函数用于比较两个元素的大小。void qsort( void* base, //指向要排序的数组size_t num, //数组中元素的个数size_t size, //数组中每个元素的大小int (*compar)(const void*, const void*));//指向一个函数这个函数可以比较两个元素的大小这个函数的第一个参数是一个void* 的指针因为void*的指针可以存放任何类型的指针这样有助于排序任何类型的数据第二个参数是一个无符号整形的数据表示元素个数第三个参数也是一个无符号整形的数据表示元素大小第四个参数是一个函数指针这个函数指针需要我们自己设计因为这个qsort函数可以排序任何类型的数据因此你需要排序什么类型的数据就可以自己设置什么样的函数可以使用C语言工具来查一下这个函数如果听到这里还没有挺明白的话也不要着急下面给大家举个例子来用一下qsort函数使用qsort来对整型数组进行排序代码演示#include stdio.h
#include stdlib.h
void print_arr(int arr[], int sz)
{int i 0;for (i 0; i sz; i){printf(%d , arr[i]);}printf(\n);
}
int cmp_int(const void* p1, const void* p2) //设置比较两个元素大小的函数
{return *(int*)p1 - *(int*)p2;//由于比较的是两个整形的数组因此需要对其进行强制类型转化为int*的指针然后解引用找到这个数//如果返回值大于0证明前面的数p1大于后面的数p2需要交换//如果返回值小于0证明前面的数p1小于后面的数p2不需要交换//如果返回值等于0证明两个数相等也不需要交换
}
int main()
{int arr[] { 5,8,9,6,3,2,7,1,4,10 };int sz sizeof(arr) / sizeof(arr[0]);printf(排序前);//打印print_arr(arr, sz);//排序qsort(arr, sz, sizeof(arr[0]), cmp_int); //这里的cmp_int就是一个回调函数printf(排序后);print_arr(arr, sz);return 0;
}注意cmp_ 函数需要自己设置需要什么类型就需要强制类型转化为什么类型对结构体进行排序对于结构体也可以进行排序只不过需要告诉cmp_函数需要排结构体中的什么比如名字、年龄、时间......关于结构体的创建和对结构体成员的访问要理解访问结构体变量使用.操作符访问结构体指针使用-操作符比较两个字符串的大小使用的是strcmp对年龄进行排序代码演示#include stdio.h
#include stdlib.h
struct Str
{char name[20];int age;
};
int cmp_str_by_age(const void* p1, const void* p2)
{//这里使用结构体指针来访问结构体成员return ((struct Str*)p1)-age - ((struct Str*)p2)-age;
}
void test1()
{struct Str s[] { {zhangsan,55},{lisi,45},{wangwu,25} };int sz sizeof(s) / sizeof(s[0]);printf(年龄排序\n);printf(排序前:\n);int i 0;for (i 0; i sz; i){printf(年龄%d\n, s[i].age);}qsort(s, sz, sizeof(s[0]), cmp_str_by_age);printf(排序后\n);for (i 0; i sz; i){printf(年龄%d\n, s[i].age);}
}
int main()
{//对年龄进行排序test1();return 0;
}对名字进行排序对名字排序就是对首字母的ASCII码值进行排序如果首字母一样就使用第二个字母进行排序依次类推代码演示#include stdio.h
#include stdlib.h
#include string.h
struct Str
{char name[20];int age;
};
int cmp_str_by_name(const void* p1, const void* p2)
{return strcmp(((struct Str*)p1)-name, ((struct Str*)p2)-name);
}
void test2()
{struct Str s[] { {zhangsan,55},{lisi,45},{wangwu,25} };int sz sizeof(s) / sizeof(s[0]);printf(名字排序\n);printf(排序前:\n);int i 0;for (i 0; i sz; i){printf(名字%s\n, s[i].name);}qsort(s, sz, sizeof(s[0]), cmp_str_by_name);printf(排序后\n);for (i 0; i sz; i){printf(名字%s\n, s[i].name);}
}
int main()
{//对年龄进行排序//test1();//对名字进行排序test2();return 0;
}因此qsort的排序功能是非常广泛的它的底层逻辑是快速排序的算法那我们可以用冒泡排序的算法也实现一个类似与qsort的函数3.冒泡排序思想实现qsort上面写的冒泡排序只可以实现整数数组的比较功能单一我们可以使用冒泡排序的思想实现类似于qsort的一种排序的方法qsort的底层逻辑是快速排序。基本框架和qsort的框架一样只是需要类似于qsort函数的代码来实现代码演示#include stdio.h
//实现比较大小的函数
int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}
//打印函数
void print_arr(int arr[], int sz)
{int i 0;for (i 0; i sz; i){printf(%d , arr[i]);}printf(\n);
}
void test1()
{int arr[] { 8,9,6,5,2,3,1,4,7,10 };int sz sizeof(arr) / sizeof(arr[0]);printf(排序前);print_arr(arr, sz);//类似于qsort函数的冒泡排序bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);printf(排序后);print_arr(arr, sz);
}
int main()
{test1();return 0;
}3.1冒泡排序函数实现使用冒泡排序逻辑实现类似于qsort函数的排序方法因此冒泡排序的逻辑就可以使用因此设置冒泡排序的趟数和一趟排序的次数都是不变的只是要注意在什么条件下需要交换怎么样交换交换什么代码演示//这时的函数参数就可以参考qsort函数的函数参数
//void qsort( void* base, //指向要排序的数组//size_t num, //数组中元素的个数//size_t size, //数组中每个元素的大小//int (*compar)(const void*, const void*));//指向一个函数这个函数可以比较两个元素的大小
void bubble_sort(void* base, size_t num, size_t width, int(*cmp_int)(const void* e1, const void* e2))
{size_t i 0; //这里的参数类型要与函数参数类型一致都为无符号整型//设置冒泡排序的趟数for (i 0; i num; i){size_t j 0;//设置一趟冒泡排序需要交换的次数for (j 0; j num - 1 - i; j){//判断交换if (){}}}
}这里要注意在什么条件下需要交换因为在设置这个函数时的函数参数是void*目的就是为了用来比较任何类型的数据因为我们又创建了一个比较大小的函数因此就可以通过比较函数的返回值来确定怎样交换如果比较函数的返回值小于0那就证明前面的一个数据小于后面的一个数据就不需要交换如果返回值大于0就证明前面的一个数据大于后面的一个数据就需要实现交换因此需要交换的条件就可以将cmp_int的返回值作为判断条件如果0就交换代码演示if (cmp_int()0)//这里还没有给这个函数传参呀那该传怎样的参数呢
{
} 根据比较函数的函数参数来进行传参也就是说要传给它两个地址一个地址是前一个数据的地址另外一个是后面一个地址的数据那就要注意前一个地址和后一个地址该怎么传呢关于指针的计算我们也知道什么类型的指针加减整数就意为着跳过整数个类型的地址但是这里是void*的类型那是不是可以传参void* basej和void* basej1这样做是不可以的void*可以接收任何类型的指针但并不意味着可以当成任何类型拿来使用使用时需要进行强制类型转化需要什么类型就强制转化为什么类型就可以这里我们需要比较的是整型数组就需要转化为int*类型(int*) basej, (int*) basej1的指针来使用,但是我们实现的这个冒泡排序是可以排序任何类型的数据所以也不能直接改为int*的指针所以还得另寻出路//代码1
if (cmp_int(base j , base j 1 )0)
{}
//代码2
if (cmp_int((int*)base j , (int*)base j 1 )0)
{}
//代码1和代码2都是不可行的操作 我们都知道char*的指针对其进行加减整数只能跳过一个字节那么如果将参数类型转化为char*的类型然后再乘上宽度数组中一个元素的大小是不是就可以达到转化任意类型的效果了,假设要排序整形一个整形的大小是4个字节因此用char*的指针*4就表明每一次要跳过4个字节的空间也就是一个整形代码演示int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2; //通过地址找到数据进行比较
}
if (cmp_int((char*)base j * width , (char*)base (j 1) * width)0)
{//如果前一位数据大于后一位数据就满足条件//交换//交换函数
} 3.2交换函数的实现如果前一个数据大于后一个数据就实现交换那该怎么交换呢可以采用一个字节一个字节的交换方式设置循环使用宽度来设置交换的次数4个字节就交换四次因此再给交换函数传参时需要传两个起始地址和宽度代码演示void Swp(char* buf1, char* buf2, int width)
{int i 0;for (i 0; i width; i){char tmp *buf1;*buf1 *buf2;*buf2 tmp;buf1;buf2;}
}
if (cmp_int((char*)base j * width , (char*)base (j 1) * width)0)
{ //如果满足分支语句条件就进来交换Swp((char*)base j * width, (char*)base (j 1) * width, width);
}3.3整体代码展示#include stdio.h
int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}
void print_arr(int arr[], int sz)
{int i 0;for (i 0; i sz; i){printf(%d , arr[i]);}printf(\n);
}
void Swp(char* buf1, char* buf2, int width)
{int i 0;for (i 0; i width; i){char tmp *buf1;*buf1 *buf2;*buf2 tmp;buf1;buf2;}
}
void bubble_sort(void* base, size_t num, size_t width, int(*cmp_int)(const void* e1, const void* e2))
{size_t i 0;for (i 0; i num; i){size_t j 0;for (j 0; j num - 1 - i; j){if (cmp_int((char*)base j * width , (char*)base (j 1) * width)0){Swp((char*)base j * width, (char*)base (j 1) * width, width);}}}
}
void test1()
{int arr[] { 8,9,6,5,2,3,1,4,7,10 };int sz sizeof(arr) / sizeof(arr[0]);printf(排序前);print_arr(arr, sz);bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);printf(排序后);print_arr(arr, sz);
}
int main()
{test1();return 0;
}但是如果有一个数组int arr[] { 21345678910 }可以看到这个数组如果要排序的话只需要排第一个和第二个就可以就不需要继续判断后面的数据因此可以将代码优化一下可以设置一个变量如果交换了就将变量修改如果变量没有被修改就要跳出循环代码优化#include stdio.h
//比较两个数据的大小
int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}
//打印函数
void print_arr(int arr[], int sz)
{int i 0;for (i 0; i sz; i){printf(%d , arr[i]);}printf(\n);
}
//交换函数
void Swp(char* buf1, char* buf2, int width)
{int i 0;for (i 0; i width; i){char tmp *buf1;*buf1 *buf2;*buf2 tmp;buf1;buf2;}
}
//使用冒泡排序的思想来实现类似于qsort的排序算法
void bubble_sort(void* base, size_t num, size_t width, int(*cmp_int)(const void* e1, const void* e2))
{size_t i 0;//假设数组有序int flag 1;for (i 0; i num; i){size_t j 0;for (j 0; j num - 1 - i; j){if (cmp_int((char*)base j * width , (char*)base (j 1) * width)0){//交换将flag赋值为0flag 0;//交换Swp((char*)base j * width, (char*)base (j 1) * width, width);} }if (1 flag){break;}}
}
void test1()
{int arr[] { 8,9,6,5,2,3,1,4,7,10 };int sz sizeof(arr) / sizeof(arr[0]);printf(排序前);print_arr(arr, sz);bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);printf(排序后);print_arr(arr, sz);
}
int main()
{//排序整形数组test1();return 0;
}使用冒泡排序对结构体进行排序#include stdio.h
#include string.h//比较两个数据的大小
int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}
//打印函数
void print_arr(int arr[], int sz)
{int i 0;for (i 0; i sz; i){printf(%d , arr[i]);}printf(\n);
}
//交换函数
void Swp(char* buf1, char* buf2, int width)
{int i 0;for (i 0; i width; i){char tmp *buf1;*buf1 *buf2;*buf2 tmp;buf1;buf2;}
}
//使用冒泡排序的思想来实现类似于qsort的排序算法
void bubble_sort(void* base, size_t num, size_t width, int(*cmp_int)(const void* e1, const void* e2))
{size_t i 0;//假设数组有序int flag 1;for (i 0; i num; i){size_t j 0;for (j 0; j num - 1 - i; j){if (cmp_int((char*)base j * width , (char*)base (j 1) * width)0){//交换将flag赋值为0flag 0;//交换Swp((char*)base j * width, (char*)base (j 1) * width, width);}}if (1 flag){break;}}
}
struct Str
{char name[20];int age;
};
//比较年龄
int cmp_str_by_age(const void* p1, const void* p2)
{return ((struct Str*)p1)-age - ((struct Str*)p2)-age;//这里使用-来访问结构体指针
}void test2()
{//结构体初始化struct Str s[] { {zhangsan,55},{lisi,25},{wangwu,35} };int sz sizeof(s) / sizeof(s[0]);bubble_sort(s, sz, sizeof(s[0]), cmp_str_by_age);
}
int cmp_str_by_name(const void* p1, const void* p2)
{return strcmp(((struct Str*)p1)-name, ((struct Str*)p2)-name);
}
void test3()
{struct Str s[] { {zhangsan,55},{lisi,25},{wangwu,35} };int sz sizeof(s) / sizeof(s[0]);bubble_sort(s, sz, sizeof(s[0]), cmp_str_by_name);
}
int main()
{//对年龄进行排序test2();//对名字进行排序test3();return 0;
}
如果要对年龄进行排序要将对名字排序的代码注释掉要不然会混在一起这里并没有将它们打印出来只是在调试的监视窗口中观察到的如果要打印出来可以在冒泡排序的函数下面加上循环打印结构体void test3()
{struct Str s[] { {zhangsan,55},{lisi,25},{wangwu,35} };int sz sizeof(s) / sizeof(s[0]);bubble_sort(s, sz, sizeof(s[0]), cmp_str_by_name);int i 0;for (i 0; i sz; i){printf(姓名%s\n, s[i].name);}
}
void test2()
{struct Str s[] { {zhangsan,55},{lisi,25},{wangwu,35} };int sz sizeof(s) / sizeof(s[0]);bubble_sort(s, sz, sizeof(s[0]), cmp_str_by_age);int i 0;for (i 0; i sz; i){printf(年龄%d\n, s[i].age);}
}
