排序算法入门：分类与基本概念详解
引言
排序是编程世界中最常见的操作之一，也是许多算法的基础。不管是从数据中找出最大值还是将一堆乱序的名字整理得井井有条，排序算法都在幕后默默工作。你可能会觉得排序很简单：从小到大排个序而已嘛。但当数据量大到上百万、上亿，甚至更高的时候，如何高效排序就变成了一件技术活。
这篇文章将带你了解排序算法的基本概念、分类方法，以及它们的优缺点和适用场景。通过这篇文章，你将对排序有一个全面的认知，为后续学习具体算法做好铺垫。
一、 排序的基本概念
排序（Sorting）是指将一组数据按照某种规则排列起来的过程。这个规则通常是：
- 从小到大排序（升序）
- 从大到小排序（降序）
比如，我们有一组数字：[5, 2, 9, 1, 7]，按照升序排序后变成：[1, 2, 5, 7, 9]。
排序的意义在于让数据更容易使用，比如：
- 数据查找：排序后的数据可以用二分查找快速找到目标。
- 数据分析：排序可以帮助我们快速找出最大值、最小值、或计算中位数。
二、 排序算法的分类
排序算法有多种分类方法，根据不同的特点，可以分为以下几类：
按算法的稳定性分类
1. 稳定排序
如果两个相等的元素在排序后依然保持原来的相对顺序，则该算法是稳定的。
常见稳定排序算法：
- 冒泡排序
- 插入排序
- 归并排序
- 计数排序
2. 不稳定排序
如果两个相等的元素在排序后可能改变原来的相对顺序，则该算法是不稳定的。
常见不稳定排序算法：
- 选择排序
- 快速排序
- 堆排序
稳定排序在一些对顺序敏感的场景（比如多关键字排序）中很重要。
按时间复杂度分类
排序算法的效率通常用时间复杂度来衡量：
- O(n²)算法（适合小规模数据）：
- 冒泡排序、选择排序、插入排序
- O(n log n)算法（适合大规模数据）：
- 快速排序、归并排序、堆排序
- O(n)算法（适合特殊场景）：
- 计数排序、桶排序、基数排序
按排序方式分类
1. 内部排序
所有数据都加载到内存中进行排序。适用于数据量较小的情况。
常见算法：冒泡排序、快速排序、堆排序。
2. 外部排序
数据量大到无法全部加载到内存，需要借助外存（如硬盘）进行排序。
常见算法：多路归并排序。
三、排序算法的评价标准
在实际选择排序算法时，通常从以下几个方面进行评价：
1. 时间复杂度
排序的效率用时间复杂度衡量：
- 最好情况：输入数据已接近有序。
- 最坏情况：输入数据完全无序。
- 平均情况：输入数据的随机分布。
2. 空间复杂度
排序算法在运行时需要额外的存储空间：
- 原地排序：只需常数级别的额外空间（如插入排序）。
- 非原地排序：需要额外的存储空间（如归并排序）。
3. 稳定性
是否保持相等元素的相对顺序？这决定了算法是否能用在多关键字排序中。
4. 简单性
算法实现的复杂程度。某些算法（如快速排序）虽然效率高，但实现起来较复杂。
四、常见排序算法概览
以下是几种常见排序算法的简单介绍，为后续深入学习具体算法做铺垫：
| 排序算法 | 时间复杂度（平均） | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 稳定 | 数据量小、初学者入门 |
| 选择排序 | O(n²) | O(1) | 不稳定 | 数据量小，对稳定性无要求 |
| 插入排序 | O(n²) | O(1) | 稳定 | 数据量小，数据部分有序 |
| 快速排序 | O(n log n) | O(log n) | 不稳定 | 大规模数据，对时间效率要求高 |
| 归并排序 | O(n log n) | O(n) | 稳定 | 大规模数据，对稳定性有要求 |
| 堆排序 | O(n log n) | O(1) | 不稳定 | 大规模数据，对内存占用要求低 |
| 计数排序 | O(n+k) | O(n+k) | 稳定 | 数据范围有限的场景 |
五、总结
在这篇文章中，我们了解了排序的基本概念、分类方法和评价标准，并简单介绍了一些常见的排序算法。排序不仅是编程中的基础操作，也是许多复杂算法的核心模块。掌握排序算法，是学习数据结构与算法的必经之路。
下一步，我们将从基础排序算法开始，深入剖析冒泡排序、选择排序和插入排序的原理与实现，敬请期待！
相关文章：
排序算法入门：分类与基本概念详解
引言 排序是编程世界中最常见的操作之一，也是许多算法的基础。不管是从数据中找出最大值还是将一堆乱序的名字整理得井井有条，排序算法都在幕后默默工作。你可能会觉得排序很简单：从小到大排个序而已嘛。但当数据量大到上百万、上亿…...
【Spring Cloud 微服务的简单概述】
🎥博主：程序员不想YY啊 💫CSDN优质创作者，CSDN实力新星，CSDN博客专家 🤗点赞🎈收藏⭐再看💫养成习惯 ✨希望本文对您有所裨益，如有不足之处，欢迎在评论区提出…...
稳定运行的以Azure Synapse Dedicated SQL Pool数据仓库为数据源和目标的ETL性能变差时提高性能方法和步骤
在Azure Synapse Dedicated SQL Pool（以前称为SQL Data Warehouse）的ETL性能变差时，可以通过以下方法和步骤来提高性能： 1. 分析和监控性能瓶颈 查看执行计划：使用SQL的SET STATISTICS IO ON和SET STATISTICS TIME O…...
可供参考的GitHub国内镜像
在配置了本地hosts文件和魔法后仍存在无法访问的问题 针对如上问题，可以使用国内的镜像地址做替换 例如: https://github.com/bubbliiiing/detr-pytorch改成 https://hub.nuaa.cf/bubbliiiing/detr-pytorch推荐使用的镜像 https://hub.yzuu.cf/ https://hub.nua…...
统计中间件稳定性指标
目前订单业务域涉及中间件：MySQL、Redis、TiDB、MQ、ES。（遗漏项请补充） 一、RDS 资源使用率 实例ID实例名称规格maxCPUavgCPUmaxDISKmaxIOPSavgIOPS活跃会话maxTPSavgTPSmaxQPSavgQPS实例风险 慢查询 慢查询会消耗大量的系统资源&#x…...
Qt Quick开发基础+实战（持续更新中…）
最近更新日期：2024/12/4 一、Qt Quick简介 写在前面： 本篇文章虽然只是作为我的学习笔记，但也作为我日后复习之用，所以会认真并详细记录，但会分重点。 1.3 新建Qt Quick Application工程 这节主要讲2个知识点&#x…...
FPGA Xilinx维特比译码器实现卷积码译码
FPGA Xilinx维特比译码器实现卷积码译码 文章目录 FPGA Xilinx维特比译码器实现卷积码译码1 Xilinx维特比译码器实现2 完整代码3 仿真结果 MATLAB （n,k,m）卷积码原理及仿真代码（你值得拥有）_matlab仿真后代码-CSDN博客 MATLAB 仿真…...
数据结构初阶1 时间复杂度和空间复杂度
本章重点 算法效率时间复杂度空间复杂度常见时间复杂度以及复杂度OJ练习 1.算法效率 1.1 如何衡量一个算法的好坏 如何衡量一个算法的好坏呢？比如对于以下斐波那契数列： long long Fib(int N) { if(N < 3) return 1;return Fib(N-1) Fib(N-2); }斐…...
基于Matlab计算机视觉的车道线识别与前车检测系统研究
随着自动驾驶技术的发展，车道线识别和前车检测成为智能驾驶系统中的核心技术之一。本实训报告围绕基于计算机视觉的车道线识别与前车检测系统展开，旨在通过处理交通视频数据，实时检测车辆所在车道及其与前车的相对位置，从而为车道…...
)
刷蓝桥杯历年考题(更新至15届~)
第十五届 CA组省赛 AcWing5980.训练士兵 方法一：树状数组:O(nlogn) self-complete /*先枚举组团，后分析每个士兵，有一个特点，组团费用是固定的，那当然是让所有士兵一块训练，训练完的士兵也不会有损失当还…...
Stream API来提取两个字符串字段
如果您有一个包含对象的List，并且想要使用Java 8的Stream API来提取两个字符串字段，然后将这些字段的值连接成一个以逗号隔开的单个字符串或者集合List，您可以按照以下步骤操作： 假设您有一个Person类，其中包含两个字…...
《无畏契约》运行时提示“d3dcompiler_43.dll丢失”是什么原因？“找不到d3dcompiler_43.dll文件”如何解决？
《无畏契约》运行时提示“d3dcompiler_43.dll丢失”是什么原因？“找不到d3dcompiler_43.dll文件”如何解决？ 作为一位软件开发从业者，我深知在游戏运行过程中，遇到各种文件丢失、文件损坏和系统报错等问题是多么令人头疼。今天&a…...
社群分享在商业引流与职业转型中的作用：开源 AI 智能名片 2+1 链动模式小程序的应用契机
摘要：本文聚焦于社群分享在商业领域的重要性，阐述其作为干货诱饵在引流方面的关键意义。详细探讨了提供有价值干货的多种方式，包括文字分享、问题解答以及直播分享等，并分析了直播分享所需的条件。同时，以自身经历为例…...
芯食代冻干科技研究院：创新与品质并重，推动家用冻干机高质量发展
11月25日,芯食代首届食品冻干前沿与智能化升级创新大会在江苏常州成功举办。本次大会由芯食代冻干科技研究院(江苏)有限公司与芯食代(上海)科技发展有限公司联合主办,云集学界专家教授、商界企业精英,共议家用冻干机的未来创新发展。作为创新大会,芯食代冻干科技研究院也在本次…...
【C++】栈和队列的模拟实现（适配器模式）
不论是C语言还是C，我们都用其对应的传统写法对栈和队列进行了模拟实现，现在我们要用新的方法模拟实现栈和队列，这个新方法就是适配器模式。 C语言传统写法： C语言模拟实现栈 C传统写法：C模拟实现栈 1.容器适配器 …...
CSS过渡练习-进度条（12）
该进度条先需要一个大盒子和一个小盒子，然后给大盒子与小盒子加style，看进度到多少就是百分之多少；如果要进度条从百分之五十到满格的话就加一个hover的样式（鼠标移到链接上时添加的特殊样式），然后是想要进…...
青动CRM系统PHP+Uniapp
全面解决企业销售团队的全流程客户服务难题,旨在助力企业销售全流程精细化、数字化管理，全面解决企业销售团队的全流程客户服务难题，帮助企业有效盘活客户资源、量化销售行为，合理配置资源、建立科学销售体系，提升销售业绩。 青动…...
word如何快速创建目录？
文章目录 1，先自己写出目录的各级标题。2、选中目标标题，然后给它们编号3、给标题按照个人需求开始分级4、插入域构建目录。4.1、利用快捷键插入域构建目录4.2、手动插入域构建目录 听懂掌声！学会了吗？ 前提声明：我在此…...
【机器学习】机器学习的基本分类-监督学习-决策树-CART（Classification and Regression Tree）
CART（Classification and Regression Tree） CART（分类与回归树）是一种用于分类和回归任务的决策树算法，提出者为 Breiman 等人。它的核心思想是通过二分法递归地将数据集划分为子集，从而构建一棵树。CART …...
使用GDI对象绘制UI时需要注意的若干细节问题总结
目录 1、一个bitmap不能同时被选进两个dc中 2、CreateCompatibleDC和CreateCompatibleBitmap要使用同一个dc作为参数 3、不能删除已经被选入DC中的GDI对象 4、使用完的GDI对象，要将之释放掉，否则会导致GDI对象泄漏 5、CreateCompatibleBitmap返回错…...
C++：std::fstream详细介绍
std::fstream 是 C 标准库中的一个类，用于处理文件的输入输出操作。它可以同时进行文件的读和写操作，因此被称为“文件流”（File Stream）。它是 C 输入输出流库 iostream 的一部分，继承了 std::istream 和 std::ostrea…...
ndp协议简介
在IPv6中，ARP（地址解析协议）被替代为邻居发现协议（Neighbor Discovery Protocol，NDP）。NDP是IPv6网络中用于发现邻居节点（相邻设备）的协议，类似于IPv4中的ARP。但与ARP不…...
915DEBUG-obsidianTemplater使用
Templater使用 tp函数不正常显示相应数据 模板使用方式不正确 <% tp.date.now("YYYY-MM-DD") %> 应该被放置在一个被Templater识别为模板的文件中，或者在你使用Templater的插入模板功能时输入。如果只是在一个普通的Markdown文件中直接输入这段代码…...
【Linux篇】权限管理 - 用户与组权限详解
一. 什么是权限？ 首先权限是限制人的。人 真实的人 身份角色 权限 角色 事物属性 二. 认识人–用户 Linux下的用户分为超级用户和普通用户 root :超级管理员，几乎不受权限的约束普通用户 :受权限的约束超级用户的命令提示符是#，普通用…...
JWT 在 SaaS 系统中的作用与分布式 SaaS 系统设计的最佳实践
在现代 SaaS（软件即服务） 系统中，随着服务规模的扩大和用户需求的多样化，如何高效、安全地进行用户身份验证、权限控制以及租户隔离，成为了系统架构中的核心问题之一。**JWT（JSON Web Token）**作…...
docker更换容器存储位置
一：原因 今天之前在某个服务器上使用docker搭建的服务突然无法访问了，进入服务器查看发现服务运行正常，但是就是无法使用，然后我这边准备将docker服务重新启动下看看，发现docker服务无法重启，提示内存已满…...
gitlab-cicd部署安装与具体操作
一、安装 本例中是用安装包直接在ubuntu下安装的，也可以用docker镜像。 curl -LJO https://gitlab-runner-downloads.s3.amazonaws.com/latest/rpm/gitlab-runner_amd64.rpmrpm -i gitlab-runner_amd64.rpm 安装runner后，需要跟在runner所在服务器安装…...
基于MFC实现的人机对战五子棋游戏
基于MFC实现的人机对战五子棋游戏 1、引言 此报告将详细介绍本次课程设计的动机、设计思路及编写技术的详细过程，展现我所学过的C知识以及我通过本次课程设计所学到例如MFC等知识。在文档最后我也会记录我所编写过程遇到的问题以及解决方案。 1.1 背景 五子棋是…...
mac电脑多个ssh keys共存
一、同一台电脑，不同域名的git仓库为什么要设置不同的ssh keys？ 每个git仓库通常要求使用唯一的ssh key，以防止权限冲突和安全问题。 权限控制：每个git仓库的权限是独立的，使用不同的ssh keys可以更好的管理权限&…...
Elasticsearch数据迁移（快照）
1. 数据条件 一台原始es服务器（192.168.xx.xx），数据迁移后的目标服务器（10.2.xx.xx）。 2台服务器所处环境： centos7操作系统， elasticsearch-7.3.0。 2. 为原始es服务器数据创建快照 修改elas…...
【Java-数据结构篇】Java 中栈和队列：构建程序逻辑的关键数据结构基石
我的个人主页 我的专栏：Java-数据结构，希望能帮助到大家！！！点赞❤ 收藏❤ 一、引言 1. 栈与队列在编程中的角色定位 栈和队列作为两种基本的数据结构，在众多编程场景中都有着独特的地位。它们为数据的有序…...
使用ensp搭建内外互通，使用路由跨不同vlan通信。
1.网络拓扑图 2.规则 （1）允许 （自己）ping通内外网，内外网随便一个pc就可以. （2） 允许（电信）ping通内外网，内外网随便一个pc就可以 （时间问题不做…...
URDF 发布者
URDF 发布者 #! /usr/bin/env python3 import rclpy from rclpy.node import Node import rclpy.parameter from sensor_msgs.msg import JointState from rcl_interfaces.msg import SetParametersResultimport threading import timeclass RotateWheelNode(Node):def __init…...
用于目标检测的集中式特征金字塔
摘要 https://arxiv.org/pdf/2210.02093 视觉特征金字塔在多种应用中已展现出其在有效性和效率方面的优越性。然而，现有方法过度关注层间特征交互，却忽略了经验证明有益的层内特征调节。尽管一些方法试图借助注意力机制或视觉变换器来学习紧凑的层内特征表示，但它们忽略了…...
微信小程序购物车全选反选功能以及合计
微信小程序基于Vant Weapp的购物车功能实现 1、单选 使用微信小程序原生表单组件checkbox和checkbox-group 注意：checkbox原生不支持bind:change事件，checkbox-group支持 <checkbox-group bindchange"handleCheck"><checkbox val…...
大数据新视界 -- Hive 数据湖集成与数据治理（下）（26 / 30）
💖💖💖亲爱的朋友们，热烈欢迎你们来到 青云交的博客！能与你们在此邂逅，我满心欢喜，深感无比荣幸。在这个瞬息万变的时代，我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…...
【基础数学二】整除，最大公约数约数，最小公倍数
整除 在数论中，一个整数 a a a 能够被另一个整数 d d d 整除，记做 d ∣ a d|a d∣a。 整除的性质： 如果 d ∣ a d | a d∣a，则对于任意整数 k k k 有 d ∣ k a d | ka d∣ka。如果 d ∣ a d|a d∣a 并且 d ∣ b d|b d∣…...
】IO模型以及补充知识)
【lua语言基础(四)】IO模型以及补充知识
💓博主CSDN主页:杭电码农-NEO💓 ⏩专栏分类:lua从入门到精通⏪ 🚚代码仓库:NEO的学习日记🚚 🌹关注我🫵带你学更多lua语言的知识 🔝🔝 lua语言基础 1. 简单的IO模型2…...
Python知识分享第十九天-网络编程
网络编程 概述用来实现 网络互联 不同计算机上运行的程序间可以进行数据交互也叫Socket编程 套接字编程 三要素IP地址概述设备在网络中的唯一标识分类IPV4城域网13广域网22局域网31IPV6八字节 十六进制相关dos命令查看ipwindows: ipconfigmac和linux: ifconfig测试网络ping 域…...
【JuMP.jl】非线性规划
[JuMP] 03 非线性规划 非线性规划模型 非线性规划问题是线性规划问题的自然推广， 在实际的工程问题中，优化问题中的目标函数与约束不会总是线性函数，因此非线性规划的求解功能是必要的。 min x ∈ R n f 0 ( x ) s.t. l j ≤ f j ( x ) ≤…...
网络（TCP）
目录 TCP socket API 详解 套接字有哪些类型？socket有哪些类型？ 图解TCP四次握手断开连接 图解TCP数据报结构以及三次握手（非常详细） socket缓冲区以及阻塞模式详解 再谈UDP和TCP bind(): 我们的程序中对myaddr参数是这样…...
40分钟学 Go 语言高并发：服务性能调优实战
服务性能调优实战 一、性能优化实战概述 优化阶段主要内容关键指标重要程度瓶颈定位收集性能指标，确定瓶颈位置CPU、内存、延迟、吞吐量⭐⭐⭐⭐⭐代码优化优化算法、并发、内存使用代码执行时间、内存分配⭐⭐⭐⭐⭐系统调优调整系统参数、资源配置系统资源利用率…...
5092 星际争霸
逆序对排序； 字符串遍历； pair 特点： 两个值，第一个是字符串，第二个是逆序对数。而且没有重复的字符串。 #include<bits/stdc.h>using namespace std; typedef long long ll; const int N1e35; #define x f…...
AUTOSAR AP 汽车API知识点总结（Automotive API ）R24-11
汽车API知识点总结 一、背景与目标 背景：智能互联汽车正逐步依赖远程诊断、软件更新等功能以确保行驶安全，并且用户已习惯于通过智能设备中的应用程序控制连接设备。虽然AUTOSAR标准支持车辆软件的可更新性，但尚未提供将AUTOSAR应用产生的数据和功能安全可靠地暴露给非AUTO…...
vue2：Cascader 级联选择器中加载两种不同的数据结构
前言 因UI调整，需要将el-tree控件更换为级联选择器，而在原树形控件中，加载了两种不同的数据结构，（参见vue2：树形控件el-tree中加载两种不同结构的数据_vue2 树形插件-CSDN博客）所以现在级联选择器中也需要加载这两种不同的数据结构。 问题 原本以为处理方式差不多，在…...
【xLSTM-Transformer序列分类】Pytorch使用xLSTM-Transformer对序列进行分类源代码
Python, Pytorch使用xLSTM-Transformer对序列进行分类源代码。xLSTM是不久前LSTM团队提出来的新模型，将xLSTM融入Transformer的Encoder中，创新型较强。另外，Transformer是完整的，即使用了Encoder、Decoder和Embedding所有模块。 …...
TDengine 签约安徽智质，助力海螺水泥智慧工厂升级
在当前制造业数字化转型的浪潮中，如何实现智能化、自动化与数据驱动的高效生产，成为企业提升竞争力的关键。尤其是在水泥、钢铁等传统行业，随着技术的不断进步，如何打破数据孤岛、提升生产管理效率，已经成为许多工厂亟…...
Hbase整合Mapreduce案例2 hbase数据下载至hdfs中——wordcount
目录 整合结构准备数据下载pom.xmlMain.javaReduce.javaMap.java操作 总结 整合结构 和案例1的结构差不多，Hbase移动到开头，后面跟随MR程序。 因此对于输入的K1 V1会进行一定的修改 准备 在HBASE中创建表，并写入数据 create "wunaii…...
WHLUG丨deepin、华中科技大学开放原子开源俱乐部、 RustSBI 和清华大学开源操作系统训练营共话开源新生代成长之路
2024年11月30日下午，由 deepin（深度）社区联合华中科技大学开放原子开源俱乐部、 RustSBI 开源社区和清华大学开源操作系统训练营共同举办的WHLUG（武汉Linux用户组）线下沙龙在华中科技大学成功举办。 本次活动聚集了50余…...
深入理解AVL树：结构、旋转及C++实现
1. AVL树的概念 什么是AVL树？ AVL树是一种自平衡的二叉搜索树，其发明者是Adelson-Velsky和Landis，因此得名“AVL”。AVL树是首个自平衡二叉搜索树，通过对树的平衡因子进行控制，确保任何节点的左右子树高度差最多为1&…...