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

C语言之快速排序

目录

一 简介

二 代码实现

快速排序基本原理:

C语言实现快速排序的核心函数:

三 时空复杂度

A.时间复杂度

B.空间复杂度

C.总结:


一 简介

快速排序是一种高效的、基于分治策略的比较排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。

二 代码实现

以下是使用C语言实现快速排序的基本步骤和代码示例:

快速排序基本原理:

  • 选择一个基准元素(pivot),通常选择数组的第一个元素或者最后一个元素。
  • 将所有比基准小的元素移动到基准元素之前,所有比基准大的元素移动到基准之后。这个操作被称为分区操作(partition)。
  • 对基准左右两边的子数组分别递归地进行上述操作。

C语言实现快速排序的核心函数:

#include <stdio.h>// 分区操作,返回基准元素最后的位置
int partition(int arr[], int low, int high) {int pivot = arr[high]; // 基准元素(这里选取了数组的最后一个元素)int i = (low - 1);  // 指针i初始化为low - 1for (int j = low; j <= high - 1; j++) {// 如果当前元素小于或等于基准元素,则与指针i所指向位置的元素交换,并将i后移一位if (arr[j] <= pivot) {i++;// 交换arr[i]和arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 把基准元素放到正确的位置(即所有小于它的元素都在它前面)int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return (i + 1);
}// 快速排序主函数
void quickSort(int arr[], int low, int high) {if (low < high) {// pi是基准元素最后所在的位置int pi = partition(arr, low, high);// 对基准元素左侧子数组进行递归排序quickSort(arr, low, pi - 1);// 对基准元素右侧子数组进行递归排序quickSort(arr, pi + 1, high);}
}// 测试快速排序
int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr)/sizeof(arr[0]);quickSort(arr, 0, n-1);printf("Sorted array: \n");for (int i=0; i<n; i++)printf("%d ", arr[i]);return 0;
}

这段代码首先定义了一个partition函数,该函数负责对输入数组进行一次划分操作,然后通过quickSort函数递归地对左右两个子数组执行同样的操作,直到子数组只剩下一个元素为止(因为只有一个元素的数组被认为是有序的)。最终,整个数组会被排序完成。

三 时空复杂度

A.时间复杂度

  • 平均情况:当每次划分都能将数组大致均分为两个子数组时,快速排序的平均时间复杂度为 O(nlog_2n)。这是由于每次递归调用都会将问题规模减半,并且需要对 n 个元素进行 log_2n 层递归。

  • 最好情况:最好的情况即每次选取的基准都能将数组完美地划分为大小相等的两部分,此时时间复杂度也是 O(nlog_2n)

  • 最坏情况:最坏的情况是每次划分后,一个子数组为空或只有一个元素,而另一个子数组包含所有剩余元素。例如,对于已经完全有序的数组,这种情况会导致退化为O(n^2)的时间复杂度。然而,在实际应用中,可以通过随机化选择基准元素(如三数取中法)来避免这种极端情况的发生,从而保证快速排序在期望下的时间复杂度仍为O(nlog_2n)

B.空间复杂度

  • 递归栈空间:快速排序是一种递归算法,其递归深度取决于输入数据的结构。在最坏情况下,递归深度可以达到 n,所以空间复杂度为 O(n)。但大多数情况下,递归深度为log_2n,此时的空间复杂度主要来自于递归调用栈,约为 O(log_2n)

  • 辅助空间:快速排序在原地排序的情况下不需要额外的数据存储空间,除了递归调用栈所占用的空间外,算法本身不使用其他额外空间,因此辅助空间复杂度可认为是 O(1)。

C.总结:

综上所述,快速排序在理想情况下是一个非常高效的排序算法,具有较好的平均性能。不过需要注意的是,为了避免最坏情况下的性能下降,通常会采取一些策略优化基准元素的选择方法。

相关文章:

C语言之快速排序

目录 一 简介 二 代码实现 快速排序基本原理&#xff1a; C语言实现快速排序的核心函数&#xff1a; 三 时空复杂度 A.时间复杂度 B.空间复杂度 C.总结&#xff1a; 一 简介 快速排序是一种高效的、基于分治策略的比较排序算法&#xff0c;由英国计算机科学家C.A.R. H…...

获取扇区航班数

1、Spark Streaming清洗服务&#xff0c;接收kafka中Topic为“task_ATC”中的数据&#xff0c;保存在MySQL中。 打开SpringBoot项目BigData-Etl-KongGuan 请认真阅读&#xff1a;在前面的“使用Spark清洗统计业务数据并保存到数据库中”任务阶段中应该已经完成了所有Topic的数…...

​【已解决】npm install​卡主不动的情况

使用 npm install 初始化前端项目时&#xff0c;会出现卡住不动的情况。原因是淘宝镜像源由原来的https://registry.npm.taobao.org 更换为下面这个&#xff1a; https://registry.npmmirror.com 直接在终端执行下面的指令即可&#xff1a; npm config set registry https://re…...

Golang协程详解

一.协程的引入 1.通过案例文章引入并发,协程概念 见:[go学习笔记.第十四章.协程和管道] 1.协程的引入,调度模型&#xff0c;协程资源竞争问题 通过上面文章可以总结出Go并发编程原理: 在一个处理进程中通过关键字 go 启用多个协程&#xff0c;然后在不同的协程中完成不同的子任…...

git:码云仓库提交以及Spring项目创建

git&#xff1a;码云仓库提交 1 前言 码云访问稳定性优于github&#xff0c;首先准备好码云的账户&#xff1a; 官网下载GIT&#xff0c;打开git bash&#xff1a; 查看当前用户的所有GIT仓库&#xff0c;需要查看全局的配置信息&#xff0c;使用如下命令&#xff1a; git …...

【Miniconda】基于conda避免运行多个PyTorch项目时发生版本冲突

【Miniconda】基于conda避免运行多个PyTorch项目时发生版本冲突 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程&#x1f448; 希望得到…...

【机器学习-02】矩阵基础运算---numpy操作

在机器学习-01中&#xff0c;我们介绍了关于机器学习的一般建模流程&#xff0c;并且在基本没有数学公式和代码的情况下&#xff0c;简单介绍了关于线性回归的一般实现形式。不过这只是在初学阶段、为了不增加基础概念理解难度所采取的方法&#xff0c;但所有的技术最终都是为了…...

《A Second-Order PHD Filter With Mean and Variance in Target Number》学习心得

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 1. 主要内容2. PHD、CPHD和SO-PHD之间的差别2.1 PHD2.2 CPHD2.3 SO-PHD2.4 关于“CPHD对每个可能的目标数量状态进行建模”3. PHD、CPHD和SO-PHD描述目标数量分布所用的参数3.1 PHD所用参数3.2 CPH…...

React 实现下拉刷新效果

简介 本文基于react实现下拉刷新效果&#xff0c;在下拉的时候会进入loading状态。 实现效果 效果如上图所示&#xff0c;在下拉到底部时候&#xff0c;会出现loading条&#xff0c;在处理完成后loading条消失。 具体代码 布局 & 逻辑 import {useRef, useState} from …...

使用endnote插入引用文献导致word英文和数字变成符号的解决方案

使用endnote插入引用文献导致word英文和数字变成符号的解决方案 如图使用endnote插入引用文献导致word英文和数字变成符号字体Wingdings Wingdings 是一个符号字体系列&#xff0c;它将许多字母渲染成各式各样的符号&#xff0c;用途十分广泛。 解决方法&#xff1a; 直接通过更…...

npm下载慢换国内镜像地址

1 设置淘宝镜像地址 npm config set registry http://registry.npm.taobao.org 2 查看当前下载地址 npm config get registry 3 其它镜像地址列表&#xff1a; 1. 官方镜像&#xff1a;https://registry.npmjs.org/ 2. 淘宝镜像&#xff1a;https://registry.npm.taobao.o…...

开源绘图工具 PlantUML 入门教程(常用于画类图、用例图、时序图等)

文章目录 一、类图二、用例图三、时序图 一、类图 类的UML图示 startuml skinparam classAttributeIconSize 0 class Dummy {-field1 : String#field2 : int~method1() : Stringmethod2() : void } enduml定义能见度&#xff08;可访问性&#xff09; startumlclass Dummy {-f…...

Ubuntu20下C/C++编程开启TCP KeepAlive

1、在linux下&#xff0c;测试tcp保活&#xff0c;可以使用tcp自带keepalive功能。 2、几个重要参数&#xff1a; tcp_keepalive_time&#xff1a;对端在指定时间内没有数据传输&#xff0c;则向对端发送一个keepalive packet&#xff0c;单位&#xff1a;秒 tcp_keep…...

前世档案(不用二叉树语法秒杀版c++)

网络世界中时常会遇到这类滑稽的算命小程序&#xff0c;实现原理很简单&#xff0c;随便设计几个问题&#xff0c;根据玩家对每个问题的回答选择一条判断树中的路径&#xff08;如下图所示&#xff09;&#xff0c;结论就是路径终点对应的那个结点。 现在我们把结论从左到右顺序…...

Java基础 - 9 - 集合进阶(二)

一. Collection的其他相关知识 1.1 可变参数 可变参数就是一种特殊形参&#xff0c;定义在方法、构造器的形参列表里&#xff0c;格式是&#xff1a;数据类型…参数名称; 可变参数的特点和好处 特点&#xff1a;可以不传数据给它&#xff1b;可以传一个或者同时传多个数据给…...

javaEE——线程的等待和结束

文章目录 Thread 类及常见方法启动一个线程中断一个线程变量型中断调用 interrupt() 方法来通知观察标志位是否被清除 等待一个线程获取当前线程引用休眠当前线程 线程的状态观察线程的所有状态观察 1: 关注 NEW 、 RUNNABLE 、 TERMINATED 状态的切换 多线程带来的风险为什么会…...

sqlplus设置提示符

作为DBA&#xff0c;需要管理好多数据库&#xff0c;经常会有一台服务器安装多个oracle实例的情况&#xff0c;为避免误操作实例&#xff0c;我们需要在执行sqkplus前&#xff0c;先通过$ echo $ORACLE_SID或 SQL>select name from v$database查看当前实例&#xff0c;这样难…...

macbook删除软件只需几次点击即可彻底完成?macbook删除软件没有叉 苹果笔记本MacBook电脑怎么卸载软件? cleanmymac x怎么卸载

在MacBook的使用过程中&#xff0c;软件安装和卸载是我们经常需要进行的操作。然而&#xff0c;不少用户在尝试删除不再需要的软件时&#xff0c;常常发现这个过程既复杂又耗时。尽管MacOS提供了一些基本的macbook删除软件方法&#xff0c;但很多时候这些方法并不能彻底卸载软件…...

Unity WebGL ios 跳转URL

需求&#xff1a; WebGL跳转网址 现象: Application.OpenURL("https://www.baidu.com"); 这个函数在安卓上可以用&#xff0c;IOS 不管用 解决方案: 编写js插件&#xff0c;unity调用js函数&#xff0c;由js跳转网址 注意事项 &#xff1a; 插件后缀为.jsli…...

机器学习模型—XGBoost

机器学习模型—XGBoost XGBoost(Extreme Gradient Boosting)是由陈天奇等人于2014年提出的一个高效可扩展的梯度提升库。它在梯度提升框架的基础上进行了优化和改进,被广泛应用于机器学习竞赛和实际应用中 作为GBDT(Gradient Boosting Decision Tree)的扩展版本,XGBoost在算…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

mac:大模型系列测试

0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何&#xff0c;是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试&#xff0c;是可以跑通文章里面的代码。训练速度也是很快的。 注意…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

Java 与 MySQL 性能优化:MySQL 慢 SQL 诊断与分析方法详解

文章目录 一、开启慢查询日志&#xff0c;定位耗时SQL1.1 查看慢查询日志是否开启1.2 临时开启慢查询日志1.3 永久开启慢查询日志1.4 分析慢查询日志 二、使用EXPLAIN分析SQL执行计划2.1 EXPLAIN的基本使用2.2 EXPLAIN分析案例2.3 根据EXPLAIN结果优化SQL 三、使用SHOW PROFILE…...