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

浅谈排序——快速排序(最常用的排序)

快速排序(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;
}

相关文章:

浅谈排序——快速排序(最常用的排序)

快速排序&#xff08;Quick Sort&#xff09;是一种常见的排序算法&#xff0c;由英国计算机科学家东尼霍尔&#xff08;Tony Hoare&#xff09;在1960年发明。这是一种分治算法&#xff0c;基本思想是通过一趟排序将要排序的数据分割成独立的两部分&#xff0c;其中一部分的所…...

Springboot项目实现简单的文件服务器,实现文件上传+图片及文件回显

文章目录 写在前面一、配置1、application.properties2、webMvc配置3、查看效果 二、文件上传 写在前面 平常工作中的项目&#xff0c;上传的文件一般都会传到对象存储云服务中。当接手一个小项目&#xff0c;如何自己动手搭建一个文件服务器&#xff0c;实现图片、文件的回显…...

5V低压步进电机驱动芯片GC6150,应用于摄像机,机器人 医疗器械等产品中。具有低噪声、低振动的特点

GC6150是双通道5V低压步进电机驱动器&#xff0c;具有低噪声、低振动的特点&#xff0c;特别适用于相机变焦对焦系统、万向架、摇头机等精度、低噪声STM控制系统&#xff0c;该芯片为每个通道集成了一个256微步的驱动器。通过SPI & T2C接口&#xff0c;客户可以方使地调整驱…...

3D Web轻量引擎HOOPS Communicator如何实现对大模型的渲染支持?

除了读取轻松外&#xff0c;HOOPS Communicator对超大模型的支持效果也非常好&#xff0c;它可以支持30GB的包含70万个零件和3.5亿个三角面的Catia装配模型&#xff01; 那么它是如何来实现对大模型的支持呢&#xff1f; 我们将从以下几个方面与大家分享&#xff1a;最低帧率…...

『 Linux 』进程地址空间概念

文章目录 &#x1fad9; 前言&#x1fad9; 进程地址空间是什么&#x1fad9; 写时拷贝&#x1fad9; 可执行程序中的虚拟地址&#x1fad9; 物理地址分布方式 &#x1fad9; 前言 在c/C中存在一种内存的概念; 一般来说一个内存的空间分布包括栈区,堆区,代码段等等; 且内存是…...

PySpark大数据处理详细教程

欢迎各位数据爱好者&#xff01;今天&#xff0c;我很高兴与您分享我的最新博客&#xff0c;专注于探索 PySpark DataFrame 的强大功能。无论您是刚入门的数据分析师&#xff0c;还是寻求深入了解大数据技术的专业人士&#xff0c;这里都有丰富的知识和实用的技巧等着您。让我们…...

三(五)ts非基础类型(对象)

在ts里面定义对象的方式也有很多。 普通定义 let obj1:{} {} // obj1.name fufu 报错&#xff0c;只能定义为空对象且不能修改 // 但是可以在赋初始值的时候直接添加属性&#xff0c;这是ts在类型推断时&#xff0c;它会宽容地匹配对象的结构。 let obj2:{} {name: fufu}…...

HeartBeat监控Redis状态

目录 一、概述 二、 安装部署 三、配置 四、启动服务 五、查看数据 一、概述 使用heartbeat可以实现在kibana界面对redis服务存活状态进行观察&#xff0c;如有必要&#xff0c;也可在服务宕机后立即向相关人员发送邮件通知 二、 安装部署 参照文章&#xff1a;HeartBeat监…...

FairGuard无缝兼容小米澎湃OS、ColorOS 14 、鸿蒙4!

随着移动互联网时代的发展&#xff0c;各大手机厂商为打造生态系统、构建自身的技术壁垒&#xff0c;纷纷投身自研操作系统。 而对于一款游戏安全产品&#xff0c;在不同操作系统下&#xff0c;是否能够无缝兼容并且提供稳定的、高强度的加密保护&#xff0c;成了行业的一大痛…...

【Copilot】Edge浏览器的copilot消失了怎么办

这种原因&#xff0c;可能是因为你的ip地址的不在这个服务的允许范围内。你需要重新使用之前出现copilot的ip地址&#xff0c;然后退出edge的账号&#xff0c;重新登录一遍&#xff0c;最后重启edge&#xff0c;就能够使得copilot侧边栏重新出现了。...

C++入门【6-C++ 修饰符类型】

C 修饰符类型 C 允许在 char、int 和 double 数据类型前放置修饰符。 修饰符是用于改变变量类型的行为的关键字&#xff0c;它更能满足各种情境的需求。 下面列出了数据类型修饰符&#xff1a; signed&#xff1a;表示变量可以存储负数。对于整型变量来说&#xff0c;signe…...

STP笔记总结

STP --- 生成树协议 STP&#xff08;Spanning Tree Protocol&#xff0c;生成树协议&#xff09;是根据 IEEE802.1D标准建立的&#xff0c;用于在局域网中消除数据链路层环路的协议。运行STP协议的设备通过彼此交互信息发现网络中的环路&#xff0c;并有选择地对某些端口进行阻…...

Qt开发 之 记一次安装 Qt5.12.12 安卓环境的失败案例

文章目录 1、安装Qt2、安卓开发的组合套件2.1、CSDN地址2.2、官网地址2.3、发现老方法不适用了 3、尝试用新方法解决3.1、先安装JDK&#xff0c;搞定JDK环境变量3.1.1、安装jdk3.1.2、确定jdk安装路径3.1.3、打开系统环境变量配置3.1.4、配置系统环境变量3.1.5、验证JDK环境变量…...

基于SpringBoot的就业信息管理系统设计与实现(源码+数据库+文档)

摘 要 在新冠肺炎疫情的影响下&#xff0c;大学生的就业问题已经变成了一个引起人们普遍重视的社会焦点问题。在这次疫情的冲击之下&#xff0c;大学生的就业市场的供求双方都受到了不同程度的影响&#xff0c;大学生的就业情况并不十分乐观。目前&#xff0c;各种招聘平台上…...

Java面试整理(四)Java IO流

我记得自己刚开始学Java的时候,都听过师兄的分享,说IO流是很重要,而且很难。 自己正式接触之后,其实IO流这块知识并不是特别难,而且随着IT的发展,IO流这块反而用得不是很多。特别是在应用开发这个层面,用得更少。 当然,可能会有朋友跳出来说“这怎么可能?你不懂Java吧…...

《安富莱嵌入式周报》第328期:自主微型机器人,火星探测器发射前失误故障分析,微软推出12周24期免费AI课程,炫酷3D LED点阵设计,MDK5.39发布

周报汇总地址&#xff1a;嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 更新一期视频教程&#xff1a; 【实战技能】 单步运行源码分析&#xff0c;一期视频整明白FreeRTOS内核源码框架和运行…...

产品经理在项目周期中扮演的角色Axure的安装与基本使用

目录 一.项目周期流程 二.Axure是什么 三.Axure安装 3.1 一键式安装 3.2 汉化 3.3 授权登录 四.Axure的界面介绍及基本使用 4.1 菜单栏的使用 4.2 工具栏的使用 4.3 页面概要的使用及组件的使用 4.4 组件的样式设计 一.项目周期流程 在一般的项目周期中包含的工作内容有&…...

Dockerfile创建镜像介绍

1.介绍 Docker 提供了一种更便捷的方式&#xff0c;叫作 Dockerfile&#xff0c;docker build命令用于根据给定的Dockerfile构建Docker镜像。 docker build语法&#xff1a; # docker build [OPTIONS] <PATH | URL | -> 常用选项说明 --build-arg&#xff0c;设置构建时的…...

Android 滥用 SharedPreference 导致 ANR 问题

SharedPreference 是 Android 平台提供的一种轻量级的数据存储方式&#xff0c;它用于存储应用的配置信息或者一些简单的数据。SharedPreference 基于键值对的存储&#xff0c;并且支持基本的数据类型&#xff0c;如整型、字符串、布尔值等。它的使用非常简单方便&#xff0c;适…...

虚幻商城 道具汇总

文章目录 载具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卷…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...