©2020-2024 ioDraw All rights reserved,
Privacy Policy
冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
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.qsort排序
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*
base+j和void*
base+j+1？这样做是不可以的，void*可以接收任何类型的指针，但并不意味着可以当成任何类型拿来使用，使用时需要进行强制类型转化，需要什么类型就强制转化为什么类型就可以，这里我们需要比较的是整型数组，就需要转化为int*类型（(int*)
base+j, (int*)
base+j+1）的指针来使用,但是我们实现的这个冒泡排序是可以排序任何类型的数据，所以也不能直接改为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[] = { 2，1，3，4，5，6，7，8，9，10 }；
可以看到这个数组如果要排序的话只需要排第一个和第二个就可以，就不需要继续判断后面的数据，因此可以将代码优化一下，可以设置一个变量，如果交换了就将变量修改，如果变量没有被修改就要跳出循环
代码优化：
#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赋值为0； flag = 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赋值为0； flag = 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); } }