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

排序算法-快速排序法(QuickSort)

 排序算法-快速排序法(QuickSort)

1、说明

快速排序法是由C.A.R.Hoare提出来的。快速排序法又称分割交换排序法,是目前公认的最佳排序法,也是使用分而治之(Divide and Conquer)的方式,会先在数据中找到一个虚拟的中间值,并按此中间值将所有打算排序的数据分为两部分。其中小于中间值的数据放在左边,而大于中间值的数据放在右边,再以同样的方式分别处理左右两边的数据,直到排序完为止。操作与分割步骤如下:

假设有n项记录R_{1},R_{2},R_{3},...,R_{n},其键值为K_{1},K_{2},K_{3},...,K_{n}

  1. 先假设K的值为第一个键值。
  2. 从左向右找出键值K_{i},使得K_{i}> K
  3. 从左向右找出键值K_{j},使得K_{j}< K
  4. 如果i< j,那么K_{i}K_{j}互换,并回到步骤2。
  5. 如果i\geqslant j,那么将KK_{j}互相,并以j为基准点分割成左、右两部分,然后针对左、右两边执行步骤1~5,直到左边键值等于右边键值为止。

2、算法分析

  1. 在最好情况和平均情况下,时间复杂度为O(nlog_{2^{}}n)。在最坏情况下就是每次挑中的中间值不是最大就是最小的,其时间复杂度为O(n^{2})
  2. 快速排序法不是稳定排序法。
  3. 在最坏情况下,空间复杂度为O(n),而在最好情况下,空间复杂度为O(log_{2^{}}n)
  4. 快速排序法是平均运行时间最快的排序法。

3、C++代码 

#include<iostream>
using namespace std;void Print(int tempData[], int tempSize) {for (int i = 0; i < tempSize; i++) {cout << tempData[i] << "  ";}cout << endl;
}void Quick(int tempData[], int tempLeft, int tempRight) {int temp;int leftIndex;int rightIndex;int t;if (tempLeft < tempRight) {leftIndex = tempLeft + 1;rightIndex = tempRight;while (true) {for (int i = tempLeft + 1; i < tempRight; i++) {if (tempData[i] >= tempData[tempLeft]) {leftIndex = i;break;}leftIndex++;}for (int j = tempRight; j > tempLeft + 1; j--) {if (tempData[j] <= tempData[tempLeft]) {rightIndex = j;break;}rightIndex--;}if (leftIndex < rightIndex) {temp = tempData[leftIndex];tempData[leftIndex] = tempData[rightIndex];tempData[rightIndex] = temp;}else {break;}}if (leftIndex >= rightIndex) {temp = tempData[tempLeft];tempData[tempLeft] = tempData[rightIndex];tempData[rightIndex] = temp;Quick(tempData, tempLeft, rightIndex - 1);Quick(tempData, rightIndex + 1, tempRight);}}
}int main() {const int size = 10;int data[100] = { 32,5,24,55,40,81,17,48,25,71 };//32  5  24  55  40  81  17  48  25  71//32  5  24  25  40  81  17  48  55  71//32  5  24  25  17  81  40  48  55  71//17  5  24  25  32  81  40  48  55  71//5  17  24  25  32  81  40  48  55  71//5  17  25  24  32  81  40  48  55  71//5  17  25  24  32  71  40  48  55  81//5  17  25  24  32  55  40  48  71  81//5  17  25  24  32  48  40  55  71  81//5  17  25  24  32  40  48  55  71  81Print(data, size);Quick(data, 0, size - 1);Print(data, size);return 0;
}

输出结果 

相关文章:

排序算法-快速排序法(QuickSort)

排序算法-快速排序法&#xff08;QuickSort&#xff09; 1、说明 快速排序法是由C.A.R.Hoare提出来的。快速排序法又称分割交换排序法&#xff0c;是目前公认的最佳排序法&#xff0c;也是使用分而治之&#xff08;Divide and Conquer&#xff09;的方式&#xff0c;会先在数…...

Python 简介

一、Python 简介 Python 是著名的“龟叔” Guido van Rossum 在 1989 年圣诞节期间&#xff0c;为了打发无聊的圣诞节而编写的一个编程语言。牛人就是牛人&#xff0c;为了打发无聊时间竟然写了一个这么牛皮的编程语言。 现在&#xff0c;全世界差不多有 600 多种编程语言&am…...

grafana api创建dashboard 记录

文章目录 json model导入申请api key创建dashboard删除dashboard json model导入 直接在ui通过json model 导入&#xff0c;开发自己用还好&#xff0c;但对非开发人员不太友好&#xff0c;故考虑通过api后台自动创建 api doc : https://grafana.com/docs/grafana/v9.3/devel…...

局域网上IP多播与IP单播关于MAC地址的区别

IP单播进行到局域网上的时候&#xff1a; 网际层使用IP地址进行寻址&#xff0c;各路由器收到IP数据报后&#xff0c;根据其首部中的目的IP地址的网络号部分&#xff0c;基于路由表进行查表转发。 查表转发的结果可指明IP数据报的下一跳路由器的IP地址&#xff0c;但无法指明…...

三数之和[中等]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给你一个整数数组nums&#xff0c;判断是否存在三元组[nums[i], nums[j], nums[k]]满足i ! j、i ! k且j ! k&#xff0c;同时还满足nums[i] nums[j] nums[k] 0。请你返回所有和为0且不重复的三元组。 注意&#xff1a;答案中不可以…...

基于天牛须优化的BP神经网络(分类应用) - 附代码

基于天牛须优化的BP神经网络&#xff08;分类应用&#xff09; - 附代码 文章目录 基于天牛须优化的BP神经网络&#xff08;分类应用&#xff09; - 附代码1.鸢尾花iris数据介绍2.数据集整理3.天牛须优化BP神经网络3.1 BP神经网络参数设置3.2 天牛须算法应用 4.测试结果&#x…...

渗透波菜网站

免责声明 本文发布的工具和脚本&#xff0c;仅用作测试和学习研究&#xff0c;禁止用于商业用途&#xff0c;不能保证其合法性&#xff0c;准确性&#xff0c;完整性和有效性&#xff0c;请根据情况自行判断。如果任何单位或个人认为该项目的脚本可能涉嫌侵犯其权利&#xff0c…...

Spring Boot:Dao层-实例介绍

目录 Dao层的作用Dao层的特点与 Service 层和 Controller 层的关系实例介绍MenuDaoOperatorLogDaoRoleDaoUserDao四个文件的共同点引用的包使用Repository注解继承JpaRepository接口接口的实体类的主键类型使用 Query()注解 Dao层的作用 负责与数据库进行交互&#xff0c;主要…...

接口测试入门:深入理解接口测试!

很多人会谈论接口测试。到底什么是接口测试&#xff1f;如何进行接口测试&#xff1f;这篇文章会帮到你。 一、前端和后端 在谈论接口测试之前&#xff0c;让我们先明确前端和后端这两个概念。 前端是我们在网页或移动应用程序中看到的页面&#xff0c;它由 HTML 和 CSS 编写…...

Redis微服务架构

Redis微服务架构 缓存设计 缓存穿透 缓存穿透是指查询一个根本不存在的数据&#xff0c;缓存层和存储层都不会命中&#xff0c;通常出于容错的考虑&#xff0c;如果从存储层查不到数据则不写入缓层。 缓存穿透将导致不存在的数据每次请求都要到存储层去查询&#xff0c;失去…...

【C++】 局部对象,引用返回

1、new 关键字 会在堆内申请空间&#xff0c;如果仅仅是普通调用构造函数&#xff0c;不会在堆内开辟空间。 2、函数调用会形成栈帧&#xff0c;进行压栈操作&#xff0c;函数调用结束&#xff0c;会进行弹栈。 函数内的局部对象&#xff0c;会随着弹栈&#xff0c;而被销毁(…...

线性代数中涉及到的matlab命令-第二章:矩阵及其运算

目录 1&#xff0c;矩阵定义 2&#xff0c;矩阵的运算 3&#xff0c;方阵的行列式和伴随矩阵 4&#xff0c;矩阵的逆 5&#xff0c;克莱默法则 6&#xff0c;矩阵分块 1&#xff0c;矩阵定义 矩阵与行列式的区别&#xff1a; &#xff08;1&#xff09;形式上行列式…...

计算机毕业设计选什么题目好?springboot 美食推荐系统

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…...

爆肝整理,Jmeter接口性能测试-跨线程调用变量实操(超详细)

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、Jmeter中线程运…...

Maven导入程序包jakarta.servlet,但显示不存在

使用前提&#xff1a;&#xff08;Tomcat10版本&#xff09;已知tomcat10版本之后&#xff0c;使用jakart.servlet。而tomcat9以及之前使用javax.servlet。 问题描述&#xff1a;在maven仓库有导入了Jakarta程序包&#xff0c;但是界面仍然显示是javax。&#xff08;下图&…...

es6(二)——常用es6说明

ES6的系列文章目录 es6&#xff08;一&#xff09;——var和let和const的区别 文章目录 ES6的系列文章目录一、变量的结构赋值1.数组的结构赋值2.对象的结构赋值 二、模板字符串三、扩展运算符1.字符串的使用2.数组的使用 四、箭头函数1.普通函数的定义2.箭头函数的定义3.箭头…...

经典垃圾回收器

1.各垃圾回收器之间的配合使用关系 2.垃圾回收器的种类 2.1 Serial收集器&#xff08;默认新生代收集器&#xff09; Serial收集器是历史最悠久的收集器&#xff0c;曾经是新生代收集器的唯一选择&#xff0c;它是一个单线程工作的收集器&#xff0c;其“单线程”的意义不仅仅…...

台达DOP-B07S410触摸屏出现HMI no response无法上传的解决办法

台达DOP-B07S410触摸屏出现HMI no response无法上传的解决办法 台达触摸屏(B07S410)在上载程序时(显示No response from HMI)我以前的电脑是WIN7的,从来没出现过这样的问题,现在换成win10的,怎么都不行,(USB显示是一个大容量存储)换一台电脑(win10)有些行,有些不行…...

[资源推荐] 复旦大学张奇老师科研分享

刷B站的时候首页给我推了这个&#xff1a;【直播回放】复旦大学张奇教授亲授&#xff1a;人工智能领域顶会论文的发表指南先前也散漫地读了些许论文&#xff0c;但没有在一些宏观的方法论下去训练&#xff0c;读的时候能感觉出一些科研的套路&#xff0c;论文写作的套路&#x…...

C++数位动态规划算法:统计整数数目

题目 给你两个数字字符串 num1 和 num2 &#xff0c;以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件&#xff0c;我们称它是一个好整数&#xff1a; num1 < x < num2 min_sum < digit_sum(x) < max_sum. 请你返回好整数的数目。答案可能很大&…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...