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

目录
  • 1. 算法描述
  • 2. 算法分析
  • 3. 动图展示
  • 4. 代码实现
  • 5. 算法升级
  • 6. 时间复杂度分析

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冒泡排序算法的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • python实现冒泡排序算法的两种方法

    什么是冒泡排序? 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法. 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成. 这个算法的名字由来是因为越大的元素会经由交换慢慢"浮"到数列的顶端,故名冒泡排序. 以上是百度词条对冒泡排序的官方解释. 但是我要说一下我的个人理解,我觉得冒泡排序的核心思想是:每次比较两个数,如果他们顺序错误(大于或者小于),那么就把

  • python算法与数据结构之冒泡排序实例详解

    一.冒泡排序介绍 冒泡排序(英语:Bubble Sort)是一种简单的排序算法.它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 二.冒泡排序原理 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对.这一步做完,最后的元素应该会是最大的数. 针对所有的

  • Python实现冒泡排序算法的完整实例

    冒泡排序:顾名思义就是(较小的值)像泡泡一样往上冒,(大的值)往下沉. 实现原理:依次将相邻两个数值进行比较,较小的数值移到左边,较大的数值移到右边,依次比较完第一轮后,最大的数值应该排在最右边.然后再继续重复的比较,直至无数值需要交换,此时排序完成. 例子解释: 无序列表arr = [7,6,5,3,9,2,8,1,4] 数列长度:len = 9 第一趟排序: i = 1; arr = [7,6,5,3,9,2,8,1,4] 7>6 =>[6,7,5,3,9,2,8,1,4]数值小的放左边,

  • 利用python实现冒泡排序算法实例代码

    利用python实现冒泡排序算法实例代码

    冒泡排序 冒泡排序(英语:Bubble Sort)是一种简单的排序算法.它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 冒泡排序算法的运作如下: 1.比较相邻的元素.如果第一个比第二个大(升序),就交换他们两个. 2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.这步做完后,最后的元素会是最大的数.

  • 详解python算法之冒泡排序

    详解python算法之冒泡排序

    python之冒泡排序 概念: 重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小.首字母从A到Z)错误就把他们交换过来.走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素已经排序完成 这个算法的名字由来是因为越大的元素会经由交换慢慢"浮"到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名"冒泡排序". 算法原理 冒泡排序算法的原理如下: 比较相邻的元素.如果第一个比第二个大,就交换他

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

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

    目录 1. 算法描述 2. 算法分析 3. 动图展示 4. 代码实现 5. 算法升级 6. 时间复杂度分析 1. 算法描述 冒泡排序(Bubble Sort)是一种简单的排序算法.它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端. 2. 算法分析 1. 比较相邻的元素.如果第一个比第二个大(升序),就交换他们两个. 2. 对每

  • Python数学建模学习模拟退火算法旅行商问题示例解析

    Python数学建模学习模拟退火算法旅行商问题示例解析

    目录 1.旅行商问题(Travelling salesman problem, TSP) 2.模拟退火算法求解旅行商问题 3. 程序说明 4.模拟退火算法求解旅行商问题 Python 程序 5.运行结果 1.旅行商问题(Travelling salesman problem, TSP) 旅行商问题是经典的组合优化问题,要求找到遍历所有城市且每个城市只访问一次的最短旅行路线,即对给定的正权完全图求其总权重最小的Hamilton回路:设有 n个城市和距离矩阵 D=[dij],其中dij表示城市i到城

  • python有序查找算法 二分法实例解析

    python有序查找算法 二分法实例解析

    这篇文章主要介绍了python有序查找算法 二分法实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 二分法是一种快速查找的方法,时间复杂度低,逻辑简单易懂,总的来说就是不断的除以2除以2... 但是需要注意: 待查找的序列区间单调有序 例如需要查找有序数组arr里面的某个关键字key的位置,那么首先确认arr的中位数或者中点center,下面分为三种情况: 假如arr[center]>key,说明key在arr中心左边范围: 假如arr[

  • python实现AdaBoost算法的示例

    代码 ''' 数据集:Mnist 训练集数量:60000(实际使用:10000) 测试集数量:10000(实际使用:1000) 层数:40 ------------------------------ 运行结果: 正确率:97% 运行时长:65m ''' import time import numpy as np def loadData(fileName): ''' 加载文件 :param fileName:要加载的文件路径 :return: 数据集和标签集 ''' # 存放数据及标记 da

  • Python实现贪心算法的示例

    Python实现贪心算法的示例

    今天一个研究生同学问我一个问题,问题如下: 超市有m个顾客要结账,每个顾客结账的时间为Ti( i取值从1到m).超市有n个结账出口,请问全部顾客怎么选择出口,可以最早完成全部顾客的结账,并用代码实现. 其实利用的就是贪心算法来解决这个问题,那么,什么是贪心算法?怎么用贪心算法解决这个问题?让我一一道来. 一.贪心算法简介 贪心算法是一种对某些求最优解问题的更简单.更迅速的设计技术.贪心算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,省去了为找

  • Python数据拟合实现最小二乘法示例解析

    Python数据拟合实现最小二乘法示例解析

    目录 线性拟合 高阶多项式 多自变量 指数函数 所谓最小二乘法,即通过对数据进行拟合,使得拟合值与样本值的方差最小. 线性拟合 这个表达式还是非常简单的. 对于有些情况,我们往往选取自然序列作为自变量,这个时候在求自变量的取值时可以用到一些初等数学的推论,对于 x ∈ [ m , n ] 的自然序列来说,有 #文件名core.py import numpy as np def leastSquare(x,y): if len(x)==2: #此时x为自然序列 sx = 0.5*(x[1]-x[0

  • C语言实现冒泡排序算法的示例详解

    C语言实现冒泡排序算法的示例详解

    目录 1. 问题描述 2. 问题分析 3. 算法设计 动图演示 4. 程序设计 设计一 设计二 结论 5. 流程框架 6. 代码实现 7. 问题拓展 1. 问题描述 对N个整数(数据由键盘输入)进行升序排列. 2. 问题分析 对于N个数因其类型相同,我们可利用 数组 进行存储. 冒泡排序是在 两个相邻元素之间进行比较交换的过程将一个无序表变成有序表. 冒泡排序的思想:首先,从表头开始往后扫描数组,在扫描过程中逐对比较相邻两个元素的大小. 若相邻两个元素中,前面的元素大于后面的元素,则将它们互换,

  • Python基础常用内建函数图文示例解析

    Python基础常用内建函数图文示例解析

    目录 abs() all() any() bin() bool() callable() abs() 返回一个数字的绝对值,它的参数可以是整数或者浮点数.举个例子: all() 参数为一个可迭代对象,如果该可迭代对象所有元素的真值都为True(或者可迭代对象为空),则返回True.它等价于: 举个例子: any() 和all()函数相对应,如可迭代对象所有元素中只要有一个元素真值为True,那么就返回True,如果这个可迭代对象是空的,则返回True.它等价于: 举个例子: bin() 将整数转

随机推荐