数据结构八大算法详解

news/2024/4/12 14:48:37/文章来源:https://blog.csdn.net/qq_42889888/article/details/136564445

一、直接插入排序

  • 直接插入排序的核心思想就是:将数组中的所有元素依次跟前面已经排好的元素相比较,如果选择的元素比已排序的元素小,则交换,直到全部元素都比较过。
    因此,从上面的描述中我们可以发现,直接插入排序可以用两个循环完成:

  • 第一层循环:遍历待比较的所有数组元素
  • 第二层循环:将本轮选择的元素(selected)与已经排好序的元素(ordered)相比较。
    如果:selected > ordered,那么将二者交换
  • 代码实现
  • #直接插入排序
    def insert_sort(L):#遍历数组中的所有元素,其中0号索引元素默认已排序,因此从1开始for x in range(1,len(L)):#将该元素与已排序好的前序数组依次比较,如果该元素小,则交换#range(x-1,-1,-1):从x-1倒序循环到0for i in range(x-1,-1,-1):#判断:如果符合条件则交换if L[i] > L[i+1]:temp = L[i+1]L[i+1] = L[i]L[i] = temp

    二、希尔排序

  • 希尔排序的算法思想:将待排序数组按照步长gap进行分组,然后将每组的元素利用直接插入排序的方法进行排序;每次将gap折半减小,循环上述操作;当gap=1时,利用直接插入,完成排序。
    同样的:从上面的描述中我们可以发现:希尔排序的总体实现应该由三个循环完成:

  • 第一层循环:将gap依次折半,对序列进行分组,直到gap=1
  • 第二、三层循环:也即直接插入排序所需要的两次循环。具体描述见上。
  • 代码实现:
  • #希尔排序
    def insert_shell(L):#初始化gap值,此处利用序列长度的一般为其赋值gap = (int)(len(L)/2)#第一层循环:依次改变gap值对列表进行分组while (gap >= 1):#下面:利用直接插入排序的思想对分组数据进行排序#range(gap,len(L)):从gap开始for x in range(gap,len(L)):#range(x-gap,-1,-gap):从x-gap开始与选定元素开始倒序比较,每个比较元素之间间隔gapfor i in range(x-gap,-1,-gap):#如果该组当中两个元素满足交换条件,则进行交换if L[i] > L[i+gap]:temp = L[i+gap]L[i+gap] = L[i]L[i] =temp#while循环条件折半gap = (int)(gap/2)

    三、简单选择排序

  • 简单选择排序的基本思想:比较+交换。

  • 从待排序序列中,找到关键字最小的元素;
  • 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;
  • 从余下的 N - 1 个元素中,找出关键字最小的元素,重复(1)、(2)步,直到排序结束。
    因此我们可以发现,简单选择排序也是通过两层循环实现。
    第一层循环:依次遍历序列当中的每一个元素
    第二层循环:将遍历得到的当前元素依次与余下的元素进行比较,符合最小元素的条件,则交换。
  • 代码实现
  • # 简单选择排序
    def select_sort(L):
    #依次遍历序列中的每一个元素for x in range(0,len(L)):
    #将当前位置的元素定义此轮循环当中的最小值minimum = L[x]
    #将该元素与剩下的元素依次比较寻找最小元素for i in range(x+1,len(L)):if L[i] < minimum:temp = L[i];L[i] = minimum;minimum = temp
    #将比较后得到的真正的最小值赋值给当前位置L[x] = minimum

    四、堆排序

  • 堆的概念
    堆:本质是一种数组对象。特别重要的一点性质:<b>任意的叶子节点小于(或大于)它所有的父节点</b>。对此,又分为大顶堆和小顶堆,大顶堆要求节点的元素都要大于其孩子,小顶堆要求节点元素都小于其左右孩子,两者对左右孩子的大小关系不做任何要求。
    利用堆排序,就是基于大顶堆或者小顶堆的一种排序方法。下面,我们通过大顶堆来实现。

  • 基本思想:
    堆排序可以按照以下步骤来完成:首先将序列构建称为大顶堆;(这样满足了大顶堆那条性质:位于根节点的元素一定是当前序列的最大值) 

  • 取出当前大顶堆的根节点,将其与序列末尾元素进行交换;
    (此时:序列末尾的元素为已排序的最大值;由于交换了元素,当前位于根节点的堆并不一定满足大顶堆的性质)
  • 对交换后的n-1个序列元素进行调整,使其满足大顶堆的性质;

  • 重复2.3步骤,直至堆中只有1个元素为止

  • 代码实现:

  • #-------------------------堆排序--------------------------------
    #**********获取左右叶子节点**********
    def LEFT(i):return 2*i + 1
    def RIGHT(i):return 2*i + 2
    #********** 调整大顶堆 **********
    #L:待调整序列 length: 序列长度 i:需要调整的结点
    def adjust_max_heap(L,length,i):
    #定义一个int值保存当前序列最大值的下标largest = i
    #执行循环操作:两个任务:1 寻找最大值的下标;2.最大值与父节点交换while (1):
    #获得序列左右叶子节点的下标left,right = LEFT(i),RIGHT(i)
    #当左叶子节点的下标小于序列长度 并且 左叶子节点的值大于父节点时,将左叶子节点的下标赋值给largestif (left < length) and (L[left] > L[i]):largest = leftprint('左叶子节点')else:largest = i
    #当右叶子节点的下标小于序列长度 并且 右叶子节点的值大于父节点时,将右叶子节点的下标值赋值给largestif (right < length) and (L[right] > L[largest]):largest = rightprint('右叶子节点')
    #如果largest不等于i 说明当前的父节点不是最大值,需要交换值if (largest != i):temp = L[i]L[i] = L[largest]L[largest] = tempi = largestprint(largest)continueelse:break
    #********** 建立大顶堆 **********
    def build_max_heap(L):length = len(L)for x in range((int)((length-1)/2),-1,-1):adjust_max_heap(L,length,x)
    #********** 堆排序 **********
    def heap_sort(L):
    #先建立大顶堆,保证最大值位于根节点;并且父节点的值大于叶子结点build_max_heap(L)
    #i:当前堆中序列的长度.初始化为序列的长度i = len(L)
    #执行循环:1. 每次取出堆顶元素置于序列的最后(len-1,len-2,len-3...)
    #         2. 调整堆,使其继续满足大顶堆的性质,注意实时修改堆中序列的长度while (i > 0):temp = L[i-1]L[i-1] = L[0]L[0] = temp
    #堆中序列长度减1i = i-1
    #调整大顶堆adjust_max_heap(L,i,0)

    五、冒泡排序

  • 冒泡排序思路比较简单:

  • 将序列当中的左右元素,依次比较,保证右边的元素始终大于左边的元素;
    ( 第一轮结束后,序列最后一个元素一定是当前序列的最大值;)
  • 对序列当中剩下的n-1个元素再次执行步骤1。
  • #冒泡排序
    def bubble_sort(L):length = len(L)
    #序列长度为length,需要执行length-1轮交换for x in range(1,length):
    #对于每一轮交换,都将序列当中的左右元素进行比较
    #每轮交换当中,由于序列最后的元素一定是最大的,因此每轮循环到序列未排序的位置即可for i in range(0,length-x):if L[i] > L[i+1]:temp = L[i]L[i] = L[i+1]L[i+1] = temp

    六、快速排序

  • 本思想:挖坑填数+分治法
  • 从序列当中选择一个基准数(pivot)
    在这里我们选择序列当中第一个数最为基准数
  • 将序列当中的所有数依次遍历,比基准数大的位于其右侧,比基准数小的位于其左侧
  • 重复步骤1.2,直到所有子集当中只有一个元素为止。
    用伪代码描述如下:
    1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。
    2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
    3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。
    4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中
  • 代码实现:
  • #快速排序
    #L:待排序的序列;start排序的开始index,end序列末尾的index
    #对于长度为length的序列:start = 0;end = length-1
    def quick_sort(L,start,end):if start < end:i , j , pivot = start , end , L[start]while i < j:
    #从右开始向左寻找第一个小于pivot的值while (i < j) and (L[j] >= pivot):j = j-1
    #将小于pivot的值移到左边if (i < j):L[i] = L[j]i = i+1 
    #从左开始向右寻找第一个大于pivot的值while (i < j) and (L[i] < pivot):i = i+1
    #将大于pivot的值移到右边if (i < j):L[j] = L[i]j = j-1
    #循环结束后,说明 i=j,此时左边的值全都小于pivot,右边的值全都大于pivot
    #pivot的位置移动正确,那么此时只需对左右两侧的序列调用此函数进一步排序即可
    #递归调用函数:依次对左侧序列:从0 ~ i-1//右侧序列:从i+1 ~ endL[i] = pivot
    #左侧序列继续排序quick_sort(L,start,i-1)
    #右侧序列继续排序quick_sort(L,i+1,end)

    七、归并排序

  • 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个典型的应用。它的基本操作是:将已有的子序列合并,达到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。
  • 归并排序其实要做两件事:
  • 分解----将序列每次折半拆分
  • 合并----将划分后的序列段两两排序合并
    因此,归并排序实际上就是两个操作,拆分+合并
  • 如何合并?
    L[first...mid]为第一段,L[mid+1...last]为第二段,并且两端已经有序,现在我们要将两端合成达到L[first...last]并且也有序。
  • 首先依次从第一段与第二段中取出元素比较,将较小的元素赋值给temp[]
  • 重复执行上一步,当某一段赋值结束,则将另一段剩下的元素赋值给temp[]
  • 此时将temp[]中的元素复制给L[],则得到的L[first...last]有序
  • 如何分解?
    在这里,我们采用递归的方法,首先将待排序列分成A,B两组;然后重复对A、B序列
    分组;直到分组后组内只有一个元素,此时我们认为组内所有元素有序,则分组结束。
  • 代码实现

  • # 归并排序
    #这是合并的函数
    # 将序列L[first...mid]与序列L[mid+1...last]进行合并
    def mergearray(L,first,mid,last,temp):
    #对i,j,k分别进行赋值i,j,k = first,mid+1,0
    #当左右两边都有数时进行比较,取较小的数while (i <= mid) and (j <= last):if L[i] <= L[j]:temp[k] = L[i]i = i+1k = k+1else:temp[k] = L[j]j = j+1k = k+1
    #如果左边序列还有数while (i <= mid):temp[k] = L[i]i = i+1k = k+1
    #如果右边序列还有数while (j <= last):temp[k] = L[j]j = j+1k = k+1
    #将temp当中该段有序元素赋值给L待排序列使之部分有序for x in range(0,k):L[first+x] = temp[x]
    # 这是分组的函数
    def merge_sort(L,first,last,temp):if first < last:mid = (int)((first + last) / 2)
    #使左边序列有序merge_sort(L,first,mid,temp)
    #使右边序列有序merge_sort(L,mid+1,last,temp)
    #将两个有序序列合并mergearray(L,first,mid,last,temp)
    # 归并排序的函数
    def merge_sort_array(L):
    #声明一个长度为len(L)的空列表temp = len(L)*[None]
    #调用归并排序merge_sort(L,0,len(L)-1,temp)

    八、基数排序

  • 基数排序:通过序列中各个元素的值,对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。
    分配:我们将L[i]中的元素取出,首先确定其个位上的数字,根据该数字分配到与之序号相同的桶中
    收集:当序列中所有的元素都分配到对应的桶中,再按照顺序依次将桶中的元素收集形成新的一个待排序列L[ ]
    对新形成的序列L[]重复执行分配和收集元素中的十位、百位...直到分配完该序列中的最高位,则排序结束
  • 根据上述“基数排序”的展示,我们可以清楚的看到整个实现的过程
  • 代码实现
  • #************************基数排序****************************
    #确定排序的次数
    #排序的顺序跟序列中最大数的位数相关
    def radix_sort_nums(L):maxNum = L[0]
    #寻找序列中的最大数for x in L:if maxNum < x:maxNum = x
    #确定序列中的最大元素的位数times = 0while (maxNum > 0):maxNum = (int)(maxNum/10)times = times+1return times
    #找到num从低到高第pos位的数据
    def get_num_pos(num,pos):return ((int)(num/(10**(pos-1))))%10
    #基数排序
    def radix_sort(L):count = 10*[None]       #存放各个桶的数据统计个数bucket = len(L)*[None]  #暂时存放排序结果
    #从低位到高位依次执行循环for pos in range(1,radix_sort_nums(L)+1):#置空各个桶的数据统计for x in range(0,10):count[x] = 0#统计当前该位(个位,十位,百位....)的元素数目for x in range(0,len(L)):#统计各个桶将要装进去的元素个数j = get_num_pos(int(L[x]),pos)count[j] = count[j]+1#count[i]表示第i个桶的右边界索引for x in range(1,10):count[x] = count[x] + count[x-1]#将数据依次装入桶中for x in range(len(L)-1,-1,-1):#求出元素第K位的数字j = get_num_pos(L[x],pos)#放入对应的桶中,count[j]-1是第j个桶的右边界索引bucket[count[j]-1] = L[x]#对应桶的装入数据索引-1count[j] = count[j]-1# 将已分配好的桶中数据再倒出来,此时已是对应当前位数有序的表for x in range(0,len(L)):L[x] = bucket[x]

    原文:https://www.cnblogs.com/hokky/p/8529042.html

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

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

相关文章

奖励建模(Reward Modeling)实现人类对智能体的反馈

奖励建模&#xff08;Reward Modeling&#xff09;是强化学习中的一个重要概念和技术&#xff0c;它主要用于训练智能体&#xff08;如AI机器人或大型语言模型&#xff09;如何更有效地学习和遵循人类期望的行为。在强化学习环境中&#xff0c;智能体通过尝试不同的行为获得环境…

【外汇天眼】外汇投资策略:区间突破交易系统

RangeBreak系统介绍 RangeBreak区间突破交易系统被市场广泛用于日内交易&#xff0c;曾经连续多年在《美国期货杂志》盈利交易系统排行榜中位居前十。 目前该交易系统也仍旧被很多专业机构和个人投资者所推崇。 交易者可根据自己的交易习惯和性格特点进行改进&#xff0c;并不…

深入分析Android运行时环境ART:原理、特点与优化策略

摘要 随着移动互联网的快速发展&#xff0c;智能手机的性能和功能日益强大&#xff0c;其中Android操作系统因其开放性和灵活性而占据主导地位。Android运行时环境&#xff08;ART&#xff09;作为执行应用程序代码的关键组件&#xff0c;在系统性能和用户体验方面起着至关重要…

Docker创建nacos容器

1.创建数据库tq_nacos,sql文件可以从 下面地址中下载nacos安装包&#xff0c;解压后获取到sql文件nacos-mysql.sql https://github.com/alibaba/nacos/releases/tag/1.1.4 2.拉取镜像&#xff0c;创建简单容器 docker search nacosdocker pull nacos/nacos-serverdocker run…

Android使用WebView打开内嵌H5网页

Android打开外部网页链接请参考上一篇文章 https://public.blog.csdn.net/article/details/136384559 继上篇&#xff0c;新建assets文章夹&#xff0c;将H5的网页资源放到此文件夹下 把H5的资源文件都拷进来 这个时候&#xff0c;将添加打开本地网页的代码&#xff1a; //打…

3.8 动态规划 背包问题

一.01背包 46. 携带研究材料&#xff08;第六期模拟笔试&#xff09; (kamacoder.com) 代码随想录 (programmercarl.com) 携带研究材料: 时间限制&#xff1a;5.000S 空间限制&#xff1a;128MB 题目描述: 小明是一位科学家&#xff0c;他需要参加一场重要的国际科学大会…

friend(c++ 关键字)

定义 C中&#xff0c;friend关键字用于声明友元函数或友元类&#xff0c;它们可以访问类的私有&#xff08;private&#xff09;和保护&#xff08;protected&#xff09;成员&#xff0c;即使它们不是类的成员。这提供了一种突破数据封装和隐藏的方式&#xff0c;使得某些函数…

[进程间通信]管道通信【初识IPC/模拟匿名管道/模拟进程池】

文章目录 0.认识IPC1.什么是进程间通信&#xff1f;2.IPC的手段3.进程间通信的必要性4.进程间通信的技术背景5.进程间通信的本质理解6.IPC的标准 1.学习管道1.1.管道的认识1.2管道的工作原理1.3管道的特点 2.模拟匿名管道3.模拟进程池3.1task.hpp3.2processpool.cc 0.认识IPC …

AntV L7的pointLayer点图层

本案例使用L7库和Mapbox GL JS创建点数据并加载进地图。 文章目录 1. 引入 CDN 链接2. 引入组件3. 创建地图4. 创建场景5. 创建点数据5.1. 普通 json 数据5.2. geojson 数据 6. 创建点图层6.1. 普通 json 数据6.2. geojson 数据 7. 演示效果8. 代码实现 1. 引入 CDN 链接 <s…

持续集成(CICD)- gogs仓库的部署和使用

文章目录 一、gogs的介绍二、部署gog仓库三、首次启动gogs四、登录五、创建一个非空仓库六、从仓库拉取代码到本地七、把本地编辑的代码上传到仓库 一、gogs的介绍 Gogs作为一个轻量级、易于部署和使用的自托管Git服务&#xff0c;为小型团队和个人开发者提供了一个简单而强大…

985硕的4家大厂实习与校招经历专题分享(part2)

我的个人经历&#xff1a; 985硕士24届毕业生&#xff0c;实验室方向:CV深度学习 就业&#xff1a;工程-java后端 关注大模型相关技术发展 校招offer: 阿里巴巴 字节跳动 等10 研究生期间独立发了一篇二区SCI 实习经历:字节 阿里 京东 B站 &#xff08;只看大厂&#xff0c;面试…

稀碎从零算法笔记Day6-LeetCode:长度最小的子数组

前言&#xff1a;做JD的网安笔试题&#xff0c;结果查找子串&#xff08;单词&#xff09;这个操作不会。痛定思痛&#xff0c;决定学习滑动数组 题型&#xff1a;数组、双指针、滑动窗口 链接&#xff1a;209. 长度最小的子数组 - 力扣&#xff08;LeetCode&#xff09; 来…

VS配置开发与远程调试笔记

先简单写一下&#xff0c;后续详细补充 场景&#xff1a;本地机器开发&#xff0c;虚拟机调试 准备工作&#xff1a; 由于要将生成的文件生成在虚拟机&#xff0c;避免反复拷贝&#xff0c;直接配置虚拟机共享文件夹进行写入&#xff0c;步骤如下&#xff1a; 虚拟机打开网…

修复通达OA 百度ueditor 文件上传漏动

前些日子&#xff0c;服务器阿里云监控报警&#xff0c;有文件木马文件&#xff0c;因为非常忙&#xff0c;就没及时处理&#xff0c;直接删除了木马文件了事。 谁知&#xff0c;这几天对方又上传了木马文件。好家伙&#xff0c;今天不花点时间修复下&#xff0c;你都传上瘾了…

hadoop学习中遇到的问题一

由于看视频总是断断续续&#xff0c;经常遇到各种报错&#xff0c;现将遇到的问题进行总结。 hadoop学习中遇到的问题&#xff1a;hadoop拒绝连接 hadoop安装好之后&#xff0c;在本地浏览器输入地址http://192.168.222.102:9870&#xff0c;提示拒绝连接。在网上找了很多相关…

【Unity开发】【VR】PICO项目在运行编辑器时无法正常显示游戏场景

【背景】 做了一个PICO项目&#xff0c;真机在手边时开发后用PC的Preview模式直接调试&#xff0c;真机不在手边时希望用VRTK的Simulation Rig&#xff0c;用键鼠模拟控制器输入进行快速调试。但是发现Simulation Rig状态下运行后&#xff0c;游戏场景变得很怪&#xff0c;很多…

44.网络编程/静态库动态库相关知识20240307

一、基于UDP的网络聊天室 项目需求&#xff1a; 如果有用户登录&#xff0c;其他用户可以收到这个人的登录信息如果有人发送信息&#xff0c;其他用户可以收到这个人的群聊信息如果有人下线&#xff0c;其他用户可以收到这个人的下线信息服务器可以发送系统信息。 服务器代码…

O2O:Sample Efficient Offline-to-Online Reinforcement Learning

IEEE TKDE 2024 paper Introduction O2O存在策略探索受限以及分布偏移问题&#xff0c;进而导致在线微调阶段样本效率低。文章提出OEMA算法首先使用离线数据训练乐观的探索策略&#xff0c;然后提出基于元学习的优化方法&#xff0c;减少分布偏移并提高O2O的适应过程。 Meth…

23种设计模式——工厂方法模式

定义&#xff1a; 一个用于创建对象的接口&#xff0c;让子类决定实例化哪一个类。工厂方法使一个类的实例化延迟到其他子类。 工厂方法通用类图&#xff1a; 这个图更好理解 在工厂方法模式中&#xff0c;抽象产品类Product负责定义产品的共性&#xff0c;实现对事物最抽象的…