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

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

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

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

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...