python 基础知识点(蓝桥杯python科目个人复习计划20)

今日复习内容:基础算法中的选择排序/插入排序/快速排序/归并排序/桶排序

一.选择排序

1.算法步骤

  • 从左往右找到最小的元素,放在起始位置
  • 重复上述步骤,依次找到第二,第三小的元素

2.具体描述

  • 给定一个长度为n的列表,算法循环n-1次后可以得到有序序列
  • 第0次循环,从[0,n-1]中找出最小值a[x],与a[0]交换 
  • 第1次循环,从[1,n-1]中找出最小值a[x],与a[1]交换 
  • 第2次循环,从[2,n-1]中找出最小值a[x],与a[2]交换 
  • 第i次循环,从[i,n-1]中找出最小值a[x],与a[i]交换 
  • 第n-2次循环,从[n-2,n-1]中找出最小值a[x],与a[n-2]交换 
  • 时间复杂度O(n^2),空间复杂度O(1),稳定

上一篇的那个题也可以用这种方法做,具体如下:

题目描述:

在一个神秘的岛屿上,有一支探险队发现了一批宝藏,这批宝藏是以整数数组的形式存在的,每个宝藏上都标有一个数字,代表了其珍贵程度。然而,由于某种神秘力量,这批宝藏的顺序被打乱了,探险队需要将宝藏按照其珍贵程度进行排序,以便更好地保护和研究它们。作为探险队的一员,肖恩需要设计合适的排序算法来将宝藏按照其珍贵程度从小到大进行排序,请你帮帮他。 

输入描述:

输入第一行包括一个数字n,表示宝藏一共有n个;

输入第二行包括n个数字,第i个数字 a[i]表示第i个宝藏的珍贵程度;

数据保证1 < n < 1000,1 < a[i] < 10^6

输出描述:

输出n个数字,为对宝藏按照其珍贵程度从小到大进行排序的结果

以下是参考答案

n = int(input())
a = list(map(int,input().split()))
# 循环n-1次
for i in range(0,n-1):
    min_value = a[i]
    min_idx = i
    for j in range(i,n):
        if a[j] < min_value:
            min_value = a[j]
            min_idx = j
    a[i],a[min_idx] = a[min_idx],a[i]
print(' '.join(map(str,a)))

运行结果:

二.插入排序

1.算法步骤

  • 第一个元素看作已排序,从左往右遍历每一个元素
  • 在已排序元素中从后往前扫描,如果当前元素大于新元素,则当前元素向后移一位
  • 重复第二步,直到找到小于等于新元素为止 

2.具体描述

  • 将上述步骤看作摸牌,每次摸一张牌从后往前判断是否可以插入
  • 对于第i张牌a[i], [0,i-1]中的数都是已经排序好的
  • 从后往前逐个判断a[j]是否大于a[i],
  • 如果a[j]大于a[i],则a[j]向后移一个位置
  • 如果a[j]小于等于a[i],则在a[j+1]的位置放置a[i]
  • 时间复杂度O(n^2),空间复杂度O(1),不稳定

    仍然是那个题,题目请看上面,过程如下:

n = int(input())
a = list(map(int,input().split()))
# 循环n-1次
for i in range(1,n):
    value = a[i]
    insert_idx = 0
    for j in range(i-1,-1,-1):
        if a[j] > value:
            a[j+1] = a[j]
        else:
            insert_idx = j + 1
            break
    a[insert_idx] = value
print(' '.join(map(str,a)))

运行结果:

 

三.快速排序

1.算法步骤

  • 找一个基准值x
  • 把列表分为三部分:小于等于x的,x,大于x的
  • 左半部分和右半部分递归使用该策略 

2.化抽象为具体

例:a = [3,5,8,1,2,9,4,7,6] ,left = 0,right = 8

  • 设置基准值下标为left
  • 存放小于等于基准值下标为idx = left + 1
  • 从left + 1 到right中的每一个元素:

       如果a[i]小于等于基准值,则将a[i]和a[idx]互换,idx +=1

  • 最终结果:[1,2] [5] [5,8,9,7,6]
  • 左侧和右侧重复上述操作
  • 时间复杂度:O(nlog(n)),空间复杂度:O(nlog(n))

现在我把它转换成代码:

# 列表a,左端点为left,右端点为right
# [left,right]
def partition(a,left,right):
    # 找一个基准值,将列表分成三部分
    # 标准中为a[left]
    idx = left + 1
    for i in range(left + 1,right + 1):
        # 如果元素小于基准值,就放到前面去
        if a[i] <= a[left]:
            a[i],a[idx] = a[idx],a[i]
            idx += 1
    # 把前半部分最后一个值和基准值交换
    a[left],a[idx- 1] = a[idx - 1],a[left]
    return idx - 1


# 将a[left,right]进行排序
def quicksort(a,left,right):
    # 我们把它打印出来
    if left < right:
        mid = partition(a,left,right)
        # 此时a被分成了三部分:a[left,mid - 1],a[mid],a[mid + 1,right]
        quicksort(a,left,mid - 1)
        quicksort(a,mid + 1,right)


n = int(input())
a = list(map(int,input().split()))
quicksort(a,0,n - 1)
print(' '.join(map(str,a)))

运行结果:

(这也是“宝藏排序”那个题的第四种做法,代码自己编的,仅供参考) 

四.归并排序

  • 首先考虑一个问题,两个有序列表怎样合并成一个列表?
  • 比如:a = [1,2,3],b = [4,5,6]
  • 方法如下: 

       1.构建一个空列表result[]

       2.当a非空且b非空

          比较a[0]和b[0]

          result 添加较小的那个元素,同时该元素从原始数组中弹出

      3.如果a非空但b是空集,则将a添加到result末尾

      4.如果b非空但a是空集,则将b添加到result末尾


现在我把它编成代码:

a = [1,2,3]
b = [4,5,6]
def Merge(a,b):
    result = []
    while len(a) != 0 and len(b) != 0:
        if a[0] < b[0]:
            result.append(a.pop(0))
        else:
            result.append(b.pop(0))
    result.extend(a)
    result.extend(b)
    return result
print(Merge(a,b))

运行结果:

 

1.算法步骤

  • 先把数组分成两部分 
  • 每部分递归处理变成有序
  • 将两个有序列表合并起来

    “宝藏排序”那个题的第五种做法:

def Merge(a,b):
    result = []
    while len(a) != 0 and len(b) != 0:
        if a[0] < b[0]:
            result.append(a.pop(0))
        else:
            result.append(b.pop(0))
    result.extend(a)
    result.extend(b)
    return result


def Mergesort(a):
    if len(a) < 2:
        return a
    mid = len(a) // 2
    left = Mergesort(a[:mid])
    right = Mergesort(a[mid:])
    return Merge(left,right)
n = int(input())
a = list(map(int,input().split()))
a = Mergesort(a)
print(' '.join(map(str,Mergesort(a))))

运行结果:

五.桶排序

  • 利用函数映射关系,将输入数据分到有限的桶里,然后每个桶分别排序
  • 初始化K个桶
  • 遍历数据,将数据放入对应桶中
  • 每个桶单独排序
  • 各个桶是数据拼接起来 

“宝藏排序” 的第五种方法:


def Bucket_Sort(a,bucketcount):
    minvalue,maxvalue = min(a),max(a)
    # 桶大小,每个桶的元素范围
    bucketsize = (maxvalue - minvalue + 1) // bucketcount
    res = [[] for _ in range(bucketcount + 1)]
    # 把所有元素放到对应桶中
    for x in a:
        # 把元素放到第几个桶中
        idx = (x - minvalue) // bucketsize
        res[idx].append(x)
    print(res)
        # 每个桶单独排序
    ans = []
    for res_x in res:
        res_x.sort()
        ans += res_x
    return ans
n = int(input())
a = list(map(int,input().split()))
a = Bucket_Sort(a,min(1000,n))
print(' '.join(map(str,a)))

运行结果:

 

OK,今天就写到这里,我有点头晕了,这几种方法全部理解透彻有点 费命。

下次继续!

(若有错误,欢迎各位指出)

 

 

 

 

 

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/310535.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

[VisualStudioCode]_[VSCODE]_[C/C++开发环境配置-问题解决和补充]

场景 在使用VSCode配置C的开发环境时《VisualStudioCode_C/C开发环境配置[1]》&#xff0c;编译时会发现找不到标准库的std::mutex和std::thread的声明&#xff0c;而这两个的头文件已经引入&#xff0c;什么情况&#xff1f; 无论如何MinGW都是Windows上验证开发C特性比较新的…

Python从入门到网络爬虫(控制语句详解)

前言 做任何事情都要遵循一定的原则。例如&#xff0c;到图书馆去借书&#xff0c;就需要有借书证&#xff0c;并且借书证不能过期&#xff0c;这两个条件缺一不可。程序设计亦是如此&#xff0c;需要使用流程控制实现与用户的交流&#xff0c;并根据用户需求决定程序“做什么…

运用AI搭建中间服务层(一)

知识点 适用于 AI 的 Visual Studio 工具 微软认知服务&#xff08;影像服务/实体搜索服务&#xff09;的使用 商业应用软件的架构设计 ASP.NET 核心 Web 应用程序 休息 应用程序接口 服务端的测试技术 软件工程中的需求演进处理 不断演进的应用场景 下面我们会用讲故…

PR-视频去水印

文章目录 前言PR-视频去水印实现示例 前言 如果您觉得有用的话&#xff0c;记得给博主点个赞&#xff0c;评论&#xff0c;收藏一键三连啊&#xff0c;写作不易啊^ _ ^。   而且听说点赞的人每天的运气都不会太差&#xff0c;实在白嫖的话&#xff0c;那欢迎常来啊!!! PR-视频…

Unity组件开发--短连接HTTP

1.网络请求管理器 using LitJson; using Cysharp.Threading.Tasks; using System; using System.Collections; using System.Collections.Generic; using UnityEngine; using UnityEngine.Networking; using UnityEngine.Events;using System.Web; using System.Text; using Sy…

企业的 Android 移动设备管理 (MDM) 解决方案

移动设备管理可帮助您在不影响最终用户体验的情况下&#xff0c;通过无线方式管理和保护组织的移动设备群&#xff0c;现代 MDM 解决方案还可以控制 App、内容和安全性&#xff0c;因此员工可以毫无顾虑地在托管设备上工作。移动设备管理软件可有效管理个人设备上的公司空间。M…

刷题第十五天-存在重复元素Ⅲ

存在重复元素Ⅲ 题目要求 解题思路 主要使用滑动窗口方法&#xff0c;让滑动窗口代销固定为t。 本题最大的难点在于快速地找到滑动窗口内的最大值和最小值&#xff0c;以及删除指定元素。 如果遍历求滑动窗口内的最大值和最小值&#xff0c;时间复杂度是O&#xff08;K&#…

自动化测试框架搭建全过程

前段时间写了一系列自动化测试相关的文章&#xff0c;当然更多的是方法和解决问题的思路角度去阐述我的一些观点。这篇文章来聊聊新手如何从零到一落地实践接口自动化测试。 为什么要做接口测试 测试理念的演变 早些时候&#xff0c;软件研发交付流程大多遵循V型或W型的瀑布模…

vue 公众号开发,调用jssdk封装

vue 公众号开发&#xff0c;经常会使用到 转发朋友&#xff0c;朋友圈&#xff0c;调用扫一扫等功能&#xff0c;这时就要使用微信的 jssdk 微信jssdk传送门 1. 安装jssdk 插件 (jweixin-module) npm install jweixin-module --save 2. 封装方法 utils/jwx.js let jweixin…

Hello,World!

“Hello, world”的由来可以追溯到 The C Programming Language 。在这门编程语言中&#xff0c;它被用作第一个演示程序&#xff0c;向人们展示了在计算机屏幕上输出“Hello world”这行字符串的计算机程序。由于这个演示程序的简洁性和直观性&#xff0c;它成为了许多初学者学…

qt图形化界面开发DAY3

作业&#xff1a; 1> 思维导图 2> 完善对话框&#xff0c;点击登录对话框&#xff0c;如果账号和密码匹配&#xff0c;则弹出信息对话框&#xff0c;给出提示”登录成功“&#xff0c;提供一个Ok按钮&#xff0c;用户点击Ok后&#xff0c;关闭登录界面&#xff0c;跳转…

Android 输入系统介绍

文章目录 一、目的二、环境三、相关概念3.1 输入设备3.2 UEVENT机制3.3 JNI3.4 EPOLL机制3.5 INotify 四、详细设计4.1 结构图4.2 代码结构4.3 InputManagerService模块4.3.1 IMS服务入口4.3.2 IMS初始化4.3.3 IMS启动4.3.4 IMS消息监听 4.4 NativeInputManager模块4.4.1 nativ…

解决Windows 11/10共享打印机无法连接问题0x00000709错误

在解决共享打印机连接问题之前&#xff0c;请确保满足以下几个条件&#xff1a; 确保Windows 11设备和共享打印机的电脑连接到同一个网络。检查网络连接是否稳定。确保共享打印机所连接的计算机处于开机状态。检查共享设置&#xff0c;确保共享打印机在Windows 7计算机上正确设…

Docker安装Nacos2.2.3并鉴权、Prometheus监听Nacos、Grafana监控Nacos【亲测可用】

1、Docker 拉取镜像&#xff1a;docker pull nacos/nacos-server:v2.2.3 2、docker run --env MODEstandalone --name nacos -d -p 8848:8848 -p 9848:9848 -p 9849:9849 nacos/nacos-server:v2.2.3 3、复制镜像中的配置文件 mkdir -vp /home/nacos/logs mkdir -vp /home/n…

Transformer详解【学习笔记】

文章目录 1、Transformer绪论2、Encoders和Decoder2.1 Encoders2.1.1 输入部分2.1.2 多头注意力机制2.1.3 残差2.1.4 LayNorm&#xff08;Layer Normalization&#xff09;2.1.5 前馈神经网路 2.2 Decoder2.2.1 多头注意力机制2.2.2 交互层 1、Transformer绪论 Transformer在做…

使用PyTorch实现去噪扩散模型

在深入研究去噪扩散概率模型(DDPM)如何工作的细节之前&#xff0c;让我们先看看生成式人工智能的一些发展&#xff0c;也就是DDPM的一些基础研究。 VAE VAE 采用了编码器、概率潜在空间和解码器。在训练过程中&#xff0c;编码器预测每个图像的均值和方差。然后从高斯分布中对…

【Spring Boot】项目端口号冲突解决方法,一步到位

启动项目遇到以下问题&#xff1a; Description: Web server failed to start. Port 8080 was already in use. Action: Identify and stop the process that’s listening on port 8080 or configure this application to listen on another port. Process finished with …

「Vue3面试系列」Vue 3.0中Treeshaking特性有哪些?举例说明一下?

文章目录 一、是什么二、如何做Vue2 项目Vue3 项目 三、作用参考文献 一、是什么 Tree shaking 是一种通过清除多余代码方式来优化项目打包体积的技术&#xff0c;专业术语叫 Dead code elimination 简单来讲&#xff0c;就是在保持代码运行结果不变的前提下&#xff0c;去除…

OpenCV入门04:调整图像对比度和亮度

教程开源 本教程开源&#xff0c;地址&#xff1a;https://gitee.com/zccbbg/opencv_study 图像的亮度和对比度说明 亮度&#xff1a; 亮度是指图像中像素的整体明亮程度。在数字图像中&#xff0c;每个像素都有一个灰度值&#xff0c;表示其亮度水平。亮度越高&#xff0c;像…

上海晋名室外暂存柜助力石墨烯材料行业气瓶储存安全

近日上海晋名又有一台室外气瓶暂存柜项目通过验收&#xff0c;此次项目主要用于石墨烯材料行业气瓶的室外暂存。 用户单位创立于2017年&#xff0c;是一家从事石墨烯等新材料技术的科技型高新技术企业。 上海晋名作为一家专注工业安全防护领域&#xff0c;危险化学品安全储存…