当前位置: 首页 > news >正文

【算法与数据结构】关于排序的问题思考

文章目录

    • 引言
    • 不断的插入值,并保证序列是递增的。
    • Python中sort()和sorted()的区别是啥?
    • sorted 函数如何使用?
    • 问题: 如何返回排序之后的索引
    • 问题:排序的稳定性
    • 问题,寻找第K大的元素的算法。
    • 引出一个算法题;
    • 参考资料

引言

突然想写一个关于排序问题的文章。笔者在初学算法的时候,总是会忽略排序算法。 当时的想法是这样的,排序算法既枯燥,有无聊; 一方面,我已经知道了冒泡排序的原理, 能写出一个简单的排序算法,差不多就行啦,对于快速排序,又有点复杂, 就算时间复杂度低一点,对我的作用也不是太大,因此总是不把排序算法放在心上。后来在刷算法题目的时候,逐渐意识到了一些关于排序算法的有趣问题,于是想在这里总结一下, 主要还是基于Python语言。

简单说一下我遇到的关于排序问题的场景:

不断的插入值,并保证序列是递增的。

假设有这样的场景:
我有一个二维列表dev_list, 列表中的元素为[a,b,c], 二维列表在迭代的过程中不断添加元素,想保证这个二维列表按照元素c为基准进行降序排列。

  • 方案一: 从后往前插入元素,不断比较, 找到合适的位置插入(第一个大于自己的位置, 插入到这个位置的后面)
    另一个思路: 从前往后插入元素, 不断比较, 找到第一个小于自己的位置,插入到这个位置
# 如果dev_list 为空,则插入一个元素,作为哨兵# 插入元素为 ele: [a,b,c]
... 上面是迭代的代码for i in range(len(dev_list)):if ele[2] > dev_list[i][2]:dev_list.insert(i, ele)break
  • 方案二:如果只是一维列表的插入,我们可以采用方案一的遍历,但是这样的复杂度是O(n), 已知的列表是有序的,我们可以采用二分法来插入, 这样的实际复杂度是 O(log2n),python中有个很好用的函数bisect, 注意,bisect这仅对升序有效。
先学习一下bisect 的用法
bisect.bisect_left(a,x)
在a中找到x合适的插入点。返回的插入点 i 将数组 a 分成两半,使得 all(val < x for val in a[lo : i]) 在左半边而 all(val >= x for val in a[i : hi]) 在右半边。bisect.bisect_right(a, x)
bisect.bisect(a,x)
插入点在右边,对于相同元素。bisect.insort_right(a,x)
bisect.insort(a,x)
先定位一个插入点, 再插入使用实例: 
#在m_list 列表中维护一个升序的数组。
dev_list.insort(m_list, ele)
  • 方案三: 先插入元素,再对列表进行排序, 这个复杂度就比较高了。 但是这个的实用性还是很强的(不考虑复杂度的情况下,一行代码就搞定了)。
L.append(ele)
以第二个元素为键值进行排序。result = sorted(L, key=lambda x:x[2])# 多维度比较
result = sorted(L, key=lambda x:(x[0], -x[1]))

Python中sort()和sorted()的区别是啥?

  1. sort()方法必须由于list对象调用, sorted()方法的参数是所有的可迭代对象
  2. sorted()方法是新生成一个列表对象
    总的来说,sorted()这个方法笔者应用的比较多。

sorted 函数如何使用?

sorted(iterable, cmp=None, key=None, reverse=False)

cmp遵守的规则: 大于返回1, 小于返回-1, 等于返回0

  1. sorted(a), 直接对a 进行排序。

  2. 如何使用cmp ? 后面可以带一个lambda表达式,有两个参数, 是从可迭代对象中取出的值, 这个函数可以自己定义,不过要符号要求。

L=[('b',2),('a',1),('c',3),('d',4)]
result = sorted(L, cmp=lambda x, y:cmp(x[1],y[1]))
  1. 如何使用key
sorted(L, key=lambda x:x[1])
  1. reverse=True 表示的是降序排序。

  2. 给出一个案例: 对tuple进行排序,先按照第一个元素升序,如果第一个元素相同,再按照第二个元素降序排列。

L = [(12, 12), (34, 13), (32, 15), (12, 24), (32, 64), (32, 11)]
L.sort(key=lambda x: (x[0], -x[1]))
result = sorted(L, key=lambda x: (x[0], -x[1]))
print(L)
  1. python 如何自定义排序

在 Python 中,通过实现类的特殊方法 lt (即“小于”运算符) 可以实现自定义排序。这个方法定义了该类的实例如何与其他实例进行比较,例如在使用 sorted 函数对该类的实例进行排序时。

以下是一个例子:

class Person:
def init(self, name, age):
self.name = name
self.age = age

def __lt__(self, other):return self.age < other.age

这个类表示一个人,其中包含姓名和年龄属性。在 lt 方法中,我们定义了一个比较规则,即以年龄大小作为比较标准。这个方法返回 True 或 False,告诉 Python 如何比较两个实例。

笔者一开始疑惑为什么只定义小于,不定义等于这个判断,想了一下,这个是不需要的。 因为我们在比较的时候,只会遇到这两种情况, 要么小于,执行交换,要么就大于等于,不执行交换。

现在我们可以创建几个 Person 实例,并使用 sorted 函数进行排序:

p1 = Person(“Alice”, 25)
p2 = Person(“Bob”, 30)
p3 = Person(“Charlie”, 20)

people = [p1, p2, p3]
sorted_people = sorted(people)

for person in sorted_people:
print(person.name, person.age)

运行结果:

Charlie 20
Alice 25
Bob 30

如你所见,sorted 函数按照我们定义的规则对 Person 实例进行排序。这个例子中只使用了一个比较规则,但你可以根据需要定义多个规则来实现更复杂的排序方式。

需要注意的是,如果两个实例的比较结果相同,Python 还会使用默认的比较规则来决定它们的顺序。因此,不同的比较规则可能会产生不同的排序结果。

问题: 如何返回排序之后的索引

有的时候,我们在解决问题的时候,不一定需要直接排序后的结果,而是想求得排序之后对应的索引, 这里我们集中讨论下。

  • 考虑对一维数组排序,并返回索引
    方法一: 使用numpy中的函数argsort()
import numpy as np
nums = [4, 1, 5, 2, 9, 6, 8, 7]
print(np.argsort(nums))

方法二: 使用enumerate

nums = [4, 1, 5, 2, 9, 6, 8, 7]
sorted_nums = sorted(enumerate(nums), key=lambda x: x[1])
idx = [i[0] for i in sorted_nums]
nums = [i[1] for i in sorted_nums]

这种是python原生支持的, 不需要引入任何依赖库, 比较实用。

  • 当然, 我们也可能会遇到一个对象列表,想对其进行排序后并返回索引。
    思路也是比较简单, 我们可以使用sorted函数, 先按照一定规则对对象进行排序,然后返回一个对象列表,最后直接遍历返回后的有序列表的对象索引就可以了。

问题:排序的稳定性

在这里,我们简单聊一聊排序的稳定性。
什么是排序的稳定性, 其实就是说,在待排序的数组中, 值相同的元素在排序之后的相对位置不变。

快排的核心思想:
选择一个基础值, 两个指针都移动,保证小于基础值的数在左边, 大于基础值的数在右边。

快排不稳定的原因: 如果有两个相同的值比基础值小, 那么它会与前面第一个比基础值大的值进行位置交换, 这个时候就会引起相同值的相对位置变化, 也就是排序不稳定

思考一下我们的冒泡排序, 在交换位置的时候, 相同值的相对位置是不会变化的。 要移动都会相对移动,要静止都会相对静止。

问题,寻找第K大的元素的算法。

参考资料:
https://www.jianshu.com/p/33ee33ce8699

  1. 排序法

  2. 插入法

  3. 小顶堆法

  4. 快速排序法。
    这里贴一个快速排序的改进算法来求解第K大的元素。

public static int partition(int[] array, int left, int right) {int k = array[left];int i = left;int j = right;while (j > i) {while (array[j] < k && j > i) {j--;}if (j > i) {array[i] = array[j];i++;}while (array[i] > k && j > i) {i++;}if (j > i) {array[j] = array[i];j--;}}array[i] = k;return i;
}public static void quickSort(int[] array, int left, int right) {if (left >= right) {return;}int i = partition(array, left, right);quickSort(array, left, i - 1);quickSort(array, i + 1, right);
}public static int findK(int[] array, int left, int right, int k) {int i = partition(array, left, right);if (i == k - 1) {return array[k - 1];} else if (i > k - 1) {return findK(array, left, i - 1, k);} else if (i < k - 1) {return findK(array, i + 1, right, k);}return 0;
}

引出一个算法题;

https://leetcode.cn/problems/minimum-size-subarray-sum/comments/

长度最小的子数组。

https://leetcode.cn/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/

参考资料

https://blog.csdn.net/y12345678904/article/details/77507552

相关文章:

【算法与数据结构】关于排序的问题思考

文章目录引言不断的插入值&#xff0c;并保证序列是递增的。Python中sort()和sorted()的区别是啥&#xff1f;sorted 函数如何使用&#xff1f;问题&#xff1a; 如何返回排序之后的索引问题&#xff1a;排序的稳定性问题&#xff0c;寻找第K大的元素的算法。引出一个算法题&am…...

行为型模式-命令模式

行为型模式-命令模式命令模式&#xff08;Command&#xff09;解决命令执行问题描述适用环境优点&#xff1a;缺点&#xff1a;违反原则&#xff1a;代码实现命令模式&#xff08;Command&#xff09; 解决命令执行问题 描述 将一个请求封装为一个对象&#xff0c;并定义该对…...

SHELL综合练习1

文章目录1、编写函数&#xff0c;实现打印绿色OK和红色FAILED 判断是否有参数&#xff0c;存在为Ok&#xff0c;不存在为FAILED2、 编写函数&#xff0c;实现判断是否无位置参数&#xff0c;如无参数&#xff0c;提示错误3、编写函数实现两个数字做为参数&#xff0c;返回最大值…...

ROS开发之如何使用发布者、订阅者和话题消息?

文章目录0、引言1、创建发布者&#xff08;velocity发布者 →geometry话题消息→turtlesim订阅者&#xff09;2、创建订阅者&#xff08;turtlesim发布者→turtlesim话题消息→pose订阅者&#xff09;3、自定义话题消息4、使用自定义话题消息&#xff08;person发布者→自定义话…...

基于Java+Springboot+vue高校资源共享交流平台设计和实现

博主介绍&#xff1a;✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专…...

收藏! 38个Python数据科研库

通用的数据科学库&#xff0c;即那些可能被数据科学领域的从业人员用于广义的&#xff0c;非神经网络的&#xff0c;非研究性工作的库&#xff1a; 数据-用于数据管理&#xff0c;处理和其他处理的库 数学-虽然许多库都执行数学任务&#xff0c;但这个小型库却专门这样做 机…...

SpringBoot过滤器获取Bean-请求重复可读-获取请求体数据-用户IP归属地获取

文章目录一.获取Bean二. Request重复可读三. 过滤器获取Body请求体数据四.用户ip获取一.获取Bean 网上一些论调说Filter无法注入Bean的原因是加载顺序: listener—>filter—>servlet导致的.我不赞同. 原因:默认机制下&#xff0c;在SpringBoot应用启动时&#xff0c;IOC…...

有哪些特别小众而有趣的编程语言呢?

相对较小众的编程语言&#xff0c;还要有趣&#xff1f;发表一些个人看法&#xff0c;如果不对大家口味&#xff0c;大家轻喷&#xff0c;留情留情。 Rust&#xff1a;Rust是一种系统编程语言&#xff0c;致力于提供高性能、可靠性和安全性。Rust具有内存安全和线程安全的特性&…...

vue中使用高德

首先我们要申请高德地图的key&#xff0c;当前升级过后高德地图使用也需要加上安全秘钥 注册账号 访问高德地图开发平台根据实际情况填写就可以&#x1f35c;&#xff08;实名认证的时候选择个人就可以&#xff0c;如果是企业级的项目&#xff0c;可能会涉及人员变动&#xf…...

React class组件和hooks setState异步更新数据详解

一、 class组件setState详解 1.class组件setState异步更新数据详解 class Father extends React.Component{state {num:0}addHandler () > { this.setState({num: 100})console.log(state中的值,this.state.num)}render() { return (<div><button onClick{this…...

ToBeWritten之嵌入式操作系统

也许每个人出生的时候都以为这世界都是为他一个人而存在的&#xff0c;当他发现自己错的时候&#xff0c;他便开始长大 少走了弯路&#xff0c;也就错过了风景&#xff0c;无论如何&#xff0c;感谢经历 转移发布平台通知&#xff1a;将不再在CSDN博客发布新文章&#xff0c;敬…...

git 实际开发中使用-解决问题

前言 git代码版本管理工具&#xff0c;打破常规的物理传输&#xff0c;更新&#xff0c;合并&#xff0c;回滚提高了开发效率和可追溯性。 网上的资料会把所有的命令都很全也很多&#xff0c;导致对刚刚了解的同学不友好&#xff0c;很难实际使用。 每个人都有自己使用git的习…...

新星计划·2023-第1期 - Python赛道报名入口 -〖你就是下一个新星〗

↓↓↓报名方式&#xff1a;&#xff08;下滑到本页面底部&#xff09;重要提醒&#xff1a;这里是 新星计划2023-第1期 - Python赛道报名入口&#xff0c;一经报名&#xff0c;不可更换。报名入口点击此处跳转 一、新星计划 新星计划是一个以发掘潜力新人、培养优质博主为目…...

Android LowMemoryKiller概述

Agenda Low memory killer 概述 内核空间LMK ULMK‐vmpressure ULMK‐PSI Low memory killer 概述 lowmemorykiller的作用就是当内存比较紧张的时候去及时杀掉一些对用户来说不那么重要的进程&#xff0c;回收内存&#xff0c;保证手机的正常运行。安卓平台lowmemorykiller机…...

特殊操作流——案例:游戏次数

需求&#xff1a;请求程序实现猜数字小游戏只能试玩三次&#xff0c;如果还想玩&#xff0c;提示&#xff1a;游戏已经结束&#xff0c;想玩请充值&#xff08;www.itcast.cn&#xff09; 思路&#xff1a; 写一个游戏类&#xff0c;里面有一个猜数字的小游戏 写一个测试类&am…...

git clone connect to gitlab sign in token弹窗让我输入用户名和密码

系列文章目录 文章目录系列文章目录前言前言 当我使用git bash输入命令&#xff1a;git clone https://gitlab.freedesktop.org/raqm/raqm.git libraqm 弹窗 ASUSLAPTOP-0R30I78P MINGW64 /e/krita-dev $ git clone https://gitlab.freedesktop.org/raqm/raqm.git libraqm C…...

【Blender】如何在Blender中添加HDRI环境贴图

​ 什么是HDRI环境贴图 环境贴图或HDRI贴图是在Blender中照亮3D场景并实现逼真效果的最有效和最快捷的方法之一。 HDRIs本质上是现实世界照明的快照&#xff0c;其中包含高动态范围成像&#xff08;HDRI&#xff09;的准确照明细节。HDRI是一个包含亮度信息&#xff08;从暗…...

前端监控指的是什么?

前端监控分为三个方面&#xff1a; 异常监控&#xff08;监控前端页面的报错&#xff09;性能监控&#xff08;监控页面的性能&#xff09;用户行为监控&#xff08;监控用户的行为&#xff0c;计算PV、UV、在线时间等、数据监控即我们常说的埋点 例子1 在后端突然上线了某个需…...

.net core 面试题 2023

文章目录1. 什么是 ASP.net core2. .net 术语3. 托管资源 和 非托管资源4. GC 和 垃圾回收5. .net中所有类的基类6. 如何实现对象的深拷贝7. 依赖注入&#xff0c;为什么使用依赖注入8. IOC容器的注入方法9. ASP.net core 中 服务生命周期10. scoped的 service 可以注入到 sing…...

和ChatGPT关于Swing music的一场对话(上篇)

什么是 Swing Music &#xff1f; Swing Music 是一款漂亮的自托管音乐播放器&#xff0c;适用于您的本地音频文件。就像一个更酷的 Spotify …但带上你自己的音乐。 第一次在 reddit 上看到 Swing Music&#xff0c;就被其 UI 吸引了 但源码站点的releases 中只有 windows 和 …...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...