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

数据结构（九）——排序

news 来源：原创 2025/6/25 5:49:10

一、排序的基本概念

1.排序：重新排列表中的元素，使表中的元素满足按关键字有序

2.稳定性：Ri和Rj相对位置保持不变

3.内部排序：指在排序期间元素全部存在内存中的排序（比较和移动），如插入排序、交换排序、选择排序、归并排序和基数排序

4.外部排序：指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据
要求不断地在内，外存之间移动的排序

eg：内部排序方法的稳定性是指该排序算法不允许有相同的关键字记录（×）

二、插入排序

基本思想：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成

1.直接插入排序

代码实现：

void InsertSort(ElemType A[],int n){int i,j;for(i=2;i<=n;i++){if(A[i]<A[i-1]){A[0]=A[i];for(j=i-1;A[0]<A[j];--j){A[j+1]=A[j];}A[j+1]=A[0];}}
}

空间效率：O(1)

时间效率：O(n^2)

稳定性：稳定

2.希尔排序

把相隔某个增量的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈基本有序时，再对全体记录进行一次直接插入排序

空间效率：O(1)

时间效率：不确定

稳定性：不稳定

eg：（B）方法是从未排序的序列中挑选元素，并将其放入已排序序列的一种

A.归并排序 B.插入排序 C.快速排序 D.选择排序

eg：用希尔排序法对关键字序列{20,25,12,47,15,83,30,76}进行排序时，增量为3的一趟排序结果是：20 15 12 30 25 83 47 76

三、交换排序

1.冒泡排序

基本思想是：从后往前(或者从前往后)两两比较相邻元素的值，若为逆序则进行交换，直到序列比较完，第一趟冒泡结束，结果是将最小的元素交换到待排序列的第一个位置(或将最大的元素交换到待排序列的最后一个位置)

代码实现：

void BubbleSort(ElemType A[],int n){for(i=0;i<n-1;i++){flag=false;for(j=n-1;j>i;j--){if(A[j-1]>A[j]){swap(A[j-1],A[j]);flag=true;}}if(flag==false){return;}}
}

空间效率：O(1)

时间效率：O(n^2)

稳定性：稳定

eg：对于n个不同的关键字由小到大进行冒泡排序，在下列（B）情况下交换的次数最多

A.从小到大排列好的 B.从大到小排列好的 C.元素无序 D.元素基本有序

2.快速排序

基本思想是:在待排序表L[1,…,n]中任取一个元素 pivot 作为枢轴(通常取首元素)通过一趟快速排序将待排序表划分为独立的两部分[1,…,k-1]和[k+1,…,n]，pivot放在了最终位置L[k]中

eg：对关键字序列{49，38，65，97，76，13，27，49'}进行快速排序

空间效率：O(log2n)

时间效率：O(nlog2n)

稳定性：不稳定

快速排序是所有内部排序算法中平均性能最优的排序算法

快速排序并不适用于原本有序或基本有序的记录序列进行排序

四、习题

答案：√

答案：B

答案：49 13 27 50 76 38 65 97

答案：4

答案：O(n^2);O(n)

答案：C

答案：

第 1 趟：(71, 52, 22, 15, 30, 3, 77)
第 2 趟：(52, 22, 15, 30, 3, 71, 77)
第 3 趟：(22, 15, 30, 3, 52, 71, 77)
第 4 趟：(15, 22, 3, 30, 52, 71, 77)
第 5 趟：(15, 3, 22, 30, 52, 71, 77)
第 6 趟：(3, 15, 22, 30, 52, 71, 77)

答案：D

答案：

初始：(29, 18, 25, 47, 58, 12, 51, 10)
第 1 趟：(12, 18, 25, 10, 29, 58, 51, 47)
第 2 趟：(10, 12, 25, 18, 29, 58, 51, 47)
第 3 趟：(10, 12, 18, 25, 29, 58, 51, 47)
第 4 趟：(10, 12, 18, 25, 29, 47, 51, 58)
第 5 趟：(10, 12, 18, 25, 29, 47, 51, 58)

数据结构（九）——排序

一、排序的基本概念 1.排序：重新排列表中的元素，使表中的元素满足按关键字有序 2.稳定性：Ri和Rj相对位置保持不变 3.内部排序：指在排序期间元素全部存在内存中的排序（比较和移动），如插入排序…...

编程日记 2025/6/25 5:49:10

MinerU安装(pdf转markdown、json)

在Windows上安装MinerU，参考以下几个文章，可以成功安装，并使用GPU解析。整体安装教程： MinerU本地化部署教程——一款AI知识库建站的必备工具其中安装conda的教程： 一步步教你在 Windows 上轻松安装 Anaconda以及使…...

编程日记 2025/6/22 17:00:23

Spring框架核心技术深度解析：JDBC模板、模拟转账与事务管理

一、JDBC模板技术：简化数据库操作在传统JDBC开发中，繁琐的资源管理和重复代码一直是开发者的痛点。Spring框架提供的 JDBC模板（JdbcTemplate) 彻底改变了这一现状，它通过封装底层JDBC操作，让开发者仅需关注SQL逻辑&a…...

编程日记 2025/6/20 5:28:48

LCD电视LED背光全解析：直下式 vs 侧光式、全局调光 vs 局部调光与HDR体验

Abstract: This article explores the various types of LED backlighting used in televisions and monitors. It categorizes backlight systems based on structural design—direct-lit and edge-lit—as well as by dimming technology—global dimming and local dimmin…...

编程日记 2025/6/20 15:46:40

ET EntityRef EntityWeakRef 类分析

EntityRef EntityWeakRef 相同点也是这两个的作用：这两个都是用来表示一个实体引用。一般来说使用一个对象，直接持有对象就可以，但是如果对象来自于对象池，这个时候直接持有对象不合适，对象可能已经被对象池回收&…...

编程日记 2025/6/20 17:18:23

Python----神经网络（基于DNN的风电功率预测）

一、基于DNN的风电功率预测 1.1、背景在全球能源转型的浪潮中，风力发电因其清洁和可再生的特性而日益重要。然而，风力发电功率的波动性给电网的稳定运行和能源调度带来了挑战。准确预测风力发电机的功率输出，对于优化能源管理、提高电网可靠…...

编程日记 2025/6/24 15:53:30

Web前端入门：JavaScript 的应用领域

截至目前，您应该对前端的 HTML CSS 应该有了很清楚的认知，至少实现一个静态网页已经完全不在话下了。当然，CSS 功能绝不止这些，一些不太常用的 CSS 相关知识，后续将通过案例进行分享。那么咱们接下来看看 JavaScrip…...

编程日记 2025/6/20 8:18:39

实用工具：微软软件PowerToys（完全免费），实现多台电脑共享鼠标和键盘（支持window系统）

实用工具：微软软件 PowerToys 让多台电脑共享鼠标和键盘在如今的数字化办公与生活场景中，我们常常会面临同时使用多台电脑的情况。例如，办公时可能一台电脑用于处理工作文档，另一台用于运行专业软件或查看资料；家庭环…...

编程日记 2025/6/22 23:02:04

精益数据分析（61/126）：移情阶段评分体系构建与实战案例解析

精益数据分析（61/126）：移情阶段评分体系构建与实战案例解析在创业的移情阶段，如何科学评估用户需求的真实性与紧迫性，是决定后续产品方向的关键。今天，我们结合《精益数据分析》中的评分框架，…...

编程日记 2025/6/25 0:01:25

面试题：介绍一下JAVA中的反射机制

什么是反射机制？ Java反射机制是指在运行状态中，对于任意一个类，都能够知道这个类的所有属性和方法；对于任意一个对象，都能够调用它的任意方法和属性。这种动态获取的信息以及动态调用对象的方法的功能称为Java语言的…...

编程日记 2025/6/25 5:18:10

yarn任务筛选spark任务，判断内存/CPU使用超过限制任务

yarn任务筛选spark任务，判断内存/CPU使用超过限制任务 curl -s “http://it-cdh-node01:8088/ws/v1/cluster/apps?statesRUNNING” | jq ‘select(.apps.app[].applicationType “SPARK”) | .apps.app[].id’ | xargs -I {} curl -s “http://it-cdh-node01:808…...

编程日记 2025/5/31 8:46:30

ArcGIS Pro地块图斑顺序编号（手绘线顺序快速编号）-004

ArcGIS全系列实战视频教程——9个单一课程组合系列直播回放_arcgis初学者使用视频-CSDN博客 4大遥感软件！遥感影像解译！ArcGISENVIErdaseCognition_遥感解译软件-CSDN博客今天介绍一下在ArcGIS Pro地块图斑顺序编号（手绘线顺序快速编号&am…...

编程日记 2025/5/16 7:59:57

红黑树解析

目录一、引言二、红黑树的概念与性质 2.1 红黑树的概念 2.2 红黑树的性质三、红黑树的节点定义与结构 3.1 节点定义四、红黑树的插入操作 4.1 插入步骤 4.2 插入代码实现五、红黑树的验证 5.1 验证步骤 5.2 验证代码实现六、红黑树迭代器的实现 6.1 迭代器的…...

编程日记 2025/6/20 12:25:05

在线文档管理系统 spring boot➕vue｜源码+数据库+部署教程

📌 一、项目简介本系统采用Spring Boot Vue ElementUI技术栈，支持管理员和员工两类角色，涵盖文档上传、分类管理、公告发布、员工资料维护、部门岗位管理等核心功能。系统目标是打造一个简洁高效的内部文档管理平台，便于员工…...

编程日记 2025/6/21 1:32:26

Python3 简易DNS服务器实现

使用Python3开发一个简单的DNS服务器，支持配置资源记录(RR)，并能通过dig命令进行查询。让自己理解DNS原理实现方案我们将使用socketserver和dnslib库来构建这个DNS服务器。dnslib库能帮助我们处理DNS协议的复杂细节。 1. 安装依赖首先确保安装了d…...

编程日记 2025/6/25 20:39:49

雾锁王国开服联机教程-专用服务器

一。阿里云服务器搭建服务器地址：1分钟畅玩！一键部署联机服务器《雾锁王国（Enshrouded）》融合了生存、制作以及动作 RPG 战斗，游戏背景设定在了一个基于体素构筑的辽阔大陆。无论是攀登山脉还是跨越沙漠&#xff0…...

编程日记 2025/6/25 14:45:16

鸿蒙OSUniApp 开发的一键分享功能#三方框架 #Uniapp

使用 UniApp 开发的一键分享功能在移动应用开发中，分享功能几乎是必不可少的一环。一个好的分享体验不仅能带来更多用户，还能提升产品的曝光度。本文将详细讲解如何在 UniApp 框架下实现一个简单高效的一键分享功能，适配多个平台。各平台分…...

编程日记 2025/6/20 13:44:31

Hive PredicatePushDown 谓词下推规则的计算逻辑

1. PredicatePushDown 谓词下推谓词下推的处理顺序是先处理子节点的操作，子节点都处理完，然后处理父节点。 select web_site_sk from (select web_site_sk,web_name from web_site where web_cityPleasant Hill ) t where web_name <> site_…...

编程日记 2025/6/20 20:25:23

2024东北四省ccpc

F题解题思路数论有限小数的条件 p q \frac{p}{q} qp 在 k k k 进制下是有限小数，当且仅当 q q q 的所有质因数都是 p p p 或 k k k 的质因数。即，若 q q q 的质因数分解为 q ∏ i p i a i q \prod_{i} p_i^{a_i} q∏ipiai&#x…...

编程日记 2025/6/22 16:46:00

【C语言】初阶数据结构相关习题（二）

🎆个人主页：夜晚中的人海今日语录：知识是从刻苦劳动中得来的，任何成就都是刻苦劳动的结果。——宋庆龄文章目录 🎄一、链表内指定区间翻转🎉二、从链表中删去总和值为零的节点🚀三、链表求和&…...

编程日记 2025/6/25 23:30:57

DeepSeek执行流程加速指南：跨框架转换与编译优化的核心策略全解析

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。推荐:kwan 的首页,持续学…...

编程日记 2025/6/24 23:14:23

解决 Conda 安装 PyTorch 1.1.0 报错：excluded by strict repo priority（附三种解决方案）

# 💥解决 Conda 安装 PyTorch 1.1.0 报错问题：excluded by strict repo priority在使用旧版本 PyTorch（例如 1.1.0）时，有些开发者会遇到以下 conda 安装报错：LibMambaUnsatisfiableError: package pytorch-…...

编程日记 2025/5/28 16:26:51

面试从微前端拓展到iframe是如何通信的

一、跨域通信 1、父页面发消息给 iframe const iframe document.getElementById(myIframe); iframe.contentWindow.postMessage(form parent, https://iframe-domain.com)// iframe 接收 window.addEventListener(message, (event) > {if (event.origin ! https://paren…...

编程日记 2025/6/25 22:14:56

PyTorch循环神经网络（Pytotch）

文章目录循环神经网络（RNN）简单的循环神经网络长短期记忆网络（LSTM）门控循环单元（GRU） 循环神经网络（RNN） 循环神经网络（RecurrentNeuralNetwork，RNN&#…...

编程日记 2025/6/20 22:13:07

django中用 InforSuite RDS 替代memcache

在 Django 项目中，InforSuite RDS（关系型数据库服务）无法直接替代 Memcached，因为两者的设计目标和功能定位完全不同： 特性MemcachedInforSuite RDS核心用途高性能内存缓存，临时存储键值对数据持久化关系型…...

编程日记 2025/6/24 9:08:23

Git 常用命令详解

Git 常用命令详解（含详细示例） 本文整理了 Git 日常使用中最常用的命令，适合初学者和日常查阅，如有错误，敬请指正，谢谢！ ☁️ Git 使用流程入门（从 pull 和 push 开始） …...

编程日记 2025/6/24 20:08:33

AI、机器学习、深度学习：一文厘清三者核心区别与联系

AI、机器学习、深度学习：一文厘清三者核心区别与联系前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，可以分享一下给大家。点击跳转到网站。 https://www.captainbed.cn/ccc 前言在人工智能技术席卷全球的今天&…...

编程日记 2025/6/20 20:09:14

《数字藏品社交化破局：React Native与Flutter的创新实践指南》

NFT，这种非同质化代币，赋予了数字资产独一无二的身份标识，从数字艺术作品到限量版虚拟物品，每一件NFT数字藏品都承载着独特的价值与意义。当React Native和Flutter这两大跨平台开发框架遇上NFT数字藏品，一场技术与创意…...

编程日记 2025/5/16 7:55:40

工业操作系统核心技术揭秘

摘要随着工业 4.0 与智能制造的深入推进，工业操作系统作为工业数字化转型的核心支撑，其技术发展备受关注。本文深入剖析工业操作系统的核心技术，包括实时性保障机制、硬件抽象层设计、多任务管理策略等，结合技术原理与实际应用场…...

编程日记 2025/6/24 14:31:43

Python logging模块使用指南

Python 的 logging 模块是一个灵活且强大的日志记录工具，广泛应用于应用程序的调试、运行监控和问题排查。它提供了丰富的功能，包括多级日志记录、多种输出方式、灵活的格式配置等。以下是详细介绍： 一、为什么使用 logging 模块？…...

编程日记 2025/6/24 21:25:02

沃伦森智能无功补偿系统解决电力电容器频繁投切的隐患

在现代电力系统中，无功补偿设备的稳定运行直接影响电网质量。然而，电力电容器的频繁投切问题长期存在，如同电网的“慢性病”，不仅加速设备老化，还可能引发系统性风险。作为电力电子领域的领军企业，沃伦森电…...

编程日记 2025/6/22 15:42:59

【HarmonyOS 5】鸿蒙mPaaS详解

【HarmonyOS 5】鸿蒙mPaaS详解一、mPaaS是什么？ mPaaS 是 Mobile Platform as a Service 的缩写，即移动开发平台。蚂蚁移动开发平台mPaaS ，融合了支付宝科技能力，可以为移动应用开发、测试、运营及运维提供云到端的一站式解决…...

编程日记 2025/6/24 22:12:57

PyTorch中.item()函数：提取单元素张量值

PyTorch中，.item()函数是什么在PyTorch代码中，.item() 主要用于从一个只包含单个元素的张量（Tensor）中提取出对应的Python标量值，具体作用和使用场景如下：作用获取数值：当通过计算得到一个张量，且该张量仅包含一个元素时，使用 .item() 方法可以方便地将这个元素…...

编程日记 2025/6/23 20:52:21

PyTorch LSTM练习案例：股票成交量趋势预测

文章目录案例介绍源码地址代码实现导入相关库数据获取和处理搭建LSTM模型训练模型测试模型绘制折线图主函数绘制结果案例介绍本例使用长短期记忆网络模型对上海证券交易所工商银行的股票成交量做一个趋势预测，这样可以更好地掌握股票买卖点，从而提高…...

编程日记 2025/6/22 22:13:01

ARM A64 LDR指令

ARM A64 LDR指令 1 LDR (immediate)1.1 Post-index1.2 Pre-index1.3 Unsigned offset 2 LDR (literal)3 LDR (register)4 其他LDR指令变体4.1 LDRB (immediate)4.1.1 Post-index4.1.2 Pre-index4.1.3 Unsigned offset 4.2 LDRB (register)4.3 LDRH (immediate)4.3.1 Post-index…...

编程日记 2025/6/22 16:13:43

相关文章：