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

排序算法---快速排序

原创不易,转载请注明出处。欢迎点赞收藏~

快速排序是一种常用的排序算法,采用分治的策略来进行排序。它的基本思想是选取一个元素作为基准(通常是数组中的第一个元素),然后将数组分割成两部分,其中一部分的所有元素小于等于基准值,另一部分的所有元素大于基准值。然后对这两部分继续递归应用快速排序算法,直到整个数组有序。

算法步骤如下:

  1. 选择基准元素。
  2. 将数组分割成两部分,使得左半部分的元素都小于等于基准值,右半部分的元素都大于基准值。
  3. 对左右两部分分别应用快速排序算法(递归)。

快速排序的时间复杂度为O(nlogn)。这是因为每次划分操作会把待排序的序列分割成两个规模大致相等的子序列,划分操作的时间复杂度为O(n),递归调用的次数为O(logn)。所以总体的时间复杂度为O(nlogn)。

快速排序的空间复杂度为O(logn)。这是因为快速排序需要使用递归来进行划分操作,每一层递归都需要额外的空间来保存分割点的位置,递归调用的次数为O(logn),所以总体的空间复杂度为O(logn)。

需要注意的是,快速排序是一种原地排序算法,它不需要额外的辅助空间来进行排序。但是在实际实现中,为了提高排序的效率和减少递归深度,通常会使用一些优化策略,比如随机选择基准元素、三数取中法等。

#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[low]; // 选择第一个元素作为基准值int i = low, j = high;while (i < j){// 从右往左找到第一个小于基准值的元素while (i < j && arr[j] >= pivot){j--;}// 从左往右找到第一个大于基准值的元素while (i < j && arr[i] <= pivot){i++;}// 交换这两个元素的位置if (i < j){swap(&arr[i], &arr[j]);}}// 将基准值放到最终的位置swap(&arr[low], &arr[i]);return i;
}// 快速排序函数
void quick_sort(int arr[], int low, int high)
{if (low < high){// 找到分割点int pivotIndex = partition(arr, low, high);// 对分割点左右两部分进行递归排序quick_sort(arr, low, pivotIndex - 1);quick_sort(arr, pivotIndex + 1, high);}
}// 测试
int main()
{int arr[] = {8, 4, 2, 9, 5, 1, 6, 3, 7};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的数组:\n");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}quick_sort(arr, 0, n - 1);printf("\n排序后的数组:\n");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}putchar('\n');return 0;
}

以上示例代码演示了如何使用快速排序算法对一个整数数组进行排序。首先定义了交换函数swap用于交换数组中两个元素的位置,然后定义了分割函数partition用于将数组分割成左右两部分。 最后定义了快速排序函数quick_sort来递归地进行分割和排序。

运行示例代码后,你可以看到以下输出:

相关文章:

排序算法---快速排序

原创不易&#xff0c;转载请注明出处。欢迎点赞收藏~ 快速排序是一种常用的排序算法&#xff0c;采用分治的策略来进行排序。它的基本思想是选取一个元素作为基准&#xff08;通常是数组中的第一个元素&#xff09;&#xff0c;然后将数组分割成两部分&#xff0c;其中一部分的…...

算法||实现典型数据结构的查找、添加和删除数据 并分析其时间和空间复杂度

实现典型数据结构的查找、添加和删除数据 并分析其时间和空间复杂度 线性结构&#xff1a; 数组&#xff1a;是一种线性表数据结构&#xff0c;它用一组连续的内存空间&#xff0c;来存储一组具有相同类型的数据。 查找数据 &#xff1a;随机访问 流程图 /** 查询元素下标…...

【蓝桥杯冲冲冲】Invasion of the Milkweed G

【蓝桥杯冲冲冲】Invasion of the Milkweed G 蓝桥杯备赛 | 洛谷做题打卡day30 文章目录 蓝桥杯备赛 | 洛谷做题打卡day30[USACO09OCT] Invasion of the Milkweed G题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 题解代码我的一些话 [USACO09OCT] Invasion of the Mi…...

【JAVA WEB】 百度热榜实现 新闻页面 Chrome 调试工具

目录 百度热榜 新闻页面 Chrome 调试工具 --查看css属性 打开调试工具的方式 标签页含义 百度热榜 实现效果&#xff1a; 实现代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"vi…...

Linux——动静态库

基础知识:动vs静 类型动静加载时机运行时编译时可复用性多个文件只需要加载一份库文件每个文件都需要加载一份文件性能链接次数越多越有优势链接次数越少越有优势 代码编写 静态库 生成静态库 libmath.a:add.o sub.oar -rc $ $^%.o:%.cgcc -c $<使用静态库 头文件和工…...

Vulnhub靶机:hacksudo-search

一、介绍 运行环境&#xff1a;Virtualbox 攻击机&#xff1a;kali&#xff08;10.0.2.15&#xff09; 靶机&#xff1a;hacksudo-search&#xff08;10.0.2.50&#xff09; 目标&#xff1a;获取靶机root权限和flag 靶机下载地址&#xff1a;https://download.vulnhub.co…...

Leetcode 188 买卖股票的最佳时机 IV

题意理解&#xff1a; 给你一个整数数组 prices 和一个整数 k &#xff0c;其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说&#xff0c;你最多可以买 k 次&#xff0c;卖 k 次。 注意&#xf…...

win32编程系统BUG(Win32 API中的WM_SETTEXT消息)

由于频繁使用Win32 API中的WM_SETTEXT消息&#xff0c;导致内存占用直线上升。 暂未找到有效解决方案。...

Linux防火墙开放

记录一次问题 写的网络服务无法通信 代码没问题&#xff0c;IP绑定、端口绑定没问题&#xff0c;就是无法进行通信&#xff0c;这里要分2步走。 服务器控制台开放 进入防火墙 添加规则&#xff0c;这里以开放udp的8899端口为例 这里在服务器后台就已经开放了&#xff0c;但此时…...

通过 docker-compose 部署 Flink

概要 通过 docker-compose 以 Session Mode 部署 flink 前置依赖 Docker、docker-composeflink 客户端docker-compose.yml version: "2.2" services:jobmanager:image: flink:1.17.2ports:- "8081:8081"command: jobmanagervolumes:- ${PWD}/checkpoin…...

HarmonyOS ArkTS修改App的默认加载的界面(二十)

前言&#xff1a;在Android开发中想要修改默认启动页&#xff0c;只需要在AndroidManifest.xml中设置即可 只需要在启动的activity种添加如下属性即可 <intent-filter><action android:name"android.intent.action.MAIN" /><category android:name&qu…...

【前端高频面试题--Vue基础篇】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;前端高频面试题 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac;前端高频面试题--Vue基础篇 Vue基本原理双向绑定与MVVM模型Vue的优点计算属性与监听属性计算属性监…...

Spring Boot 实现热插拔 AOP

现在有这么一个需求:就是我们日志的开与关是交给使用人员来控制的,而不是由我们开发人员固定写死的。大家都知道可以用aop来实现日志管理,但是如何动态的来实现日志管理呢?aop源码中的实现逻辑中有这么一个步骤,就是会依次扫描Advice的实现类,然后执行。我们要做的就是自…...

2月05日,每日信息差

第一、全球首套5G及6G天地一体网络低轨试验卫星发射入轨、。据了解&#xff0c;“中国移动01星”是全球首颗可验证5G天地一体演进技术的试验卫星&#xff0c;它搭载的基站可以利用卫星的广覆盖优势把5G信号传送到地面网络无法覆盖到的地方&#xff1b;另外一颗“‘星核’验证星…...

使用Python进行数据的描述性分析,用少量的描述性指标来概括大量的原始数据

在进行数据分析时&#xff0c;当研究者得到的数据量很小时&#xff0c;可以通过直接观察原始数据来获得所有的信息。但是&#xff0c;当得到的数据量很大时&#xff0c;就必须借助各种描述性指标来完成对数据的描述工作。用少量的描述性指标来概括大量的原始数据&#xff0c;对…...

【JS逆向三】逆向某某网站的sign参数,并模拟生成仅供学习

逆向日期&#xff1a;2024.02.06 使用工具&#xff1a;Node.js 类型&#xff1a;webpack 文章全程已做去敏处理&#xff01;&#xff01;&#xff01; 【需要做的可联系我】 可使用AES进行解密处理&#xff08;直接解密即可&#xff09;&#xff1a;AES加解密工具 1、打开某某…...

移动光猫gs3101超级密码及改桥接模式教程

文章目录 超级管理员账号改桥接模式路由器连接光猫&#xff0c;PPPOE拨号即可&#xff01;附录&#xff1a;如果需要改桥接的话不知道拨号密码咋办打开光猫Telnet功能Telnet 登录 参考文章 移动光猫吉比特GS3101超级账号获取更改桥接 移动光猫gs3101超级密码及改桥接模式教程 …...

leetcode 153

153 寻找旋转排序数组中的最小值 这道题&#xff0c;如果我们熟悉数组 api&#xff0c;可以直接用 Arrays.sort()秒杀&#xff0c;这个方法使用了双轴快速排序算法。 解法1如下&#xff1a; class Solution {public int findMin(int[] nums) {Arrays.sort(nums);return nums…...

【MySQL】数据库的基础——数据库的介绍、MySQL的介绍和架构、SQL分类、MySQL的基本使用、MySQL的存储引擎

文章目录 MySQL1. 数据库的介绍1.2 主流数据库 2. MySQL的介绍2.1 MySQL架构2.2 SQL分类2.3 MySQL的基本使用2.4 MySQL存储引擎 MySQL 1. 数据库的介绍 数据库&#xff08;Database&#xff0c;简称DB&#xff09;是按照数据结构来组织、存储和管理数据的仓库。它是长期存储在计…...

后端的技术设计文档

一、 背景 1.简介 2.业务规划(非必需) 3.工作项拆解 拆解成多个工作项&#xff0c;每个工作项&#xff0c;需要多少人力。 4.资源评估(非必需) 有没有新的服务 二、架构设计 1.架构图(非必需&#xff0c;新服务比较需要) 2.技术选型 SpringCloud、Redis、Mysql、Myba…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

数据结构:递归的种类(Types of Recursion)

目录 尾递归&#xff08;Tail Recursion&#xff09; 什么是 Loop&#xff08;循环&#xff09;&#xff1f; 复杂度分析 头递归&#xff08;Head Recursion&#xff09; 树形递归&#xff08;Tree Recursion&#xff09; 线性递归&#xff08;Linear Recursion&#xff09;…...