排序——数据结构与算法 总结8

目录

8.1 排序相关概念

8.2 插入排序

8.2.1 直接插入排序:

8.2.2 折半插入排序:

8.2.3 希尔排序:

8.3 交换排序

8.3.1 冒泡排序:

8.3.2 快速排序:

8.4 选择排序

8.4.1 简单选择排序

8.4.2 堆排序

8.5 归并排序

8.6 排序算法复杂度


8.1 排序相关概念

  • 排序码:排序的依据,也称关键码
  • 排序是对线性结构的一种操作
  • 排序算法的稳定性:假定在待排序的记录序列中存在多个具有相同关键码的记录,若经过排序,这些记录的相对次序保持不变,则称这种排序算法稳定,否则为不稳定。
  • 根据排序过程中所有记录是否全部放在内存中,排序方法分为

    (1) 内排序:过程中,待排序的所有记录全部放在内存中

    (2) 外排序:过程中,需要在内外存之间交换数据

  • 根据排序方法是否建立在关键码比较的基础上,排序方法分为:

    (1) 基于比较:通过关键码之间的比较和记录的移动实现。(包括插入排序、交换排序、选择排序和归并排序)

    (2) 不基于比较:根据待排序数据的特点所采取的其他方法。(基数排序)

8.2 插入排序

8.2.1 直接插入排序:

    基本思路:有将数组分为有序区和无序区,初始时有序区只有一个元素,将无序区的元素一个一个插入有序区,直到所有元素都在有序区内。

# 直接插入排序
def InsertSort(R):for i in range(1,len(R)):if R[i]<R[i-1]:temp = R[i]  # 取出无序区的第一个元素j = i-1  # 前面都是有序的,在有序区中找插入的位置while True:R[j+1] = R[j]  # 将大于temp的元素后移,空出一个插入的位置j-=1if j<0 or R[j]<=temp:breakR[j+1] = tempreturn R

8.2.2 折半插入排序:

    折半插入排序和直接插入排序思路差不多,不过在将无序区元素插入有序区时用折半的方法插入。只是优化了插入的部分。

8.2.3 希尔排序:

    基本思路:先将整个待排序记录序列分隔成若干个子序列,在子序列内分别进行直接插入排序,待整个序列基本有序后,再对整体记录进行一次直接插入排序。

    步骤:

    (1) 相邻d个位置的元素分为一组,d=n/2(d是增量)

    (2) 将排序序列分为d个组,在各组内进行直接插入排序

    (3) 递减d=d/2,重复第二步,直到d=0为止

希尔算法的时间复杂度难以分析,一般认为其平均时间复杂度为O(n1.58)。希尔排序的速度通常要比直接插入排序快。

希尔排序是一种不稳定的排序算法

8.3 交换排序

8.3.1 冒泡排序:

    基本思路:两个元素反序时进行交换

    冒小泡:从后往前看,如果后面的比前面的小就交换。

若某一趟没有出现元素交换,说明所有元素已排好序了。

# 冒泡排序
def BubbleSort(R):for i in range(len(R)-1):exchange = Falsefor j in range(len(R)-1,i,-1):if R[j]<R[j-1]:R[j],R[j-1] = R[j-1],R[j]exchange=Trueif exchange == False:return R

8.3.2 快速排序:

    先选择一个基准(一般是第一个元素),将待排序记录划分为两部分,左侧关键码小于基准,右侧关键码大于基准,将基准值与左侧最后一个值交换位置,使得基准值在中间。然后分别对左右部分重复上述过程,直到排好。

【例题】

快速排序过程可以用递归树表示

#快速排序
def quickSort(lst,l,r):if r<=l:returnq = partition(A,l,r)quickSort(A,l,q-1)quickSort(A,q+1,r)def partition(A,l,r): #将元素进行随机划分p = randint(A[l],A[r])A[p],A[r] = A[r],A[p]i = lfor j in range(l,r-1):if A[j]<=A[r]:A[i],A[j] = A[j],A[i]i+=1A[i],A[r] = A[r],A[i]return i

8.4 选择排序

8.4.1 简单选择排序

    分为无序区和有序区,每趟在无序区中选出最小的记录minj,minj和有序区后一个数字交换

    是一种不稳定的排序方法

# 简单选择排序
def SelectSort(R):for i in range(len(R)-1):minj = ifor j in range(i+1,len(R)):if R[j]<R[minj]:  # 从无序区选最小元素minj = jif minj!=i:R[i],R[minj] = R[minj],R[i]

8.4.2 堆排序

    堆是完全二叉树

    堆的存储是顺序的

    堆的定义:大根堆,小根堆

    大根堆:父结点的关键字大于子结点的关键字

步骤:

(1)根据序列用广度优先构建一个完全二叉树,上滤(自底向上)调整为大根堆

(2)输出堆顶元素,然后用堆尾元素代替堆顶

(3)从根节点筛选,使其形成一个堆(此时的根节点就是之前的堆尾元素)

    筛选:将根节点与左右孩子的较大者进行交换,一直进行到所有子树均为堆或将调整结点交换到叶子位置。

(4)重复二三步骤(n-1次),得到有序序列

【例题】

8.5 归并排序

基础思路:将两个位置相邻的有序子序列归并为一个有序序列

归并要做 \left \lceil log_2n \right \rceil 趟,每趟归并时间为O(n)

#归并排序,给列表A中下标从l到r的区间排序
def mergeSort(A,l,r):if r-l<=1:#边界条件处理returnmid = (l+r)//2mergeSort(A,l,mid)#递归调用mergeSort(A,mid,r)merge(A,l,mid,r)#递推到当前层def merge(A,l,mid,r): #合并数组A[l,m-1]和A[m,r-1]l = A[l,mid-1]r = A[mid,r-1]k = 0i = 0j = 0while k<=r-l:if l[i]<=r[j]:i +=1A[K] = l[i]else:A[K] = r[j]j+=1k+=1

8.6 排序算法复杂度

基于比较排序算法的平均时间复杂度不可能优于O(nlog_2n)

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

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

相关文章

Conformal low power-2.电源感知等效性检查

电源感知等效性检查 ■ 第24页&#xff1a;电源感知等效性检查概述 ■ 第24页&#xff1a;启动低功耗&#xff08;等效性检查&#xff09;软件 ■ 第25页&#xff1a;电源感知等效性检查流程 ■ 第28页&#xff1a;电源感知等效性检查示例Do文件 电源感知等效性检查概述…

C# 异步编程Invoke、beginInvoke、endInvoke的用法和作用

C# 异步编程Invoke、beginInvoke、endInvoke的用法和作用 一、Invoke Invoke的本质只是一个方法&#xff0c;方法一定是要通过对象来调用的。 一般来说&#xff0c;Invoke其实用法只有两种情况&#xff1a; Control的Invoke Delegate的Invoke 也就是说&#xff0c;Invoke前…

【IEEE官方列表会议,EI, Scopus稳定检索】第三届半导体与电子技术国际研讨会(ISSET 2024,2024年8月23-25)

2024年第三届半导体与电子技术国际研讨会&#xff08;ISSET 2024&#xff09;将于2024年8月23-25日在中国西安举行。 ISSET 2024将围绕“半导体”与“电子技术”等相关最新研究领域&#xff0c;为来自国内外高等院校、科学研究所、企事业单位的专家、教授、学者、工程师等提供一…

Ubuntu20.04系统非root用户安装GAMIT10.71

&#xff08;测试环境&#xff1a;20240701升级包和20240701数据&#xff0c;解算通过&#xff09; QQ:8212714 群&#xff1a;302883438群文件&#xff08;source安装包20240701升级包&#xff09; 1、首先在计算机中安装VMware Workstation 16 Pro。建议&#xff1a;分配…

提高LabVIEW软件通用性的方法

提高LabVIEW软件通用性的方法 在使用LabVIEW开发软件时&#xff0c;提高软件的通用性非常重要。通用性意味着软件可以在不同的应用场景中使用&#xff0c;具备高度的适应性和灵活性&#xff0c;从而提高软件的价值和用户满意度。以下从多个角度详细探讨如何提高LabVIEW软件的通…

二十年大数据到 AI,图灵奖得主眼中的数据库因果循环

最近&#xff0c;MIT 教授 Michael Stonebraker 和 CMU 教授 Andrew Pavlo (Andy) 教授联合发表了一篇数据库论文。Michael Stonebraker 80 高龄&#xff0c;是数据库行业唯一在世的图灵奖得主&#xff0c;Andy 则是业界少壮派里的最大 KOL。 一老一少&#xff0c;当今数据库届…

获超九成Gartner用户力推!FortiGate连续五年斩获“客户之选”称号

近日&#xff0c;Gartner Peer Insights™ 网络防火墙客户之选报告发布&#xff0c;Fortinet 连续第五年荣登这项权威榜单。该评选结果源于广大用户对 Fortinet 防火墙产品的真实反馈&#xff0c;是客户选择 Fortinet 的重要参考依据&#xff0c;也是FortiGate能够占据全球防火…

玩鸣潮提示错误代码126:加载x3daudio1_7.dll失败无法打开的多个详细有效解决方法分享

玩游戏期间你是否也有遇到过找不到x3daudio1_7.dll无法继续执行代码打不开游戏&#xff1f;那么遇到这个问题要怎么办&#xff1f;有什么方法能解决&#xff1f;今天详细给大家介绍一下如何解决找不到x3daudio1_7.dll文件或x3daudio1_7.dll丢失的多个不同方法&#xff01; 第一…

数据开源 | Magic Data大模型高质量十万轮对话数据集

能够自然的与人类进行聊天交谈&#xff0c;是现今的大语言模型 (LLM) 区别于传统语言模型的重要能力之一&#xff0c;近日OpenAI推出的GPT-4o给我们展示了这样的可能性。 对话于人类来说是与生俱来的&#xff0c;但构建具备对话能力的大模型是一项不小的挑战&#xff0c;收集高…

three-platformize 微信小程序 uniapp 使用截图功能

最近需要将3d场景进行截图&#xff0c;但是网上的各种各样&#xff0c;看的我一团乱麻&#xff0c;因此在解决完后就将这些简单的分享一下&#xff1b; 原理&#xff1a;将3维场景的那个canvas中的像素提取出来&#xff0c;找一个空的canvas二维画布放上去&#xff0c;然后用二…

【鸿蒙学习笔记】Stage模型

官方文档&#xff1a;Stage模型开发概述 目录标题 Stage模型好处Stage模型概念图ContextAbilityStageUIAbility组件和ExtensionAbility组件WindowStage Stage模型-组件模型Stage模型-进程模型Stage模型-ArkTS线程模型和任务模型关于任务模型&#xff0c;我们先来了解一下什么是…

Pearson 相关系数的可视化辅助判断和怎么用

Pearson 相关系数的可视化辅助判断和怎么用 flyfish Pearson 相关系数 是一种用于衡量两个连续型变量之间线性相关程度的统计量。其定义为两个变量协方差与标准差的乘积的比值。公式如下&#xff1a; r ∑ ( x i − x ˉ ) ( y i − y ˉ ) ∑ ( x i − x ˉ ) 2 ∑ ( y i −…

RK3568平台(opencv篇)opencv处理图像视频

一.读取图像文件并展示 灰度图像&#xff1a; 灰度图需要用 8 位二进制来表示&#xff0c;取值范围是 0-255。用 0 表示 0&#xff08;黑色&#xff09;&#xff0c; 用 255 表示 1&#xff08;白色&#xff09;&#xff0c;取值越大表示该点越亮。 RGB 彩色图像&#xff1a;…

计算机网络浅谈—什么是 OSI 模型?

开放系统通信&#xff08;OSI&#xff09;模型是一个代表网络通信工作方式的概念模型。 思维导图 什么是 OSI 模型&#xff1f; 开放系统互连 (OSI) 模型是由国际标准化组织创建的概念模型&#xff0c;支持各种通信系统使用标准协议进行通信。简单而言&#xff0c;OSI 为保证…

【问题记录】VsCode中以管理员权限运行Powershell

问题展示 今天在尝试运行nodemon命令的时候出问题&#xff0c;显示没法识别&#xff0c;经过分析发现是管理员权限的问题&#xff0c;由于是在vscode里面进行开发&#xff0c;因此特此进行配置。 方法一 直接在vscode命令行中输入如下命令&#xff1a; Start-Process powers…

如何查询并下载韩国签证

登录大韩民国签证门户网站&#xff08;https://www.visa.go.kr&#xff09;&#xff0c;点击“查询/签发”- “办理进度查询及打印”。 2) 输入护照号码、英文姓名及出生日期后点击查询。 3) 若签证通过&#xff0c;办理状态信息栏下面会显示签证信息。 4&#xff09;点击“签证…

人生苦短,我用Python+Docker

今天用一个简单的例子&#xff0c;介绍下如何使用Docker进行Python部署。 前期准备 本地需要有Python环境&#xff1b; 一个Linux的服务器并已经装好Docker &#xff1b; 能把代码上传到服务端的工具。 本文的本地环境是Win10Python3.12&#xff0c;服务器使用Ubuntu的云服…

springboot通江银耳销售管理系统-计算机毕业设计源码15998

摘要 随着人们健康意识的增强&#xff0c;银耳这种传统的中药食材备受关注。而通江银耳是四川省通江县特产&#xff0c;中国国家地理标志产品。四川省通江县是银耳的发源地&#xff0c;中国银耳之乡&#xff0c;通江银耳因主产于此而得名&#xff0c;以其独到的质厚、肉嫩、易炖…

Objective-C 中的 isa 不再是简单的结构体指针

了解 Objective-C 中的 isa 指针内存结构 在 Objective-C 中&#xff0c;isa 指针是对象和类之间的重要桥梁。它不仅帮助运行时系统识别对象的类型&#xff0c;还参与了一些内存和性能优化。本文将深入讲解 isa 指针的内存结构&#xff0c;包括其在早期和现代实现中的演变。 …

彩虹小插画:成都亚恒丰创教育科技有限公司

彩虹小插画&#xff1a;色彩斑斓的梦幻世界 在繁忙的生活节奏中&#xff0c;总有一抹温柔的色彩能悄然触动心弦&#xff0c;那就是彩虹小插画带来的梦幻与宁静。彩虹&#xff0c;这一自然界的奇迹&#xff0c;被艺术家们巧妙地融入小巧精致的插画之中&#xff0c;不仅捕捉了瞬…