AI 助理
备案控制台
开发者社区 人工智能 文章 正文

进阶C语言：冒泡排序

2023-06-16 697
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 初阶C语言--冒泡排序、qsort函数的使用、使用冒泡排序的思想实现类似于qsort的函数。
冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

紫蓝色几何渐变科技互联网微信公众号封面 (1).gif

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>voidbubble_sort(intarr[], intsz)
{
//设置冒泡排序的趟数inti=0;
for (i=0; i<sz-1; i++)
    {
//一趟冒泡排序的次数intj=0;
for (j=0; j<sz-1-i; j++)
        {
if (arr[j] >arr[j+1])  //如果前面的一个数字大于后面的数字就交换            {
inttmp=arr[j];
arr[j] =arr[j+1];
arr[j+1] =tmp;
            }
        }
    }
}
voidprint_arr(intarr[], intsz)
{
inti=0;
for (i=0; i<sz; i++)
    {
printf("%d ", arr[i]);
    }
printf("\n");
}
intmain()
{
intarr[] = { 5,4,8,9,7,6,3,2,1,10 };
//使用冒泡排序的算法，来排序intsz=sizeof(arr) /sizeof(arr[0]);
printf("排序前:>");
print_arr(arr, sz);
bubble_sort(arr, sz);
//打印printf("排序后:>");
print_arr(arr, sz);
return0;
}

这样写就可以实现冒泡排序，但是有一点，上面写的代码只能排序整型数组，如果要排序字符、结构体...就不能适用了，因此我们来学习一个新的排序方式

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是比较函数，用于比较两个元素的大小。 
voidqsort( void*base,   //指向要排序的数组size_tnum,   //数组中元素的个数size_tsize,  //数组中每个元素的大小int (*compar)(constvoid*, constvoid*));
//指向一个函数，这个函数可以比较两个元素的大小
这个函数的第一个参数是一个void* 的指针，因为void*的指针可以存放任何类型的指针，这样有助于排序任何类型的数据，第二个参数是一个无符号整形的数据，表示元素个数，第三个参数也是一个无符号整形的数据，表示元素大小，第四个参数是一个函数指针，这个函数指针需要我们自己设计，因为这个qsort函数可以排序任何类型的数据，因此你需要排序什么类型的数据就可以自己设置什么样的函数

可以使用C语言工具来查一下这个函数：

如果听到这里还没有挺明白的话，也不要着急，下面给大家举个例子来用一下qsort函数：

使用qsort来对整型数组进行排序

代码演示：

#include <stdio.h>#include <stdlib.h>voidprint_arr(intarr[], intsz)
{
inti=0;
for (i=0; i<sz; i++)
    {
printf("%d ", arr[i]);
    }
printf("\n");
}
intcmp_int(constvoid*p1, constvoid*p2)  //设置比较两个元素大小的函数{
return*(int*)p1-*(int*)p2;
//由于比较的是两个整形的数组，因此需要对其进行强制类型转化为（int*）的指针，然后解引用找到这个数//如果返回值大于0证明前面的数p1大于后面的数p2，需要交换//如果返回值小于0证明前面的数p1小于后面的数p2，不需要交换//如果返回值等于0证明两个数相等，也不需要交换}
intmain()
{
intarr[] = { 5,8,9,6,3,2,7,1,4,10 };
intsz=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);
return0;
}

注意：cmp_  函数需要自己设置，需要什么类型就需要强制类型转化为什么类型 对结构体进行排序

对于结构体也可以进行排序，只不过需要告诉cmp_函数需要排结构体中的什么，比如：名字、年龄、时间......

关于结构体的创建，和对结构体成员的访问要理解 访问结构体变量使用.操作符 访问结构体指针使用->操作符 比较两个字符串的大小使用的是strcmp

对年龄进行排序

代码演示：

#include <stdio.h>#include <stdlib.h>structStr{
charname[20];
intage;
};
intcmp_str_by_age(constvoid*p1, constvoid*p2)
{
//这里使用结构体指针来访问结构体成员return ((structStr*)p1)->age- ((structStr*)p2)->age;
}
voidtest1()
{
structStrs[] = { {"zhangsan",55},{"lisi",45},{"wangwu",25} };
intsz=sizeof(s) /sizeof(s[0]);
printf("年龄排序：\n");
printf("排序前:\n");
inti=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);
    }
}
intmain()
{
//对年龄进行排序test1();
return0;
}
对名字进行排序 对名字排序就是对首字母的ASCII码值进行排序，如果首字母一样，就使用第二个字母进行排序，依次类推

代码演示：

#include <stdio.h>#include <stdlib.h>#include <string.h>structStr{
charname[20];
intage;
};
intcmp_str_by_name(constvoid*p1, constvoid*p2)
{
returnstrcmp(((structStr*)p1)->name, ((structStr*)p2)->name);
}
voidtest2()
{
structStrs[] = { {"zhangsan",55},{"lisi",45},{"wangwu",25} };
intsz=sizeof(s) /sizeof(s[0]);
printf("名字排序：\n");
printf("排序前:\n");
inti=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);
    }
}
intmain()
{
//对年龄进行排序//test1();//对名字进行排序test2();
return0;
}

因此qsort的排序功能是非常广泛的，它的底层逻辑是快速排序的算法，那我们可以用冒泡排序的算法也实现一个类似与qsort的函数

3.冒泡排序思想实现qsort

上面写的冒泡排序只可以实现整数数组的比较，功能单一，我们可以使用冒泡排序的思想实现类似于qsort的一种排序的方法，qsort的底层逻辑是快速排序。

基本框架和qsort的框架一样，只是需要类似于qsort函数的代码来实现

代码演示：

#include <stdio.h>//实现比较大小的函数intcmp_int(constvoid*p1, constvoid*p2)
{
return*(int*)p1-*(int*)p2;
}
//打印函数voidprint_arr(intarr[], intsz)
{
inti=0;
for (i=0; i<sz; i++)
    {
printf("%d ", arr[i]);
    }
printf("\n");
}
voidtest1()
{
intarr[] = { 8,9,6,5,2,3,1,4,7,10 };
intsz=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);
}
intmain()
{
test1();
return0;
}

3.1冒泡排序函数实现

使用冒泡排序逻辑实现类似于qsort函数的排序方法，因此，冒泡排序的逻辑就可以使用，因此设置冒泡排序的趟数和一趟排序的次数都是不变的，只是要注意在什么条件下需要交换，怎么样交换，交换什么

代码演示：

//这时的函数参数就可以参考qsort函数的函数参数//void qsort( void* base,   //指向要排序的数组//size_t num,   //数组中元素的个数//size_t size,  //数组中每个元素的大小//int (*compar)(const void*, const void*));//指向一个函数，这个函数可以比较两个元素的大小voidbubble_sort(void*base, size_tnum, size_twidth, int(*cmp_int)(constvoid*e1, constvoid*e2))
{
size_ti=0;  //这里的参数类型要与函数参数类型一致都为无符号整型//设置冒泡排序的趟数for (i=0; i<num; i++)
    {
size_tj=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*的指针，所以还得另寻出路！ 
//代码1if (cmp_int(base+j  , base+j+1 )>0)
{
}
//代码2if (cmp_int((int*)base+j  , (int*)base+j+1 )>0)
{
}
//代码1和代码2都是不可行的操作
我们都知道char*的指针对其进行加减整数只能跳过一个字节，那么如果将参数类型转化为char*的类型然后再乘上宽度（数组中一个元素的大小）是不是就可以达到转化任意类型的效果了,假设要排序整形，一个整形的大小是4个字节，因此用char*的指针*4就表明每一次要跳过4个字节的空间也就是一个整形

代码演示：

intcmp_int(constvoid*p1, constvoid*p2)
{
return*(int*)p1-*(int*)p2; //通过地址找到数据进行比较}
if (cmp_int((char*)base+j*width , (char*)base+ (j+1) *width)>0)
{
//如果前一位数据大于后一位数据就满足条件//交换//交换函数：}

3.2交换函数的实现

如果前一个数据大于后一个数据就实现交换，那该怎么交换呢？ 可以采用一个字节一个字节的交换方式，设置循环，使用宽度来设置交换的次数，4个字节就交换四次

因此再给交换函数传参时需要传两个起始地址和宽度

代码演示：

voidSwp(char*buf1, char*buf2, intwidth)
{
inti=0;
for (i=0; i<width; i++)
    {
chartmp=*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>intcmp_int(constvoid*p1, constvoid*p2)
{
return*(int*)p1-*(int*)p2;
}
voidprint_arr(intarr[], intsz)
{
inti=0;
for (i=0; i<sz; i++)
    {
printf("%d ", arr[i]);
    }
printf("\n");
}
voidSwp(char*buf1, char*buf2, intwidth)
{
inti=0;
for (i=0; i<width; i++)
    {
chartmp=*buf1;
*buf1=*buf2;
*buf2=tmp;
buf1++;
buf2++;
    }
}
voidbubble_sort(void*base, size_tnum, size_twidth, int(*cmp_int)(constvoid*e1, constvoid*e2))
{
size_ti=0;
for (i=0; i<num; i++)
    {
size_tj=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);
            }
        }
    }
}
voidtest1()
{
intarr[] = { 8,9,6,5,2,3,1,4,7,10 };
intsz=sizeof(arr) /sizeof(arr[0]);
printf("排序前：");
print_arr(arr, sz);
bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
printf("排序后：");
print_arr(arr, sz);
}
intmain()
{
test1();
return0;
}

但是如果有一个数组 int arr[] = { 2，1，3，4，5，6，7，8，9，10 }； 可以看到这个数组如果要排序的话只需要排第一个和第二个就可以，就不需要继续判断后面的数据，因此可以将代码优化一下，可以设置一个变量，如果交换了就将变量修改，如果变量没有被修改就要跳出循环

代码优化：

#include <stdio.h>//比较两个数据的大小intcmp_int(constvoid*p1, constvoid*p2)
{
return*(int*)p1-*(int*)p2;
}
//打印函数voidprint_arr(intarr[], intsz)
{
inti=0;
for (i=0; i<sz; i++)
    {
printf("%d ", arr[i]);
    }
printf("\n");
}
//交换函数voidSwp(char*buf1, char*buf2, intwidth)
{
inti=0;
for (i=0; i<width; i++)
    {
chartmp=*buf1;
*buf1=*buf2;
*buf2=tmp;
buf1++;
buf2++;
    }
}
//使用冒泡排序的思想来实现类似于qsort的排序算法voidbubble_sort(void*base, size_tnum, size_twidth, int(*cmp_int)(constvoid*e1, constvoid*e2))
{
size_ti=0;
//假设数组有序intflag=1;
for (i=0; i<num; i++)
    {
size_tj=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;
        }
    }
}
voidtest1()
{
intarr[] = { 8,9,6,5,2,3,1,4,7,10 };
intsz=sizeof(arr) /sizeof(arr[0]);
printf("排序前：");
print_arr(arr, sz);
bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
printf("排序后：");
print_arr(arr, sz);
}
intmain()
{
//排序整形数组test1();
return0;
}
使用冒泡排序对结构体进行排序 
#include <stdio.h>#include <string.h>//比较两个数据的大小intcmp_int(constvoid*p1, constvoid*p2)
{
return*(int*)p1-*(int*)p2;
}
//打印函数voidprint_arr(intarr[], intsz)
{
inti=0;
for (i=0; i<sz; i++)
    {
printf("%d ", arr[i]);
    }
printf("\n");
}
//交换函数voidSwp(char*buf1, char*buf2, intwidth)
{
inti=0;
for (i=0; i<width; i++)
    {
chartmp=*buf1;
*buf1=*buf2;
*buf2=tmp;
buf1++;
buf2++;
    }
}
//使用冒泡排序的思想来实现类似于qsort的排序算法voidbubble_sort(void*base, size_tnum, size_twidth, int(*cmp_int)(constvoid*e1, constvoid*e2))
{
size_ti=0;
//假设数组有序intflag=1;
for (i=0; i<num; i++)
    {
size_tj=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;
        }
    }
}
structStr{
charname[20];
intage;
};
//比较年龄intcmp_str_by_age(constvoid*p1, constvoid*p2)
{
return ((structStr*)p1)->age- ((structStr*)p2)->age;
//这里使用->来访问结构体指针}
voidtest2()
{
//结构体初始化structStrs[] = { {"zhangsan",55},{"lisi",25},{"wangwu",35} };
intsz=sizeof(s) /sizeof(s[0]);
bubble_sort(s, sz, sizeof(s[0]), cmp_str_by_age);
}
intcmp_str_by_name(constvoid*p1, constvoid*p2)
{
returnstrcmp(((structStr*)p1)->name, ((structStr*)p2)->name);
}
voidtest3()
{
structStrs[] = { {"zhangsan",55},{"lisi",25},{"wangwu",35} };
intsz=sizeof(s) /sizeof(s[0]);
bubble_sort(s, sz, sizeof(s[0]), cmp_str_by_name);
}
intmain()
{
//对年龄进行排序test2();
//对名字进行排序test3();
return0;
}
如果要对年龄进行排序要将对名字排序的代码注释掉，要不然会混在一起

这里并没有将它们打印出来，只是在调试的监视窗口中观察到的 如果要打印出来可以在冒泡排序的函数下面加上循环打印结构体 
voidtest3()
{
structStrs[] = { {"zhangsan",55},{"lisi",25},{"wangwu",35} };
intsz=sizeof(s) /sizeof(s[0]);
bubble_sort(s, sz, sizeof(s[0]), cmp_str_by_name);
inti=0;
for (i=0; i<sz; i++)
    {
printf("姓名：%s\n", s[i].name);
    }
}
voidtest2()
{
structStrs[] = { {"zhangsan",55},{"lisi",25},{"wangwu",35} };
intsz=sizeof(s) /sizeof(s[0]);
bubble_sort(s, sz, sizeof(s[0]), cmp_str_by_age);
inti=0;
for (i=0; i<sz; i++)
    {
printf("年龄：%d\n", s[i].age);
    }
}

文章标签：
C语言
搜索推荐
算法
关键词：
C语言冒泡排序
C语言进阶
stackY
目录
相关文章
写代码的大学生
|
7月前
|
C语言
指针进阶（C语言终）
指针进阶（C语言终）
写代码的大学生
71 4
可惜已不在
|
3月前
|
算法 搜索推荐 C语言
【C语言】冒泡排序+优化版
【C语言】冒泡排序+优化版
可惜已不在
35 1
ephemerals__
|
3月前
|
C语言
【c语言】qsort函数及泛型冒泡排序的模拟实现
本文介绍了C语言中的`qsort`函数及其背后的回调函数概念。`qsort`函数用于对任意类型的数据进行排序，其核心在于通过函数指针调用用户自定义的比较函数。文章还详细讲解了如何实现一个泛型冒泡排序，包括比较函数、交换函数和排序函数的编写，并展示了完整的代码示例。最后，通过实际运行验证了排序的正确性，展示了泛型编程的优势。
ephemerals__
39 0
笨笨小乌龟
|
6月前
|
搜索推荐 C语言
C语言冒泡排序（附源码和动态图）
冒泡排序是一种简单的排序算法，其基本思想是通过重复遍历待排序的数列，比较每对相邻元素的值，如果它们的顺序错误（即满足一定的排序条件，如从小到大排序时前一个元素大于后一个元素），就交换它们的位置。这个过程就像水底的气泡一样逐渐向上冒，因此得名“冒泡排序”。
笨笨小乌龟
113 1
就学呗
|
7月前
|
数据库 C语言
C语言进阶 文件操作知识（上）
C语言进阶 文件操作知识（上）
就学呗
46 3
就学呗
|
7月前
|
存储 C语言
C语言进阶 文件操作知识(下)
C语言进阶 文件操作知识(下)
就学呗
46 2
加油，旭杏
|
7月前
|
存储 编译器 数据库
【再识C进阶5(上)】详细介绍C语言文件操作——文件是用于存储数据
【再识C进阶5(上)】详细介绍C语言文件操作——文件是用于存储数据
加油，旭杏
61 2
GR鲸鱼
|
8月前
|
编译器 C语言 C++
从C语言到C++_21(模板进阶+array)+相关笔试题（下）
从C语言到C++_21(模板进阶+array)+相关笔试题
GR鲸鱼
57 2
碳基肥宅
|
8月前
|
C语言
万字详解：C语言三子棋进阶 + N子棋递归动态判断输赢（二）
我们可以通过创建并定义符号常量NUMBER，来作为判断是否胜利的标准。如三子棋中，令NUMBER为3，则这八个方向中有任意一个方向达成3子连珠，则连珠的这个棋子所代表的玩家获胜。
碳基肥宅
84 1
碳基肥宅
|
8月前
|
算法 C语言 C++
万字详解：C语言三子棋进阶 + N子棋递归动态判断输赢（一）
三子棋游戏设计的核心是对二维数组的把握和运用。
碳基肥宅
102 1