当前位置: 首页 > 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;但还未接触过云原生。公司部分应用进行了云原生改造&…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程

鸿蒙电脑版操作系统来了&#xff0c;很多小伙伴想体验鸿蒙电脑版操作系统&#xff0c;可惜&#xff0c;鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机&#xff0c;来体验大家心心念念的鸿蒙系统啦&#xff01;注意&#xff1a;虚拟…...

stm32进入Infinite_Loop原因(因为有系统中断函数未自定义实现)

这是系统中断服务程序的默认处理汇编函数&#xff0c;如果我们没有定义实现某个中断函数&#xff0c;那么当stm32产生了该中断时&#xff0c;就会默认跑这里来了&#xff0c;所以我们打开了什么中断&#xff0c;一定要记得实现对应的系统中断函数&#xff0c;否则会进来一直循环…...

在ubuntu等linux系统上申请https证书

使用 Certbot 自动申请 安装 Certbot Certbot 是 Let’s Encrypt 官方推荐的自动化工具&#xff0c;支持多种操作系统和服务器环境。 在 Ubuntu/Debian 上&#xff1a; sudo apt update sudo apt install certbot申请证书 纯手动方式&#xff08;不自动配置&#xff09;&…...

板凳-------Mysql cookbook学习 (十--2)

5.12 模式匹配中的大小写问题 mysql> use cookbook Database changed mysql> select a like A, a regexp A; ------------------------------ | a like A | a regexp A | ------------------------------ | 1 | 1 | --------------------------…...

python3GUI--基于PyQt5+DeepSort+YOLOv8智能人员入侵检测系统(详细图文介绍)

文章目录 一&#xff0e;前言二&#xff0e;技术介绍1.PyQt52.DeepSort3.卡尔曼滤波4.YOLOv85.SQLite36.多线程7.入侵人员检测8.ROI区域 三&#xff0e;核心功能1.登录注册1.登录2.注册 2.主界面1.主界面简介2.数据输入3.参数配置4.告警配置5.操作控制台6.核心内容显示区域7.检…...