广告
返回顶部
首页 > 资讯 > 后端开发 > Python >Python实现冒泡排序算法的示例解析
  • 665
分享到

Python实现冒泡排序算法的示例解析

Python冒泡排序算法Python冒泡排序 2022-11-11 01:11:23 665人浏览 薄情痞子

Python 官方文档:入门教程 => 点击学习

摘要

目录1. 算法描述2. 算法分析3. 动图展示4. 代码实现5. 算法升级6. 时间复杂度分析1. 算法描述 冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地遍历要排

1. 算法描述

冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2. 算法分析

1. 比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。

2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤,除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

那么我们需要进行n-1次冒泡过程,每次对应的比较次数如下图所示:

3. 动图展示

看明白了运行流程,我们再来看看动图实现:

4. 代码实现

我们对如下无序列表进行排序

实现代码:

import time

pop_list = [19, 14, 10, 4, 15, 26, 20, 96]
print("没排序前的列表为:", pop_list)
# 记录开始时间
start = time.time()
# 外层循环控制轮数
for i in range(len(pop_list) - 1):
    # 内层循环控制比较次数
    for j in range(len(pop_list) - i - 1):
        # 如果前一个数字比后一个数字大,就交换位置
        if pop_list[j] > pop_list[j + 1]:
            # python特有交换位置方式
            pop_list[j], pop_list[j + 1] = pop_list[j + 1], pop_list[j]

print("排序好的列表为:", pop_list)
# 记录结束时间
end = time.time()
print("算法总耗时:", end - start)

运行结果:

5. 算法升级

在循环中定义了一个变量count,如果第一次循环后count没有变化,就说明输入的是有序序列,这时我们直接return退出循环,这时候的时间复杂度为O(n)

实现代码:

import time

def bubble_sort(pop_list):
    for j in range(len(pop_list) - 1, 0, -1):
        count = 0
        for i in range(0, j):
            if pop_list[i] > pop_list[i + 1]:
                pop_list[i], pop_list[i + 1] = pop_list[i + 1], pop_list[i]
                count += 1
        if count == 0:
            return


pop_list = [19, 14, 10, 4, 15, 26, 20, 96]
print("没排序前的列表为:", pop_list)
# 记录开始时间
start = time.time()
bubble_sort(pop_list)
print("排序好的列表为:", pop_list)
# 记录结束时间
end = time.time()
print("算法总耗时:", end - start)

运行结果:

6. 时间复杂度分析

最优时间复杂度:O(n) (表示遍历一次发现没有任何可以交换的元素,排序结束。)

最坏时间复杂度:O(n^2)

稳定性:稳定

排序分析:待排数组中一共有8个数,第一轮排序时进行了7次比较,第二轮排序时进行了6比较,依次类推,最后一轮进行了1次比较。

数组元素总数为N时,则一共需要的比较次数为:(N-1)+ (N-2)+ (N-3)+ ...1=N*(N-1)/2

算法约做了N^2/2次比较。因为只有在前面的元素比后面的元素大时才交换数据,所以交换的次数少于比较的次数。如果数据是随机的,大概有一半数据需要交换,则交换的次数为N^2/4(不过在最坏情况下,即初始数据逆序时,每次比较都需要交换)。

交换和比较的操作次数都与 N^2 成正比,由于在大O表示法中,常数忽略不计,冒泡排序的时间复杂度为O(N^2)。

以上就是Python实现冒泡排序算法的示例解析的详细内容,更多关于Python冒泡排序算法的资料请关注编程网其它相关文章!

--结束END--

本文标题: Python实现冒泡排序算法的示例解析

本文链接: https://www.lsjlt.com/news/118561.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
  • Python实现冒泡排序算法的示例解析
    目录1. 算法描述2. 算法分析3. 动图展示4. 代码实现5. 算法升级6. 时间复杂度分析1. 算法描述 冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地遍历要排...
    99+
    2022-11-11
    Python冒泡排序算法 Python冒泡排序
  • python编程冒泡排序法实现动图排序示例解析
    目录先上个冒泡排序的效果图:动态排序的原理Python tkinter库Canvas操作动态排序的完整代码部分代码注释先上个冒泡排序的效果图:  是不是,有那么一点点像了...
    99+
    2022-11-12
    python编程 python冒泡排序动图实现
  • TypeScript实现十大排序算法之冒泡排序示例详解
    目录一. 冒泡排序的定义二. 冒泡排序的流程三. 冒泡排序的图解四. 冒泡排序的代码五. 冒泡排序的时间复杂度六. 冒泡排序的总结一. 冒泡排序的定义 冒泡排序是一种简单的排序方法...
    99+
    2023-02-23
    TypeScript冒泡排序算法 TypeScript 算法
  • C语言实现冒泡排序算法的示例详解
    目录1. 问题描述2. 问题分析3. 算法设计动图演示4. 程序设计设计一设计二结论5. 流程框架6. 代码实现7. 问题拓展1. 问题描述 对N个整数(数据由键盘输入)进行升序排列...
    99+
    2022-11-13
    C语言 冒泡排序算法 C语言 冒泡排序
  • Python冒泡排序算法怎么实现
    今天小编给大家分享一下Python冒泡排序算法怎么实现的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。1. 算法描述冒泡排序(...
    99+
    2023-07-02
  • java实现冒泡排序算法
    介绍冒泡排序是一种算法,比较相邻元素,如果他们处在错误的位置上,那么交换他们的位置。排序可以进行升序或者降序。原理从第一个元素开始,比较第一个元素和第二个元素,如果第一个元素大于第二个元素,那么交换他们的位置。比较 第二个元素和第三个元素的...
    99+
    2018-06-06
    java 冒泡排序 算法
  • go实现冒泡排序算法
    目录1、基本思想2、算法步骤第一轮开始排序: 第二轮开始排序: 第三轮开始排序: 第四轮开始排序: 3、算法实现1、基本思想 通过对待排序序列...
    99+
    2022-11-13
    go 冒泡排序
  • 图文详解Python冒泡排序算法
    本篇文章给大家带来了关于python的相关知识,其中主要介绍了关于冒泡排序的相关问题,包括了算法描述、分析、代码实现等等内容,下面一起来看一下,希望对大家有帮助。冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数...
    99+
    2022-06-14
    python
  • Java实现冒泡排序示例介绍
    何为冒泡排序 冒泡:就像气泡从水中冒出来一样 在冒泡排序中,最小数或最大数取决于您是按升序还是降序对数组进行排序,向上冒泡到数组的开头或结尾。 算法描述: 比较相邻的元素。如果第一个...
    99+
    2023-05-18
    Java冒泡排序 Java冒泡排序算法
  • 怎么使用Python实现冒泡排序算法
    这篇文章主要介绍“怎么使用Python实现冒泡排序算法”,在日常操作中,相信很多人在怎么使用Python实现冒泡排序算法问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”怎么使用Python实现冒泡排序算法”的疑...
    99+
    2023-07-02
  • C语言实现交换排序算法(冒泡,快速排序)的示例代码
    目录前言一、冒泡排序1.基本思想2.优化3.扩展二、快速排序1.基本思想2.优化3.代码前言 查找和排序是数据结构与算法中不可或缺的一环,是前辈们在算法道路上留下的重要且方便的一些技...
    99+
    2022-11-13
    C语言 交换排序算法 C语言 冒泡排序 C语言 快速排序
  • php怎么实现冒泡排序算法
    本文操作环境:windows10系统、php 7、thinkpad t480电脑。在给出具体的实现代码之前,我们先来简单介绍下冒泡排序。冒泡排序是一种比较简单的排序算法,它重复地走访过要排序的元素列,一次比较两个相邻的元素,如果他们的顺序(...
    99+
    2017-10-26
    php 冒泡排序
  • JS如何实现冒泡排序算法
    这篇文章主要介绍了JS如何实现冒泡排序算法,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。1. 算法步骤比较相邻的元素。如果第一个比第二个大,...
    99+
    2022-10-19
    js 冒泡排序
  • C#实现冒泡排序和插入排序算法
    1.选择排序(冒泡排序) 升序 用第一个元素跟其他元素比较,如果该元素比其他元素,则交换,保证该元素是最小的。然后再用第二个元素跟后面其他的比较,保证第二个元素是除第一个最小的。依次...
    99+
    2022-11-13
    C# 冒泡排序 插入排序
  • C语言中冒泡排序的示例分析
    这篇文章给大家分享的是有关C语言中冒泡排序的示例分析的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。(壹)冒泡排序1.1冒泡排序的设计冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排...
    99+
    2023-06-29
  • 详解Python排序算法的实现(冒泡,选择,插入,快速)
    目录1. 前言2. 冒泡排序算法2.1 摆擂台法2.2 相邻两个数字相比较3. 选择排序算法4. 插入排序5. 快速排序6. 总结1. 前言 所谓排序,就是把一个数据群体按个体数据的...
    99+
    2022-11-10
    Python 排序算法
  • C#怎么实现冒泡排序和插入排序算法
    这篇文章主要讲解了“C#怎么实现冒泡排序和插入排序算法”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C#怎么实现冒泡排序和插入排序算法”吧!1.选择排序(冒泡排序)升序用第一个元素跟其他元素...
    99+
    2023-06-30
  • Python冒泡排序注意要点实例详解
    冒泡排序注意三点: 1. 第一层循环可不用循环所有元素。 2.两层循环变量与第一层的循环变量相关联。 3.第二层循环,最终必须循环集合内所有元素。 示例代码一: 1.第一层循环,只循环n-1个元素。 2....
    99+
    2022-06-04
    详解 要点 实例
  • 基于Go语言实现冒泡排序算法
    目录冒泡排序图片演示普通的冒泡排序算法优化算法小结冒泡排序 冒泡排序是交换排序中最简单的一种算法。 算法思路: 遍历数组,相邻的两个元素进行比较,以升序为例,如果前面的元素大于后面的...
    99+
    2022-12-08
    Go语言实现冒泡排序算法 Go语言冒泡排序 Go 冒泡排序
  • 如何使用go实现冒泡排序算法
    这篇文章给大家分享的是有关如何使用go实现冒泡排序算法的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。1、基本思想通过对待排序序列从后向前,依次比较相邻元素的排序码,若发现逆序则交换,使排序码较小的元素从后部移向前...
    99+
    2023-06-29
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作