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

交换排序——冒泡排序、快速排序

交换排序就是通过比较交换实现排序。分冒泡排序和快速排序两种。

一、冒泡排序:

1、简述

顾名思义就是大的就冒头,换位置。

通过多次重复比较、交换相邻记录而实现排序;每一趟的效果都是将当前键值最大的记录换到最后。

冒泡排序算法的原理如下: 

  • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 
  • 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。 
  • 针对所有的元素重复以上的步骤,除了最后一个。 
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较

2、复杂度

时间复杂度:O(n²)

空间复杂度:O(1)

3、稳定性:稳定排序

4、例子

#include <iostream>
using namespace std;
// 冒泡
int main() {int arr[8] = {45, 38, 66, 90, 88, 10, 25, 45};int arrCount = sizeof(arr) / sizeof(arr[0]);for (int i = 0; i < arrCount - 1; i++) {for (int j = 0; j < arrCount - i - 1; j++) {if (arr[j] > arr[j+1]) { // 对比两个值int tmp = arr[j];// 交换位置arr[j] = arr[j+1];arr[j+1] = tmp;}}cout<<i+1<<"次排序后:";for (int i = 0;i < arrCount;i++) {cout << arr[i] << " ";}cout<<endl;}cout<<"最后结果:";for (int i = 0;i < arrCount;i++) {cout << arr[i] << " ";}return 0;
}

输出结果:

1次排序后:38 45 66 88 10 25 45 90 
2次排序后:38 45 66 10 25 45 88 90 
3次排序后:38 45 10 25 45 66 88 90 
4次排序后:38 10 25 45 45 66 88 90 
5次排序后:10 25 38 45 45 66 88 90 
6次排序后:10 25 38 45 45 66 88 90 
7次排序后:10 25 38 45 45 66 88 90 
最后结果:10 25 38 45 45 66 88 90

二、快速排序:

关键词:基准值,递归算法

1、简述

快速排序(Quicksort),计算机科学词汇,适用领域Pascal,C++等语言,是对冒泡排序算法的一种改进。

快速排序算法流程如下: 

  • 首先设定一个基准值,通过该基准值将数组分成左右两部分。 
  • 将大于或等于基准值的数据集中到数组右边,小于基准值的数据集中到数组的左边。此时,左边部分中各元素都小于基准值,而右边部分中各元素都大于或等于基准值 。
  • 然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个基准值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。 
  • 重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

2、复杂度

时间复杂度:O(n\log_{2}n) 、最差O(n²) (注:快速排序在表基本有序时,最不利于其发挥效率,即蜕化为冒泡排序,其时间复杂度为O(n²))

空间复杂度:O(\log_{2}n)

3、稳定性:不稳定排序

在交换的过程中相同的数值可能会被换到前面去,所以是不稳定的。

4、例子

在经历第一趟之后,我们将基准值左边和右边分别进行同样的操作。

left和right从原先的0和7,更新为对应的数值:

第一趟排序之后: [25 38 10] 45 [88 90 66 45]

分别对子序列排序:

左边子序列排序: [25 38 10] > left = 0, right = 2, flag = 25

                              [10] 25 [38]

再对25左右两侧进行同样的排序方式,得出左边子序列排序后的结果:

                             10 25 38

右边子序列排序: [88 90 66 45] > left = 4, right = 7, flag = 88

                              [45 66] 88 [90]

再对88左右两侧进行同样的排序方式,最后得到右边子序列排序后的顺序 :

                             45 66 88 90

合并起来就是: [10 25 38 45 45 66 88 90]

 由于交换规则一致,我们可以用递归来处理。

#include <iostream>
using namespace std;
/// 交换位置
void swapPosition(int arr[], int x, int y) {arr[x] = arr[y]+arr[x];arr[y] = arr[x] - arr[y];arr[x] = arr[x] - arr[y];
}void quickSort(int list[], int begin, int end) {// 将基准值flag定为列表第一个。int left = begin, right = end, flag = list[begin];cout<<"这趟排序的起始位置:"<<begin<<",结束位置:"<<end<<",基准值:"<<flag<<endl;// 左右指针未碰头则反复做:while (left < right) {// 从右边开始!!!// 右边没找到小于 flag 的右指针 继续往左移while (list[right] >= flag && left<right) {--right;}// 右边找到比flag小的数据,则将其送到左边,并且将左边的指针往右移动if(left < right) {// 交换位置swapPosition(list, left, right);++left;}// 接着开始左边的循环// 左边没找到大于 flag 的左指针 继续往右移while (list[left] <= flag && left<right) {++left;}// 左边找到比flag大的数据,则将其送到右边,并且将右边的指针往左移动if(left < right) {// 交换位置swapPosition(list, left, right);--right;}}cout<<"结果:";for (int i = 0;i < 8;i++) {cout << list[i] << " ";}cout<<endl;if (begin<left-1){cout<<"开始左边的递归:"<<endl;quickSort(list, begin, left-1);}if(right+1 < end){cout<<"开始右边的递归:"<<endl;quickSort(list, right+1, end);}
}
int main() {int arr[8] = {45, 38, 66, 90, 88, 10, 25, 45};int arrCount = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, arrCount - 1);cout<<"最后结果:";for (int i = 0;i < arrCount;i++) {cout << arr[i] << " ";}return 0;
}

输出结果:

这趟排序的起始位置:0,结束位置:7,基准值:45
结果:25 38 10 45 88 90 66 45 
开始左边的递归:
这趟排序的起始位置:0,结束位置:2,基准值:25
结果:10 25 38 45 88 90 66 45 
开始右边的递归:
这趟排序的起始位置:4,结束位置:7,基准值:88
结果:10 25 38 45 45 66 88 90 
开始左边的递归:
这趟排序的起始位置:4,结束位置:5,基准值:45
结果:10 25 38 45 45 66 88 90 
最后结果:10 25 38 45 45 66 88 90

参考:

百度百科——冒泡排序:https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F?fromModule=lemma_search-box

百度百科——快速排序:https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/369842?fr=ge_ala


生命不息,学习不止,若有不正确的地方,欢迎指正。

相关文章:

交换排序——冒泡排序、快速排序

交换排序就是通过比较交换实现排序。分冒泡排序和快速排序两种。 一、冒泡排序&#xff1a; 1、简述 顾名思义就是大的就冒头&#xff0c;换位置。 通过多次重复比较、交换相邻记录而实现排序&#xff1b;每一趟的效果都是将当前键值最大的记录换到最后。 冒泡排序算法的原…...

Android 10.0 禁用adb shell input输入功能

1.前言 在10.0的产品开发中,在进行一些定制开发中,对于一些adb shell功能需要通过属性来控制禁止使用input 等输入功能,比如adb shell input keyevent 响应输入事件等,所以就需要 熟悉adb shell input的输入事件流程,然后来禁用adb shell input的输入事件功能,接下来分…...

cuda显存访问耗时

背景&#xff1a; 项目中有个数据量大小为5195 * 512 * 128float 1.268G的显存&#xff0c;发现有个函数调用很耗时&#xff0c;函数里面就是对这个显存进行128个元素求和&#xff0c;得到一个5195 * 512的图像 分析 1. 为什么耗时 直观上感觉这个流程应该不怎么耗时才对&a…...

【HTML5高级第三篇】drag拖拽、音频视频、defer/async属性、dialog应用

文章目录 一、拖拽事件1.1 拖拽事件1.2 案例&#xff1a;拖拽丢弃图片 二、音频和视频三、defer 与 async 属性3.1 概述3.2 示例一&#xff1a;3.3 示例二&#xff1a; 四、dialog 元素 一、拖拽事件 原生JavaScipt案例合集 JavaScript DOM基础 JavaScript 基础到高级 Canvas…...

独享IP vs. 共享IP:哪种更适合你?

无论是个人用户还是企业组织&#xff0c;在互联网上都需要一个唯一标识来与其他设备进行通信。这就涉及到使用独立分配给自己或多个用户分享的公共 IP 地址&#xff08;也称为共享 IP&#xff09;。那么&#xff0c;究竟应该选择独占一个专用地址还是与他人分享相同地址呢&…...

【Arduino27】DHT11温湿度传感器模拟值实验

硬件准备 DHT11温湿度&#xff1a;1个 面包板&#xff1a;1个 杜邦线&#xff1a;3根 硬件连线 VDD引脚接 5V 电源 DATE引脚接 4号 接口 GND引脚接 GND 接口 软件程序 #include<DHT.h>#define DHT11_pin 4 //温湿度传感器引脚DHT dht(DHT11_pin,DHT11);float tem…...

dockerfile基于apline将JDK20打包成镜像

dockerfile基于apline将JDK20打包成镜像 ​ 今天就来和大家聊聊如何把最新出版的JDK20打包成docker镜像&#xff0c;很多uu都会采用centos作为基础镜像&#xff0c;这么做会有一个问题&#xff0c;centos系统会含有很多库文件&#xff0c;这些库文件JDK程序并不是完全需要的&a…...

MATLAB基础-MAT文件的读写操作

简介 MAT文件是MATLAB格式的双精度二进制数据文件&#xff0c;由MATLAB软件创建&#xff0c;可以使用MATLAB软件再其他计算机上以其他浮点格式读取&#xff0c;同时也可以使用其他软件通过MATLAB的应用程序接口来进行读写操作。如果只是再MATLAB环境中处理数据&#xff0c;使用…...

PostgreSQL PG15 新功能 PG_WALINSPECT

开头还是介绍一下群&#xff0c;如果感兴趣PolarDB ,MongoDB ,MySQL ,PostgreSQL ,Redis &#xff0c;Oracle ,Oceanbase 等有问题&#xff0c;有需求都可以加群群内有各大数据库行业大咖&#xff0c;CTO&#xff0c;可以解决你的问题。加群请加微信号 liuaustin3 &#xff08;…...

时序预测 | MATLAB实现TCN-BiLSTM时间卷积双向长短期记忆神经网络时间序列预测

时序预测 | MATLAB实现TCN-BiLSTM时间卷积双向长短期记忆神经网络时间序列预测 目录 时序预测 | MATLAB实现TCN-BiLSTM时间卷积双向长短期记忆神经网络时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 1.MATLAB实现TCN-BiLSTM时间卷积双向长短期记忆神…...

数据结构和算法(2):向量

抽象数据类型 数组到向量 C/C 中&#xff0c;数组A[]中的元素与[0,n)内的编号一一对应&#xff0c;A[0],A[1],...,A[n-1]&#xff1b;反之&#xff0c;每个元素均由&#xff08;非负&#xff09;编号唯一指代&#xff0c;并可直接访问A[i] 的物理地址 Ai s&#xff0c;s 为单…...

mysql 大表如何ddl

大家好&#xff0c;我是蓝胖子&#xff0c;mysql对大表(千万级数据)的ddl语句&#xff0c;在生产上执行时一定要千万小心&#xff0c;一不小心就有可能造成业务阻塞&#xff0c;数据库io和cpu飙高的情况。今天我们就来看看如何针对大表执行ddl语句。 通过这篇文章&#xff0c;…...

C++新特性:智能指针

一 、为什么需要智能指针 智能指针主要解决以下问题&#xff1a; 1&#xff09;内存泄漏&#xff1a;内存手动释放&#xff0c;使用智能指针可以自动释放 2&#xff09;共享所有权指针的传播和释放&#xff0c;比如多线程使用同一个对象时析构问题&#xff0c;例如同样的数据…...

SAP FI之批量修改财务凭证的BAPI

文章目录 前言一、pandas是什么&#xff1f;二、使用步骤 1.引入库2.读入数据总结 前言 一般涉及修改财务凭证&#xff0c;或者其它凭证&#xff0c;不应直接更新数据库&#xff0c;而是使用系统提供的function module,或者BAPI&#xff0c;或者使用BDC。 一、 示例&#xf…...

Spring Boot + Vue的网上商城之商品分类

Spring Boot Vue的网上商城之商品分类 在网上商城中&#xff0c;商品分类是非常重要的一个功能&#xff0c;它可以帮助用户更方便地浏览和筛选商品。本文将介绍如何使用Spring Boot和Vue来实现商品分类的功能&#xff0c;包括一级分类和二级分类的管理以及前台按分类浏览商品…...

Docker 容器逃逸漏洞 (CVE-2020-15257)复现

漏洞概述 containerd是行业标准的容器运行时&#xff0c;可作为Linux和Windows的守护程序使用。在版本1.3.9和1.4.3之前的容器中&#xff0c;容器填充的API不正确地暴露给主机网络容器。填充程序的API套接字的访问控制验证了连接过程的有效UID为0&#xff0c;但没有以其他方式…...

Python 如何使用 csv、openpyxl 库进行读写 Excel 文件详细教程(更新中)

csv 基本概述 首先介绍下 csv (comma separated values)&#xff0c;即逗号分隔值&#xff08;也称字符分隔值&#xff0c;因为分隔符可以不是逗号&#xff09;&#xff0c;是一种常用的文本格式&#xff0c;用以存储表格数据&#xff0c;包括数字或者字符。 程序在处理数据时…...

$nextTick属性使用与介绍

属性介绍 $nextTick 是 Vue.js 中的一个重要方法&#xff0c;之前我们也说过$ref 等一些重要的属性&#xff0c;这次我们说$nextTick&#xff0c;$nextTick用于在 DOM 更新后执行回调函数。它通常用于处理 DOM 更新后的操作&#xff0c;因为 Vue 在更新 DOM 后不会立即触发回调…...

【群智能算法改进】一种改进的鹈鹕优化算法 IPOA算法[2]【Matlab代码#58】

文章目录 【获取资源请见文章第5节&#xff1a;资源获取】1. 原始POA算法2. 改进后的IPOA算法2.1 随机对立学习种群初始化2.2 动态权重系数2.3 透镜成像折射方向学习 3. 部分代码展示4. 仿真结果展示5. 资源获取 【获取资源请见文章第5节&#xff1a;资源获取】 1. 原始POA算法…...

k8s 入门到实战--部署应用到 k8s

k8s 入门到实战 01.png 本文提供视频版&#xff1a; 背景 最近这这段时间更新了一些 k8s 相关的博客和视频&#xff0c;也收到了一些反馈&#xff1b;大概分为这几类&#xff1a; 公司已经经历过服务化改造了&#xff0c;但还未接触过云原生。公司部分应用进行了云原生改造&…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

C++八股 —— 单例模式

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

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

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

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