百度360必应搜狗淘宝本站头条
python类型转换python串口编程python计时python异常python进度条
当前位置：网站首页 > 技术资源 > 正文

python|冒泡排序及优化（python冒泡法排序代码）

off999 2024-10-27 11:51 30 浏览 0 评论

一、冒泡排序简介

冒泡排序(Bubble Sort)是一种常见的排序算法，相对来说比较简单。

冒泡排序重复地走访需要排序的元素列表，依次比较两个相邻的元素，如果顺序(如从大到小或从小到大)错误就交换它们的位置。重复地进行直到没有相邻的元素需要交换，则元素列表排序完成。

在冒泡排序中，值最大(或最小)的元素会通过交换慢慢“浮”到元素列表的“顶端”。就像“冒泡”一样，所以被称为冒泡排序。

二、冒泡排序原理

冒泡排序的原理如下：

1. 比较相邻的两个元素。如果第一个比第二个大则交换他们的位置(升序排列，降序则反过来)。

2. 从列表的开始一直到结尾，依次对每一对相邻元素都进行比较。这样，值最大的元素就通过交换“冒泡”到了列表的结尾，完成第一轮“冒泡”。

3. 重复上一步，继续从列表开头依次对相邻元素进行比较。已经“冒泡”出来的元素不用比较(一直比较到结尾也可以，已经“冒泡”到后面的元素即使比较也不需要交换，不比较可以减少步骤)。

4. 继续从列表开始进行比较，每轮比较会有一个元素“冒泡”成功。每轮需要比较的元素个数会递减，一直到只剩一个元素没有“冒泡”时(没有任何一对元素需要比较)，则列表排序完成。

以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 进行升序排列为例。列表的初始状态如下图。

要进行升序排列，则大的元素要依次“冒泡”到列表的结尾。

1. 从列表的开头，比较相邻的两个元素，如果第一个值比第二个值大则交换。10小于17，不需要交换。

2. 向列表的结尾方向“走访”，比较第二组相邻的元素(第二个和第三个)，如果不是从小到大则交换。17小于50，不需要交换。

3. 继续“走访”，比较第三组相邻的元素，如果不是从小到大则交换。50大于7，所以需要交换。

4. 对顺序错误的元素进行位置交换。交换50和7的位置。

5. 一直“走访”到结尾，第一轮“冒泡”结束后，值最大的元素“冒泡”到了列表的结尾。50“冒泡”到了列表结尾。

在下一轮“冒泡”中，不需要再将50进行比较，需要比较的元素个数减1。

6. 从列表开头，重复下一轮“冒泡”，每进行一轮“冒泡”，需要比较的元素都少一个，直到没有元素对需要比较时，整个列表排序完成。排序结果如下图。

三、Python实现冒泡排序

四、冒泡排序的时间复杂度和稳定性

1. 时间复杂度

在没有特殊说明时，一般都是计算最坏时间复杂度。

在冒泡排序中，最坏的情况是元素列表的初始状态是完全逆序排列的，需要进行 n-1 轮“冒泡”，每一轮“冒泡”需要进行 n-i 次比较和交换操作。i 的平均值为 n/2 ，时间复杂度为 T(n)=n(n-1)/2 ，再乘每次操作的步骤数(常数，不影响大O记法)，所以冒泡排序的时间复杂度为 O(n^2) 。

2. 稳定性
排序算法的稳定性指，当元素列表中有相等的元素时，相等元素的相对次序是否固定不变，如果相对次序固定不变，则排序算法是稳定的，反之。
在冒泡排序中，每次比较两个元素，当元素的大小顺序错误时才会进行交换，如果元素列表中有两个相等的元素，它们最终肯定会相邻在一起，但对它们比较时不会进行交换，相对次序是保持不变的。所以冒泡排序是一种稳定的排序算法。

冒泡排序优化：将时间复杂度降为O(n)



相关推荐

阿里云国际站ECS:阿里云ECS如何提高网站的访问速度?

TG：@yunlaoda360引言：速度即体验，速度即业务在当今数字化的世界中，网站的访问速度已成为决定用户体验、用户留存乃至业务转化率的关键因素。页面加载每延迟一秒，都可能导致用户流失和收入损失。对...

高流量大并发Linux TCP性能调优_linux 高并发网络编程

其实主要是手里面的跑openvpn服务器。因为并没有明文禁p2p（哎……想想那么多流量好像不跑点p2p也跑不完），所以造成有的时候如果有比较多人跑BT的话，会造成VPN速度急剧下降。本文所面对的情况为...

性能测试100集(12)性能指标资源使用率

在性能测试中，资源使用率是评估系统硬件效率的关键指标，主要包括以下四类：#性能测试##性能压测策略##软件测试#1.CPU使用率定义：CPU处理任务的时间占比，计算公式为1-空闲时间/总...

Linux 服务器常见的性能调优_linux高性能服务端编程

一、Linux服务器性能调优第一步——先搞懂“看什么”很多人刚接触Linux性能调优时，总想着直接改配置，其实第一步该是“看清楚问题”。就像医生看病要先听诊，调优前得先知道服务器“哪里...

Nginx性能优化实战:手把手教你提升10倍性能!

关注△mikechen△，十余年BAT架构经验倾囊相授！Nginx是大型架构而核心，下面我重点详解Nginx性能@mikechen文章来源：mikechen.cc1.worker_processe...

高并发场景下，Spring Cloud Gateway如何抗住百万QPS?

关注△mikechen△，十余年BAT架构经验倾囊相授！大家好，我是mikechen。高并发场景下网关作为流量的入口非常重要，下面我重点详解SpringCloudGateway如何抗住百万性能@m...

Kubernetes 高并发处理实战(可落地案例 + 源码)

目标场景：对外提供HTTPAPI的微服务在短时间内收到大量请求（例如每秒数千至数万RPS），要求系统可弹性扩容、限流降级、缓存减压、稳定运行并能自动恢复。总体思路（多层防护）：边缘层：云LB...

高并发场景下，Nginx如何扛住千万级请求?

Nginx是大型架构的必备中间件，下面我重点详解Nginx如何实现高并发@mikechen文章来源：mikechen.cc事件驱动模型Nginx采用事件驱动模型，这是Nginx高并发性能的基石。传统...

Spring Boot+Vue全栈开发实战，中文版高清PDF资源

SpringBoot+Vue全栈开发实战，中文高清PDF资源，需要的可以私我：）SpringBoot致力于简化开发配置并为企业级开发提供一系列非业务性功能，而Vue则采用数据驱动视图的方式将程序...

Docker-基础操作_docker基础实战教程二

一、镜像1、从仓库获取镜像搜索镜像：dockersearchimage_name搜索结果过滤：是否官方:dockersearch--filter="is-offical=true...

你有空吗?跟我一起搭个服务器好不好?

来人人都是产品经理【起点学院】，BAT实战派产品总监手把手系统带你学产品、学运营。昨天闲的没事的时候，随手翻了翻写过的文章，发现一个很严重的问题。就是大多数时间我都在滔滔不绝的讲理论，却很少有涉及动手...

部署你自己的 SaaS_saas如何部署

部署你自己的VPNOpenVPN——功能齐全的开源VPN解决方案。（DigitalOcean教程）dockovpn.io—无状态OpenVPNdockerized服务器，不需要持久存储。...

Docker Compose_dockercompose安装

DockerCompose概述DockerCompose是一个用来定义和管理多容器应用的工具，通过一个docker-compose.yml文件，用YAML格式描述服务、网络、卷等内容，...

京东T7架构师推出的电子版SpringBoot，从构建小系统到架构大系统

前言：Java的各种开发框架发展了很多年，影响了一代又一代的程序员，现在无论是程序员，还是架构师，使用这些开发框架都面临着两方面的挑战。一方面是要快速开发出系统，这就要求使用的开发框架尽量简单，无论...

Kubernetes (k8s) 入门学习指南_k8s kubeproxy

Kubernetes(k8s)入门学习指南一、什么是Kubernetes？为什么需要它？Kubernetes(k8s)是一个开源的容器编排系统，用于自动化部署、扩展和管理容器化应用程序。它...

取消回复欢迎 你 发表评论:

一周热门
最近发表
标签列表
Copyright Your WebSite.Some Rights Reserved.