浅谈排序——快速排序(最常用的排序)
快速排序(Quick Sort)是一种常见的排序算法,由英国计算机科学家东尼·霍尔(Tony Hoare)在1960年发明。这是一种分治算法,基本思想是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序算法在平均状况下,排序 n 个项目要 Ο(n log n) 次比较。在最坏状况下则需要 Ο(n^2) 次比较,但这种状况并不常见。实际上,快速排序通常明显比其他 Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地达成。
快速排序的一个优点是它是不稳定的排序算法,意味着相同的元素在排序后可能会保持其原有的顺序。
下面是一个伪代码示例:
快速排序(数组 a, 长度 n)
如果 n > 1
选择 a[1] 作为基准值
左 = 1
右 = n当 左 <= 右
当 a[右] >= 基准值
右 = 右 - 1
当 a[左] <= 基准值
左 = 左 + 1交换 a[左] 和 a[右]
快速排序(a, 左, 右)
在这个算法中,我们选择数组的中位数作为基准值,然后将数组分为两部分,一部分是所有小于基准值的元素,另一部分是所有大于或等于基准值的元素。然后对这两部分递归地进行快速排序。
在实际应用中,快速排序是效率非常高的一种排序算法,尤其是在处理大量数据时。
ok,下面是代码
#include<stdio.h>
int a[100], n;
void qs(int left, int right)
{int i, j, t, temp;if (left > right)return;temp = a[left];i = left;j = right;while (i != j){while (a[j] >= temp && i < j){j--;}while (a[i] <= temp && i < j){i++;}if (i < j){t = a[i];a[i] = a[j];a[j] = t;}} a[left] = a[i];a[i] = temp;qs(left, i - 1);qs(i + 1, right);
}int main()//快速排序
{int i, j, t;scanf("%d", &n);for (int i =1; i <= n; i++){scanf("%d", &a[i]);}qs(1, n);for (int i = 1; i <= n; i++){printf("%d ", a[i]);}return 0;
}
相关文章:
浅谈排序——快速排序(最常用的排序)
快速排序(Quick Sort)是一种常见的排序算法,由英国计算机科学家东尼霍尔(Tony Hoare)在1960年发明。这是一种分治算法,基本思想是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所…...
Springboot项目实现简单的文件服务器,实现文件上传+图片及文件回显
文章目录 写在前面一、配置1、application.properties2、webMvc配置3、查看效果 二、文件上传 写在前面 平常工作中的项目,上传的文件一般都会传到对象存储云服务中。当接手一个小项目,如何自己动手搭建一个文件服务器,实现图片、文件的回显…...
5V低压步进电机驱动芯片GC6150,应用于摄像机,机器人 医疗器械等产品中。具有低噪声、低振动的特点
GC6150是双通道5V低压步进电机驱动器,具有低噪声、低振动的特点,特别适用于相机变焦对焦系统、万向架、摇头机等精度、低噪声STM控制系统,该芯片为每个通道集成了一个256微步的驱动器。通过SPI & T2C接口,客户可以方使地调整驱…...
3D Web轻量引擎HOOPS Communicator如何实现对大模型的渲染支持?
除了读取轻松外,HOOPS Communicator对超大模型的支持效果也非常好,它可以支持30GB的包含70万个零件和3.5亿个三角面的Catia装配模型! 那么它是如何来实现对大模型的支持呢? 我们将从以下几个方面与大家分享:最低帧率…...
『 Linux 』进程地址空间概念
文章目录 🫙 前言🫙 进程地址空间是什么🫙 写时拷贝🫙 可执行程序中的虚拟地址🫙 物理地址分布方式 🫙 前言 在c/C中存在一种内存的概念; 一般来说一个内存的空间分布包括栈区,堆区,代码段等等; 且内存是…...
PySpark大数据处理详细教程
欢迎各位数据爱好者!今天,我很高兴与您分享我的最新博客,专注于探索 PySpark DataFrame 的强大功能。无论您是刚入门的数据分析师,还是寻求深入了解大数据技术的专业人士,这里都有丰富的知识和实用的技巧等着您。让我们…...
三(五)ts非基础类型(对象)
在ts里面定义对象的方式也有很多。 普通定义 let obj1:{} {} // obj1.name fufu 报错,只能定义为空对象且不能修改 // 但是可以在赋初始值的时候直接添加属性,这是ts在类型推断时,它会宽容地匹配对象的结构。 let obj2:{} {name: fufu}…...
HeartBeat监控Redis状态
目录 一、概述 二、 安装部署 三、配置 四、启动服务 五、查看数据 一、概述 使用heartbeat可以实现在kibana界面对redis服务存活状态进行观察,如有必要,也可在服务宕机后立即向相关人员发送邮件通知 二、 安装部署 参照文章:HeartBeat监…...
FairGuard无缝兼容小米澎湃OS、ColorOS 14 、鸿蒙4!
随着移动互联网时代的发展,各大手机厂商为打造生态系统、构建自身的技术壁垒,纷纷投身自研操作系统。 而对于一款游戏安全产品,在不同操作系统下,是否能够无缝兼容并且提供稳定的、高强度的加密保护,成了行业的一大痛…...
【Copilot】Edge浏览器的copilot消失了怎么办
这种原因,可能是因为你的ip地址的不在这个服务的允许范围内。你需要重新使用之前出现copilot的ip地址,然后退出edge的账号,重新登录一遍,最后重启edge,就能够使得copilot侧边栏重新出现了。...
C++入门【6-C++ 修饰符类型】
C 修饰符类型 C 允许在 char、int 和 double 数据类型前放置修饰符。 修饰符是用于改变变量类型的行为的关键字,它更能满足各种情境的需求。 下面列出了数据类型修饰符: signed:表示变量可以存储负数。对于整型变量来说,signe…...
STP笔记总结
STP --- 生成树协议 STP(Spanning Tree Protocol,生成树协议)是根据 IEEE802.1D标准建立的,用于在局域网中消除数据链路层环路的协议。运行STP协议的设备通过彼此交互信息发现网络中的环路,并有选择地对某些端口进行阻…...
Qt开发 之 记一次安装 Qt5.12.12 安卓环境的失败案例
文章目录 1、安装Qt2、安卓开发的组合套件2.1、CSDN地址2.2、官网地址2.3、发现老方法不适用了 3、尝试用新方法解决3.1、先安装JDK,搞定JDK环境变量3.1.1、安装jdk3.1.2、确定jdk安装路径3.1.3、打开系统环境变量配置3.1.4、配置系统环境变量3.1.5、验证JDK环境变量…...
基于SpringBoot的就业信息管理系统设计与实现(源码+数据库+文档)
摘 要 在新冠肺炎疫情的影响下,大学生的就业问题已经变成了一个引起人们普遍重视的社会焦点问题。在这次疫情的冲击之下,大学生的就业市场的供求双方都受到了不同程度的影响,大学生的就业情况并不十分乐观。目前,各种招聘平台上…...
Java面试整理(四)Java IO流
我记得自己刚开始学Java的时候,都听过师兄的分享,说IO流是很重要,而且很难。 自己正式接触之后,其实IO流这块知识并不是特别难,而且随着IT的发展,IO流这块反而用得不是很多。特别是在应用开发这个层面,用得更少。 当然,可能会有朋友跳出来说“这怎么可能?你不懂Java吧…...
《安富莱嵌入式周报》第328期:自主微型机器人,火星探测器发射前失误故障分析,微软推出12周24期免费AI课程,炫酷3D LED点阵设计,MDK5.39发布
周报汇总地址:嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 更新一期视频教程: 【实战技能】 单步运行源码分析,一期视频整明白FreeRTOS内核源码框架和运行…...
产品经理在项目周期中扮演的角色Axure的安装与基本使用
目录 一.项目周期流程 二.Axure是什么 三.Axure安装 3.1 一键式安装 3.2 汉化 3.3 授权登录 四.Axure的界面介绍及基本使用 4.1 菜单栏的使用 4.2 工具栏的使用 4.3 页面概要的使用及组件的使用 4.4 组件的样式设计 一.项目周期流程 在一般的项目周期中包含的工作内容有&…...
Dockerfile创建镜像介绍
1.介绍 Docker 提供了一种更便捷的方式,叫作 Dockerfile,docker build命令用于根据给定的Dockerfile构建Docker镜像。 docker build语法: # docker build [OPTIONS] <PATH | URL | -> 常用选项说明 --build-arg,设置构建时的…...
Android 滥用 SharedPreference 导致 ANR 问题
SharedPreference 是 Android 平台提供的一种轻量级的数据存储方式,它用于存储应用的配置信息或者一些简单的数据。SharedPreference 基于键值对的存储,并且支持基本的数据类型,如整型、字符串、布尔值等。它的使用非常简单方便,适…...
虚幻商城 道具汇总
文章目录 载具Vehicle Variety Pack(车辆品种包)Vehicle Variety Pack Volume 2(车辆品种包第 2 卷)家具Free Furniture Pack(免费家具包)Old West - VOL 1 - Interior Furniture(旧西部 - 第1卷 - 家具包)Old West VOL.3 - Travel Supplies and Goods(旧西部 - 第3卷…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
【深度学习新浪潮】什么是credit assignment problem?
Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...
