【算法基础】冒泡排序解析_3473: 【冒泡排序】数组元素的排序-程序员宅基地

技术标签： C/C++ 算法

作者：柒号华仔
个人主页：欢迎访问我的主页
个人信条：星光不问赶路人,岁月不负有心人。
个人方向：专注于5G领域，同时兼顾其他网络协议，编解码协议，C/C++，linux等，感兴趣的小伙伴可以关注我，一起交流。

1. 冒泡排序介绍

1.1 定义

在我们日常喝可乐雪碧的过程中，会看见无数气泡向水面移动，直到冒出水面，气泡比水轻会向前移动，我们称这种现象为冒泡。在我们数组排序中，每一个数组元素根据大小比对，小的元素不断向前移动，如同气泡在冒出一样，我们称这种排序方法为冒泡排序。

冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

1.2 基本原理

冒泡的原理如下：

比较相邻的两个元素，如果第一个比第二个大，就两者进行交换，如果第一个比第二个小，则保持顺序不变。
对数组中的每一对相邻元素依次做上面的比对和交换工作，这样最大的数就移到了最后。
一轮完毕后，继续重复步骤1和步骤2的操作，直到没有任何一对数字需要比较，最后便得到了依次排序好的数组。

下面的动图非常清晰的诠释了冒泡排序的过程：

在这里插入图片描述

1.3 时间复杂度

如果数组是正序排列的，一轮比对即可完成排序，此时时间复杂度为O(n)；

如果数组是完全倒序的，需要进行n-1轮排序，每一轮要进行n-i次比对。这里的i是已经比对的轮次数，也是数组末尾已经排序好元素个数。总的比对次数为：
(n-1)+(n-2)+…+1=n*(n-1)/2
此时时间复杂度为O( $n^2$ )；

因此，冒泡排序的平均时间复杂度为O( $n^2$ ) 。

1.5 优缺点

优点：冒泡排序算法简单，稳定可靠。

缺点：当数据量庞大并且乱序严重时，比较次数多，排序效率低。

2. 代码实现

2.1 代码设计

a. 实现冒泡排序需要设计两层循环，外循环为总的比对轮次，内循环为未排列好的元素；

b. 取出待比对元素array[i]，将其与array[i+1]进行比对，若前者比后者大，则进行交换，否则不进行交换。

c. 依次重复向后比对，直至这一轮比对交换完，再从头进行下一轮。

d. 总共进行size轮比对，排序完成

2.2 代码实现

#include <stdio.h>
  
void printArray(int array[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void bubble_sort(int array[],int size){
    int temp,i,j;
    for(i = 0;i < size-1;i++){
        for (j = 0;j < size-1-i;j++){
            if (array[j] > array[j+1]) {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}
int main(){
    int array[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};

    bubble_sort(array,sizeof(array)/sizeof(int));
    printArray(array,sizeof(array)/sizeof(int));

    return 0;
}

运行结果：
在这里插入图片描述

本文链接：https://blog.csdn.net/NoBack7/article/details/128903371

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

c# 调用c++ lib静态库_c#调用lib-程序员宅基地

文章浏览阅读2w次，点赞7次，收藏51次。四个步骤1.创建C++ Win32项目动态库dll 2.在Win32项目动态库中添加外部依赖项 lib头文件和lib库3.导出C接口4.c#调用c++动态库开始你的表演...①创建一个空白的解决方案，在解决方案中添加 Visual C++ , Win32 项目空白解决方案的创建：添加Visual C++ , Win32 项目这......_c#调用lib

deepin/ubuntu安装苹方字体-程序员宅基地

文章浏览阅读4.6k次。苹方字体是苹果系统上的黑体，挺好看的。注重颜值的网站都会使用，例如知乎：font-family: -apple-system, BlinkMacSystemFont, Helvetica Neue, PingFang SC, Microsoft YaHei, Source Han Sans SC, Noto Sans CJK SC, W..._ubuntu pingfang

html表单常见操作汇总_html表单的处理程序有那些-程序员宅基地

文章浏览阅读159次。表单表单概述表单标签表单域按钮控件demo表单标签表单标签基本语法结构<form action="处理数据程序的url地址“ method=”get|post“ name="表单名称”></form><!--method将表单中的数据传送给服务器处理，get方式直接显示在url地址中，数据可以被缓存，且长度有限制；而post方式数据隐藏传输，_html表单的处理程序有那些

PHP设置谷歌验证器（Google Authenticator）实现操作二步验证_php otp 验证器-程序员宅基地

文章浏览阅读1.2k次。使用说明:开启Google的登陆二步验证（即Google Authenticator服务）后用户登陆时需要输入额外由手机客户端生成的一次性密码。实现Google Authenticator功能需要服务器端和客户端的支持。服务器端负责密钥的生成、验证一次性密码是否正确。客户端记录密钥后生成一次性密码。下载谷歌验证类库文件放到项目合适位置(我这边放在项目Vender下面)https://github.com/PHPGangsta/GoogleAuthenticatorPHP代码示例://引入谷_php otp 验证器

【Python】matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距-程序员宅基地

文章浏览阅读4.3k次，点赞5次，收藏11次。matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距

docker — 容器存储_docker 保存容器-程序员宅基地

文章浏览阅读2.2k次。①Storage driver 处理各镜像层及容器层的处理细节，实现了多层数据的堆叠，为用户提供了多层数据合并后的统一视图②所有 Storage driver 都使用可堆叠图像层和写时复制（CoW）策略③docker info 命令可查看当系统上的 storage driver主要用于测试目的，不建议用于生成环境。_docker 保存容器

随便推点

网络拓扑结构_网络拓扑csdn-程序员宅基地

文章浏览阅读834次，点赞27次，收藏13次。网络拓扑结构是指计算机网络中各组件（如计算机、服务器、打印机、路由器、交换机等设备）及其连接线路在物理布局或逻辑构型上的排列形式。这种布局不仅描述了设备间的实际物理连接方式，也决定了数据在网络中流动的路径和方式。不同的网络拓扑结构影响着网络的性能、可靠性、可扩展性及管理维护的难易程度。_网络拓扑csdn

JS重写Date函数，兼容IOS系统_date.prototype 将所有 ios-程序员宅基地

文章浏览阅读1.8k次，点赞5次，收藏8次。IOS系统Date的坑要创建一个指定时间的new Date对象时，通常的做法是：new Date("2020-09-21 11:11:00")这行代码在 PC 端和安卓端都是正常的，而在 iOS 端则会提示 Invalid Date 无效日期。在IOS年月日中间的横岗许换成斜杠，也就是new Date("2020/09/21 11:11:00")通常为了兼容IOS的这个坑，需要做一些额外的特殊处理，笔者在开发的时候经常会忘了兼容IOS系统。所以就想试着重写Date函数，一劳永逸，避免每次ne_date.prototype 将所有 ios