常用排序算法汇总—Python版

在这里插入图片描述

一、选择排序

1. 原理:

选择排序(Selection Sort)是一种简单直观的排序算法,它的基本思路是将数组按顺序分成已排序部分和未排序部分,然后每次从未排序部分中选择出最小的元素,将其添加到已排序部分的末尾。重复这个过程,直到未排序部分为空,整个数组都已排好序。

2. 代码

def selection_sort(lst):
    n = len(lst)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if lst[j] < lst[min_idx]:
                min_idx = j
        lst[i], lst[min_idx] = lst[min_idx], lst[i]
    return lst

arr = [3, 5, 8, 1, 2, 9, 4, 7, 6]
sorted_arr = selection_sort(arr)
print(sorted_arr)

二、冒泡排序

1. 原理:

冒泡排序(Bubble Sort)是一种简单直观的排序算法,它的基本思路是重复地遍历数列,一次比较两个元素,如果它们的顺序错误,就交换位置。每一次遍历都将最大或最小的元素“浮”到了最顶端,因此得名冒泡排序。

2. 代码

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


lst = [8, 3, 5, 1, 2, 7, 6, 4]
sorted_lst = bubble_sort(lst)
print(sorted_lst)  # 输出 [1, 2, 3, 4, 5, 6, 7, 8]

三、插入排序

1. 原理:

插入排序(Insertion Sort)是一种简单直观的排序算法,它的基本思路是将未排序的元素一个一个插入到已经排序的部分中适当的位置上去。它的实现过程是将一个待排序的列表分成两部分,第一部分为已排序的,第二部分为未排序的,初始状态下第一部分为列表中的第一个元素,而第二部分为除第一个元素外的其他元素。在排序过程中,我们是从未排序部分中取出一个元素,将它插入到已排序部分中去。重复这个过程,直到未排序部分为空,整个列表都已排好序。

2. 代码

def insertion_sort(lst):
    n = len(lst)
    for i in range(1, n):
        key = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > key:
            lst[j+1] = lst[j]
            j -= 1
        lst[j+1] = key
    return lst



lst = [8, 3, 5, 1, 2, 7, 6, 4]
sorted_lst = insertion_sort(lst)
print(sorted_lst)  # 输出 [1, 2, 3, 4, 5, 6, 7, 8]

该函数的主要实现过程如下:

  1. 遍历整个列表,从下标 i=1 开始,逐步将未排序部分添加到已排序部分中
  2. 选取未排序部分的第一个元素作为 key,将其与已排序部分逐一比较
  3. 如果 key 小于已排序部分的某一个元素,则将该元素向后移动一位,继续比较
  4. 如果 key 大于或等于已排序部分的某一个元素,则将 key 插入到该元素后面

四、归并排序

1. 原理:

归并排序(Merge Sort)是一种基于分治思想的排序算法,它的基本思路是将数组分成两个等长的部分,分别对这两部分进行递归排序,然后将排好序的两个子数组合并起来。因为归并排序的实现过程中需要开辟额外的空间来存储临时数组,所以归并排序不是基于比较排序的最优算法,但归并排序的时间复杂度通常很优秀,表现稳定。

2. 代码

def merge_sort(arr):
    # 递归终止条件,数组长度为 1
    if len(arr) == 1:
        return arr

    # 将数组一分为二,并递归对两个子数组进行排序
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # 对排好序的子数组进行归并操作
    sorted_arr = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1

    sorted_arr += left[i:]
    sorted_arr += right[j:]

    return sorted_arr




lst = [8, 3, 5, 1, 2, 7, 6, 4]
sorted_lst = merge_sort(lst)
print(sorted_lst)  # 输出 [1, 2, 3, 4, 5, 6, 7, 8]

该函数的主要实现过程如下:

  1. 如果数组长度为 1,直接返回该数组(递归终止条件)
  2. 将数组一分为二,并递归对左右两个子数组进行排序,最终返回排好序的子数组
  3. 对排好序的子数组进行归并操作,通过比较两个子数组的首元素,不断将更小的元素添加到一个新的数组中,最终将子数组中剩余的元素也加入到新数组中来
  4. 返回归并后的新数组

五、快速排序

1. 原理

快速排序是一种基于分治思想的排序算法,它的基本思路是先找到一个基准值(pivot),将数组划分为两部分,使得左半部分的所有元素小于等于基准值,右半部分的所有元素大于基准值。然后对左右两个部分分别递归地进行同样的处理,直到整个数组有序。

2. 代码

def quick_sort(arr):
    # 如果数组长度小于等于 1,直接返回
    if len(arr) <= 1:
        return arr

    # 选择第一个元素为基准值,随机选择也是一种优化方法
    pivot = arr[0]

    # 使用列表推导式获取左侧和右侧子数组
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]

    # 递归调用快速排序,并将左右子数组拼接起来
    return quick_sort(left) + [pivot] + quick_sort(right)

lst = [8, 3, 5, 1, 2, 7, 6, 4]
sorted_lst = quick_sort(lst)
print(sorted_lst)  # 输出 [1, 2, 3, 4, 5, 6, 7, 8]

该函数的实现并不复杂,思路也比较清晰。主要包含以下步骤:

  1. 如果数组长度小于等于 1,直接返回该数组
  2. 选择第一个元素作为基准值,将数组划分为左右两个子数组,分别为左半部分 left 和右半部分 right
  3. 对左右子数组进行递归调用快速排序,并将将子数组返回值拼接成新数组,注意需要将基准值 pivot 放入中间

六、堆排序

1. 原理

在 heapify() 函数中,函数的参数 n 表示构成二叉树的前 n 个元素,参数 i 表示当前根节点在数组中的位置。该函数的作用是将以 i 为根节点的子树进行堆化,也就是将其变成一个最大堆。在实现过程中,需要不断检查左右子节点和根节点之间的大小关系,并进行必要的交换。

heap_sort() 函数中,先使用叶节点的父节点开始建立一个最大堆,然后对于数组中已经是最大堆的部分,每次提取根节点(最大值),并将其与堆结构末尾的值进行交换。整个排序过程时间复杂度为 O(nlogn)。

2. 代码

def heapify(arr, n, i):
    """
    以 i 为根节点,将 arr 中的前 n 个元素构成的二叉树进行堆化
    """
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    # 寻找最大值节点
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大值节点不是 i,那么需要进行交换
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        # 递归堆化交换后的子树
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # 构建最大堆
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)

    # 逐个取出最大值
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        # 对前 i 个元素进行重新构建最大堆
        heapify(arr, i, 0)

    return arr

lst = [8, 3, 5, 1, 2, 7, 6, 4]
sorted_lst = heap_sort(lst)
print(sorted_lst)  # 输出 [1, 2, 3, 4, 5, 6, 7, 8]

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

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

相关文章

【五一创作】【软考:软件设计师】 5 计算机组成与体系结构(三)认证技术 | 计算机可靠性

欢迎来到爱书不爱输的程序猿的博客, 本博客致力于知识分享&#xff0c;与更多的人进行学习交流 本文收录于软考中级&#xff1a;软件设计师系列专栏,本专栏服务于软考中级的软件设计师考试,包括不限于知识点讲解与真题讲解两大部分,并且提供电子教材与电子版真题,关注私聊即可 …

三范式(详解+例子)

第一范式&#xff08;1NF&#xff09;&#xff1a;每一列都是不可分割的原子数据项&#xff08;什么意思&#xff0c;每一项都不可分割&#xff0c;像下面的表格就能分割&#xff0c;所以它连第一范式都算不上&#xff09; 分割后的样子 &#xff08;它就是第一范式了&#xff…

FPGA学习_01_基础知识(有点劝退,心灵弱小者勿入)

有些人喜欢直接拿开发板看教程开干&#xff0c;我认为了解点历史发展没什么坏处&#xff0c;一些FPGA的基础知识也是同样重要的。 1.1. FPGA的主要厂商 XILINX 占据FPGA绝大部分的市场份额 ALTERA 被 INTEL 167亿美元收购 改名为INTEL LATTICE 被神秘的中国公…

HMM理论学习笔记-隐马尔可夫模型的三个元素、假设和问题

文章目录 概率论基础条件概率全概公式边缘概率联合概率联合概率与边缘概率的关系贝叶斯公式&#xff08;条件联合概率&#xff09;马尔科夫链的概念 HMM简述HMM的三个元素符号定义1、状态转移概率矩阵A2、观测概率矩阵B3、初始状态概率向量π HMM的三个假设1、齐次马尔可夫假设…

Spring Boot使用(基础)

目录 1.Spring Boot是什么? 2.Spring Boot使用 2.1Spring目录介绍 2.2SpringBoot的使用 1.Spring Boot是什么? Spring Boot就是Spring脚手架,就是为了简化Spring开发而诞生的 Spring Boot的优点: 1.快速集成框架,提供了秒级继承各种框架,提供了启动添加依赖的功能 2.内…

简单搭建node后台(笔记用)

毕设过程 mongodb 配置 使用node写后台一些语法运用bug关于安装一款群控软件后&#xff0c;修改了环境变量导致后台崩溃![](https://img-blog.csdnimg.cn/7c684b2e318048b3ad1db78484e10e6a.jpeg) vue管理后台 mongodb 配置 https://blog.csdn.net/weixin_43405300/article/de…

【SPSS】相关分析和偏相关分析详细操作过程(附案例实战)

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

java的spi机制使用场景讲解和具体使用

八股文背多了&#xff0c;相信大家都听说过一个词&#xff0c;SPI扩展。 有的面试官就很喜欢问这个问题&#xff0c;SpringBoot的自动装配是如何实现的&#xff1f; 基本上&#xff0c;你一说是基于spring的SPI扩展机制&#xff0c;再把spring.factories文件和EnableAutoConf…

C++(多态上)

目录: 1.多态的概念 2.多态的定义和实现 3.虚函数构成重写的特例 4.剖析一道非常经典的题 5.剖析多态的原理 ------------------------------------------------------------------------------------------------------------------------- 1.多态的概念 概念:通俗来说&#…

Word2vec原理+实战学习笔记(二)

来源&#xff1a;投稿 作者&#xff1a;阿克西 编辑&#xff1a;学姐 前篇&#xff1a;Word2vec原理实战学习笔记&#xff08;一&#xff09;​​​​​​​ 视频链接&#xff1a;https://ai.deepshare.net/detail/p_5ee62f90022ee_zFpnlHXA/6 5 对比模型&#xff08;论文Mod…

Python使用AI photo2cartoon制作属于你的漫画头像

Python使用AI photo2cartoon制作属于你的漫画头像 1. 效果图2. 原理3. 源码参考 git clone https://github.com/minivision-ai/photo2cartoon.git cd ./photo2cartoon python test.py --photo_path images/photo_test.jpg --save_path images/cartoon_result.png1. 效果图 官方…

(22)目标检测算法之 yolov8模型导出总结

yolov8模型导出总结 不断更新中… 几种部署情况: onnxxmlengine官网说明:https://github.com/ultralytics/ultralytics/blob/main/docs/modes/export.md导出参数: onnx 参数解析format: 导出的模型形式:onnx xml engine ... imgsz: 设置模型的输入尺寸大小,默认640*640 ke…

磁盘和固态磁盘

磁盘和固态磁盘 磁盘的物理结构 ​ 磁盘的表面由一些磁性的物质组成&#xff0c;可以用这些磁性物质来记录二进制数据。磁盘的盘面被划分成一个个磁道&#xff0c;这样一个“圈”就是一个磁道。同一磁盘上不同磁道上记录的信息量相同&#xff0c;因此内侧磁道上的数据密度较大…

STM32F429移植microPython笔记

目录 一、microPython下载。二、安装开发环境。三、编译开发板源码。四、下载验证。 一、microPython下载。 https://micropython.org/download/官网 下载后放在linux中。 解压命令&#xff1a; tar -xvf micropython-1.19.1.tar.xz 二、安装开发环境。 sudo apt-get inst…

【Java笔试强训 14】

&#x1f389;&#x1f389;&#x1f389;点进来你就是我的人了博主主页&#xff1a;&#x1f648;&#x1f648;&#x1f648;戳一戳,欢迎大佬指点! 欢迎志同道合的朋友一起加油喔&#x1f93a;&#x1f93a;&#x1f93a; 目录 一、选择题 二、编程题 &#x1f525;计算日期…

玩着3dmax把Python学了-01

3ds Max 2022以前的版本要借助Python的api来实现Python编程达到编辑绘图脚本的功能&#xff0c;但是好消息来了&#xff0c;3ds Max 2022 起&#xff0c;MaxPlus 不再作为 3ds Max 的 Python API 包含在内。而是3ds Max 将 Python 3.7 的标准版本包涵其中了&#xff0c;位于 [3…

Filter 过滤器

Filter过滤器介绍 这里我们讲解Filter的执行流程&#xff0c;从下图可以大致了解到&#xff0c;当客户端发送请求的时候&#xff0c;会经过过滤器&#xff0c;然后才能到我们的servlet&#xff0c;当我们的servlet处理完请求之后&#xff0c;我们的response还是先经过过滤器才…

基于SpringBoot的线上日志阅读器

软件特点 部署后能通过浏览器查看线上日志。支持Linux、Windows服务器。采用随机读取的方式&#xff0c;支持大文件的读取。支持实时打印新增的日志&#xff08;类终端&#xff09;。支持日志搜索。 使用手册 基本页面 配置路径 配置日志所在的目录&#xff0c;配置后按回车…

2023亚马逊云科技研究,数字化技能为中国企业和员工带来经济效益

在中国&#xff0c;信息技术在个人、企业和宏观经济层面都推动着重大变革。为了研究这些变化所带来的影响&#xff0c;盖洛普咨询公司(Gallup)和亚马逊云科技开展了关于数字化技能的调研。 研究表明&#xff0c;数字化技能正在为中国企业和在职人员带来巨大的经济价值&#x…

一文带你入门C++类和对象【十万字详解,一篇足够了】

本文字数较多&#xff0c;建议电脑端访问。不多废话&#xff0c;正文开始 文章目录 ———————————————【类和对象 筑基篇】 ———————————————一、前言二、面向过程与面向对象三、结构体与类1、C中结构体的变化2、C中结构体的具体使用3、结构体 --&…
最新文章