【排序 - 快速排序】
快速排序(Quick Sort)是一种高效的排序算法,它基于分治(Divide and Conquer)的策略。这种排序算法的核心思想是选择一个基准元素,将数组分割成两部分,使得左边的元素都小于等于基准元素,右边的元素都大于等于基准元素,然后对这两部分分别递归地应用快速排序。
算法步骤:
-
选择基准元素:从数组中选择一个元素作为基准(pivot)。通常选择第一个元素、最后一个元素或者随机一个元素作为基准。
-
分区(Partition):重新排列数组,使得比基准元素小的元素都在基准元素的左边,比基准元素大的元素都在右边。同时,基准元素位于最终排序的位置。
-
递归排序:递归地对基准元素左右两边的子数组进行快速排序。

实现步骤:
下面是用C语言实现快速排序的代码:
#include <stdio.h>// 函数:交换数组中两个元素的值
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 函数:将数组分区,并返回基准元素的位置(索引)
int partition(int arr[], int low, int high) {int pivot = arr[high]; // 选择最后一个元素作为基准int i = low - 1; // 初始化分区索引,比基准元素小的元素会放在左边for (int j = low; j < high; j++) {// 如果当前元素小于或等于基准元素,则将它交换到分区的左边if (arr[j] <= pivot) {i++; // 移动分区索引swap(&arr[i], &arr[j]);}}// 最后将基准元素交换到正确的位置swap(&arr[i + 1], &arr[high]);return i + 1; // 返回基准元素的位置
}// 函数:实现快速排序
void quickSort(int arr[], int low, int high) {if (low < high) {// 对数组进行分区int pi = partition(arr, low, high);// 对基准元素左边和右边的子数组进行递归排序quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}// 函数:打印数组元素
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数:测试快速排序的实现
int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);quickSort(arr, 0, n - 1);printf("排序后的数组: \n");printArray(arr, n);return 0;
}
代码解析:
- swap函数:用于交换数组中两个元素的值。
- partition函数:选择数组中的最后一个元素作为基准,将数组分为两部分,返回基准元素最终的位置索引。
- quickSort函数:实现快速排序的递归算法。在每次递归中,先使用partition函数将数组分区,然后递归地对分区后的两部分进行排序。
- printArray函数:用于打印数组元素,方便查看排序结果。
- main函数:测试快速排序的实现,打印排序前和排序后的数组。
时间复杂度:
快速排序的时间复杂度主要取决于分区操作的时间复杂度和递归调用的次数。在最坏情况下,快速排序的时间复杂度为 O(n^2),但在平均情况下为 O(n log n),这使得它成为一种高效的排序算法。
总结:
快速排序通过分治策略和分区操作,实现了高效的排序。它不需要额外的存储空间(除了递归调用时的栈空间),并且在平均情况下具有较好的性能表现。因此,快速排序是实际应用中常用的排序算法之一,尤其适合大数据集的排序任务。
相关文章:
【排序 - 快速排序】
快速排序(Quick Sort)是一种高效的排序算法,它基于分治(Divide and Conquer)的策略。这种排序算法的核心思想是选择一个基准元素,将数组分割成两部分,使得左边的元素都小于等于基准元素…...
pytest使用报错(以及解决pytest所谓的“抑制print输出”)
1. 测试类的类名问题 #codingutf-8import pytestclass TestClass1:def setup(self) -> None:print(setup)def test_01(self) -> None:print(test_01111111111111111111111)def test_02(self) -> None:print(test_02)以上述代码为例,如果类名是Test开头&am…...
开源项目编译harbor arm架构的包 —— 筑梦之路
GitHub - amy5200/harbor-arm64 先做个记录,空了再验证...
[笔记] SKF Enveloping FAQ 用户指南
文档编号:Application Note CM3013 1.名词解释: 1.1cavitationWhat Is Cavitation? | Pumps & Systems 叶片在液体中扰动形成的超声波 1.2 stiff machinehttps://suspensionlist.com/the-pros-and-cons-of-stiff-vs-soft-suspension-systems/ …...
宪法学学习笔记(个人向) Part.3
宪法学学习笔记(个人向) Part 3 3. 国家基本制度 3.1 国家性质 3.1.1 国家性质概述 国家性质的概念 国家性质也称国体,或国家的阶级本质,是指各个阶级在国家中的地位(哪个阶层是统治阶层,哪个阶层是被统治阶层,哪个…...
联想拯救者Y7000 IRX9 笔记本接口功能介绍
适用机型:Legion Y7000 IRX9; 83JJ; USB(3.2 Gen 1)Type-接口摄像头开关组合音频插孔 多用于USB Type-C接口 以太网接口 多用途USB Type-C接口(支持USB Power Delivery)HDMI接口USB(3.2 Gen 1&…...
【ESP32】打造全网最强esp-idf基础教程——16.SmartConfig一键配网
SmartConfig一键配网 一、SmartConfig知识扫盲 在讲STA课程的时候,我们用的是代码里面固定的SSID和密码去连接热点,但实际应用中不可能这么弄,我们得有办法把家里的WiFi SSID和密码输入到设备里面去,对于带屏带输入设备还…...
MD5加密和注册页面的编写
MD5加密 1.导入包 npm install --save ts-md5 2.使用方式 import { Md5 } from ts-md5; //md5加密后的密码 const md5PwdMd5.hashStr("123456").toUpperCase(); 遇见的问题及用到的技术 注册页面 register.vue代码 <template><div class"wappe…...
【Android组件】封装加载弹框
📖封装加载弹框 ✅1. 构造LoadingDialog✅2. 调用LoadingDialog 效果: ✅1. 构造LoadingDialog 构造LoadingDialog类涉及到设计模式中的建造者模式,进行链式调用,注重的是构建的过程,设置需要的属性。 步骤一&#x…...
Spring源码二十:Bean实例化流程三
上一篇Spring源码十九:Bean实例化流程二中,我们主要讨论了单例Bean创建对象的主要方法getSingleton了解到了他的核心流程无非是:通过一个简单工厂的getObject方法来实例化bean,当然spring在实例化前后提供了扩展如:bef…...
前端导出文件时,后端代码出错如何将错误信息返回给前端展示
功能说明:前端导出excel时,后端出现异常,比如sql异常,或者创建excel时出现的异常,希望将这些异常信息返回给前端查看。 框架:vue3 axios Springboot 实现难度分析:前端导出excel,…...
解决Spring Boot应用中的内存优化问题
解决Spring Boot应用中的内存优化问题 大家好,我是微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 1. Spring Boot应用的内存管理 在开发和部署Spring Boot应用时,有效地管理内存是确保应用性能和稳…...
shark云原生-日志体系-filebeat高级配置(适用于生产)-更新中
文章目录 1. filebeat.inputs 静态日志收集器2. filebeat.autodiscover 自动发现2.1. autodiscover 和 inputs2.2. 如何配置生效2.3. Providers 提供者2.4. Providers kubernetes2.5. 配置 templates2.5.1. kubernetes 自动发现事件中的变量字段2.5.2 配置 templates 2.6. 基于…...
响应式设计的双璧:WebKit 支持 CSS Flexbox 和 Grid 布局深度解析
响应式设计的双璧:WebKit 支持 CSS Flexbox 和 Grid 布局深度解析 在现代网页设计中,响应式布局是实现跨设备兼容性的关键。CSS Flexbox 和 Grid 作为 CSS 布局的两大支柱,提供了强大的工具来构建灵活和复杂的用户界面。WebKit,作…...
Linux软件包管理
一、软件包管理 1.什么是软件包 一般在window系统的.exe是软件按转包 2.linux系统下的软件包安装方式 PRM 软件包安装 软件名称.rpmYUM 包管理工具 yum intall 软件名称 -y源码安装 下载源代码---编译---安装 很麻烦,稳定 3.二进制软件包 二进制 4.获取*.rpm…...
如何分辨AI生成的内容?AI生成内容检测工具对比实验
检测人工智能生成的文本对各个领域的组织都提出了挑战,包括学术界和新闻界等。生成式AI与大语言模型根据短描述来进行内容生成的能力,产生了一个问题:这篇文章/内容/作业/图像到底是由人类创作的,还是AI创作的?虽然 LL…...
Clion中怎么切换不同的程序运行
如下图,比如这个文件夹下面有那么多的项目: 那么我想切换不同的项目运行怎么办呢?如果想通过下图的Edit Configurations来设置是不行的: 解决办法: 如下图,选中项目的CMakeLists.txt,右键再点击…...
【C++初阶】C++入门(下)
【C初阶】C入门(下) 🥕个人主页:开敲🍉 🥕所属专栏:C🥭 🌼文章目录🌼 6. 引用 6.1 引用的概念 6.2 引用特性 6.3 常引用 6.4 使用场景 6.5 传值、传引用效率…...
【3】迁移学习模型
【3】迁移学习模型 文章目录 前言一、安装相关模块二、训练代码2.1. 管理预训练模型2.2. 模型训练代码2.3. 可视化结果2.4. 类别函数 总结 前言 主要简述一下训练代码 三叶青图像识别研究简概 一、安装相关模块 #xingyun的笔记本 print(xingyun的笔记本) %pip install d2l %…...
【工具分享】FOFA——网络空间测绘搜索引擎
文章目录 FOFA介绍FOFA语法其他引擎 FOFA介绍 FOFA官网:https://fofa.info/ FOFA(Fingerprinting Organizations with Advanced Tools)是一款网络空间测绘的搜索引擎,它专注于帮助用户收集和分析互联网上的设备和服务信息。FOFA…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
xmind转换为markdown
文章目录 解锁思维导图新姿势:将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件(ZIP处理)2.解析JSON数据结构3:递归转换树形结构4:Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...
【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!
【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...
