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

王道计算机数据结构+插入排序、冒泡排序、希尔排序、快速排序、简单选择排序

本内容是基于王道计算机数据结构的插入排序、冒泡排序、希尔排序、快速排序、简单选择排序整理。

文章目录

  • 插入排序
    • 算法
    • 性能
    • 代码
  • 冒泡排序
    • 算法
    • 性能
    • 代码
  • 希尔排序
    • 算法
    • 性能
    • 代码
  • 快速排序
    • 算法
    • 性能
    • 代码
  • 简单选择排序
    • 算法
    • 性能
    • 代码

插入排序

算法

算法思想:每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中,直到全部记录插入完成。

性能

  • 空间复杂度:O(1)
  • 时间复杂度:
    • 最好:原本就有序;O(n)
    • 最坏:原本为逆序;O(n2);
    • 平均:O(n2);
  • 稳定性:稳定;

代码

image.png
image.png
image.png

#include <iostream>
using namespace std;void InsertSort(int a[],int n) {int i, j, temp;for(i = 1; i < n; i++) {if (a[i] < a[i - 1]) {temp = a[i];for (j = i - 1; j >= 0 && a[j] > temp; j--) {a[j + 1] = a[j];}a[j + 1] = temp;}}
}void printfarray(int a[], int n) {for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;
}int main() {int a[8] = {38, 49, 65, 97, 76, 13, 27, 49};int n = 8;cout << "插入排序前的数组为: ";printfarray(a, n);cout << endl;InsertSort(a,n);cout << "插入排序后的数组为: ";printfarray(a, n);cout << endl;
}

image.png

冒泡排序

算法

  • 从后往前(或从前往后)两两比较相邻元素的值,若为逆序(即A[i-1]>A[i]),则交换它们,直到序列比较完。称这样过程为“一趟”冒泡排序。
  • 第一趟排序使关键字值最小的一个元素“冒”到最前面;
  • 每一趟排序都可以使一个元素移动到最终位置,已经确定最终位置的元素在之后的处理中无需再对比;
  • 若某一趟排序没有发生“交换”,说明此时已经整体有序。

性能

  • 空间复杂度:O(1)
  • 时间复杂度:
    • 最好:原本就有序;O(n)
    • 最坏:原本为逆序;O(n2);
    • 平均:O(n2);
  • 稳定性:稳定;

代码

image.png

#include <iostream>
using namespace std;void swap(int &a, int &b){int temp = a;a = b;b = temp;
}void BubbleSort(int a[],int n) {for(int i = 0; i < n-1; i++) {bool flag = false; // 表示本趟冒泡是否发生交换的标志for (int j = n - 1; j > i; j--) {if (a[j-1] > a[j]) {swap(a[j-1],a[j]);flag = true;}}if (flag == false) {return;}}
}void printfarray(int a[], int n) {for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;
}int main() {int a[8] = {38, 49, 65, 97, 76, 13, 27, 49};int n = 8;cout << "冒泡排序前的数组为: ";printfarray(a, n);cout << endl;BubbleSort(a,n);cout << "冒泡排序后的数组为: ";printfarray(a, n);cout << endl;
}

image.png

希尔排序

算法

  • 先将待排序表分割成若干形如L[i, i+d, i+2d, … ,i + kd]的“特殊”子表,对各个子表分别进行直接插入排序。缩小增量d,重复上述过程,直到d=1为止。
  • 先追求表中元素部分有序,再逐渐逼近全局有序。

性能

  • 空间复杂度:O(1)
  • 时间复杂度:未知,但优于直接插入排序
  • 稳定性:不稳定;

代码

image.png
image.png
image.png
image.png

#include <iostream>
using namespace std;void ShellSort(int a[],int n) {int i, j, d, temp;for (d = n / 2; d >= 1; d = d / 2) {for(i = d; i < n; i++) {if(a[i] < a[i-d]) {temp = a[i];for(j = i - d; j >= 0 && a[j] > temp; j-=d) {a[j + d] = a[j];}a[j + d] = temp;}}}
}void printfarray(int a[], int n) {for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;
}int main() {int a[11] = {38, 6, 9, 3, 49, 65, 97, 76, 13, 27, 49};int n = 11;cout << "希尔排序前的数组为: ";printfarray(a, n);cout << endl;ShellSort(a,n);cout << "希尔排序后的数组为: ";printfarray(a, n);cout << endl;
}

image.png

快速排序

算法

算法思想:在待排序表L[1 … n]中任取一个元素pivot作为枢轴(或基准,通常取首元素),通过一趟排序将待排序表划分为独立的两部分L[1 … k-1]和L[k+1 … n],使得L[1 … k-1]中的所有元素小于pivot,L[k+1 … n]中的所有元素大于等于pivot,则pivot放在了其最终位置L(k) 上,这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程,直至每部分内只有一个元素或空为止,即所有元素放在了其最终位置上。
算法表现主要取决于递归深度,若每次“划分”越均匀,则递归深度越低。“划分”越不均匀,递归深度越深。

性能

  • 空间复杂度:
    • 最好:O(n)
    • 最坏:O(log(n))
  • 时间复杂度:
    • 最好:每次划分很均匀;O(n2)
    • 最坏:原本为正序或逆序;O(n log(n));
    • 平均:O(n log(n));
  • 稳定性:不稳定;

代码

image.png
image.png

#include <iostream>
using namespace std;int Partition(int a[],int low, int high) {int pivot = a[low];while (low < high) {while(low < high && a[high] >= pivot) high--;a[low] = a[high];while(low < high && a[low] <= pivot) low++;a[high] = a[low];}a[low] = pivot;return low;
}void QuickSort(int a[],int low, int high) {if (low < high) {int pivotpos = Partition(a,low,high); // 划分QuickSort(a, low, pivotpos-1); // 划分左子表QuickSort(a, pivotpos + 1, high); // 划分右子表}
}void printfarray(int a[], int n) {for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;
}int main() {int a[11] = {38, 6, 9, 3, 49, 65, 97, 76, 13, 27, 49};int n = 11;cout << "快速排序前的数组为: ";printfarray(a, n);cout << endl;QuickSort(a,0,n-1);cout << "快速排序后的数组为: ";printfarray(a, n);cout << endl;
}

image.png

简单选择排序

算法

  • 每一趟在待排序元素中选取关键字最小的元素加入有序子序列
  • 必须进行总共 n - 1 趟处理;

性能

  • 空间复杂度:O(1)
  • 时间复杂度:O(n2)
  • 稳定性:不稳定;

代码

image.png

#include <iostream>
using namespace std;void swap(int &a, int &b){int temp = a;a = b;b = temp;
}void SelectSort(int a[],int n) {for (int i = 0; i < n-1; i++) {int min = i;for(int j = i + 1; j < n; j++) {if (a[j] < a[min])min = j;}if (min != i) {swap(a[i],a[min]);}}
}void printfarray(int a[], int n) {for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;
}int main() {int a[11] = {38, 6, 9, 3, 49, 65, 97, 76, 13, 27, 49};int n = 11;cout << "选择排序前的数组为: ";printfarray(a, n);cout << endl;SelectSort(a,n);cout << "选择排序后的数组为: ";printfarray(a, n);cout << endl;
}

image.png

相关文章:

王道计算机数据结构+插入排序、冒泡排序、希尔排序、快速排序、简单选择排序

本内容是基于王道计算机数据结构的插入排序、冒泡排序、希尔排序、快速排序、简单选择排序整理。 文章目录 插入排序算法性能代码 冒泡排序算法性能代码 希尔排序算法性能代码 快速排序算法性能代码 简单选择排序算法性能代码 插入排序 算法 算法思想&#xff1a;每次将一个…...

python爬虫学习(三十三天)---多线程上篇

hello&#xff0c;小伙伴们&#xff01;我是喔的嘛呀。今天我们来学习多线程方面的知识。 目录 一、了解多线程 &#xff08;1&#xff09;大概描述 &#xff08;2&#xff09;多线程爬虫的优势 &#xff08;3&#xff09;多线程爬虫的实现方式 &#xff08;4&#xff09…...

JavaScript 原型链那些事

在讲原型之前我们先来了解一下函数。 在JS中&#xff0c;函数的本质就是对象&#xff0c;它与其他对象不同的是&#xff0c;创建它的构造函数与创建其他对象的构造函数不一样。那产生函数对象的构造函数是什么呢&#xff1f;是一个叫做Function的特殊函数&#xff0c;通过newFu…...

nginx的知识面试易考点

Nginx概念 Nginx 是一个高性能的 HTTP 和反向代理服务。其特点是占有内存少&#xff0c;并发能力强&#xff0c;事实上nginx的并发能力在同类型的网页服务器中表现较好。 Nginx 专为性能优化而开发&#xff0c;性能是其最重要的考量指标&#xff0c;实现上非常注重效率&#…...

每日Attention学习9——Efficient Channel Attention

模块出处 [CVPR 20] [link] [code] ECA-Net: Efficient Channel Attention for Deep Convolutional Neural Networks 模块名称 Efficient Channel Attention (ECA) 模块作用 通道注意力 模块结构 模块代码 import torch import torch.nn as nn import torch.nn.functional …...

Java语言程序设计——篇三(1)

选择结构 概述选择单分支if语句例题讲解 双分支if-else语句例题讲解 条件运算符多分支的if-else语句例题讲解 嵌套的if语句例题讲解 switch语句结构例题讲解代码演示运行结果 概述 Java中的控制结构&#xff0c;包括&#xff1a; 1、选择结构( if、if-else、switch ) 2、循环结…...

基于SpringBoot实现轻量级的动态定时任务调度

在使用SpringBoot框架进行开发时&#xff0c;一般都是通过Scheduled注解进行定时任务的开发&#xff1a; Component public class TestTask {Scheduled(cron"0/5 * * * * ? ") //每5秒执行一次public void execute(){SimpleDateFormat df new SimpleDateFormat(…...

夸克升级“超级搜索框” 推出AI搜索为中心的一站式AI服务

大模型时代&#xff0c;生成式AI如何革新搜索产品&#xff1f;阿里智能信息事业群旗下夸克“举手答题”。7月10日&#xff0c;夸克升级“超级搜索框”&#xff0c;推出以AI搜索为中心的一站式AI服务&#xff0c;为用户提供从检索、创作、总结&#xff0c;到编辑、存储、分享的一…...

element-ui el-select选择器组件下拉框增加自定义按钮

element-ui el-select选择器组件下拉框增加自定义按钮 先看效果 原理&#xff1a;在el-select下添加禁用的el-option&#xff0c;将其value绑定为undefined&#xff0c;然后覆盖el-option禁用状态下的默认样式即可 示例代码如下&#xff1a; <template><div class…...

Python基于you-get下载网页上的视频

​ 1.python 下载地址 下载 : https://www.python.org/downloads/ 2. 配置环境变量 配置 python_home 地址 配置 python_scripts 地址 在path 中加入对应配置 3. 验证 ​ C:\Users>python --version Python 3.12.4C:\Users>wheel version wheel 0.43.04. 下载 c…...

大模型/NLP/算法面试题总结3——BERT和T5的区别?

1、BERT和T5的区别&#xff1f; BERT和T5是两种著名的自然语言处理&#xff08;NLP&#xff09;模型&#xff0c;它们在架构、训练方法和应用场景上有一些显著的区别。以下是对这两种模型的详细比较&#xff1a; 架构 BERT&#xff08;Bidirectional Encoder Representation…...

vue3项目打包的时候,怎么区别测试环境,和本地环境

在Vue 3项目中区别测试环境和本地环境&#xff0c;并标记接口的方法可以通过环境变量来实现。 首先&#xff0c;你可以在你的项目根目录下创建一个.env文件&#xff0c;并定义你的环境变量。比如&#xff0c;你可以创建.env.local作为本地环境的配置文件&#xff0c;.env.test…...

小特性 大用途 —— YashanDB JDBC驱动的这些特性你都get了吗?

在现代数据库应用场景中&#xff0c;系统的高可用性和负载均衡是确保服务稳定性的基石。YashanDB JDBC驱动通过其创新的多IP配置特性&#xff0c;为用户带来了简洁而强大的解决方案&#xff0c;以实现数据库连接的高可用性和负载均衡&#xff0c;满足企业级应用的高要求。 01 …...

全网最全的软件测试面试八股文

前面看到了一些面试题&#xff0c;总感觉会用得到&#xff0c;但是看一遍又记不住&#xff0c;所以我把面试题都整合在一起&#xff0c;都是来自各路大佬的分享&#xff0c;为了方便以后自己需要的时候刷一刷&#xff0c;不用再到处找题&#xff0c;今天把自己整理的这些面试题…...

VMware虚拟机配置桥接网络

转载&#xff1a;虚拟机桥接网络配置 一、VMware三种网络连接方式 VMware提供了三种网络连接方式&#xff0c;VMnet0, VMnet1, Vmnet8&#xff0c;分别代表桥接&#xff0c;Host-only及NAT模式。在VMware的编辑-虚拟网络编辑器可看到对应三种连接方式的设置&#xff08;如下图…...

华为机考真题 -- 攀登者1

题目描述: 攀登者喜欢寻找各种地图,并且尝试攀登到最高的山峰。地图表示为一维数组,数组的索引代表水平位置,数组的元素代表相对海拔高度。其中数组元素0代表地面。 一个山脉可能有多座山峰(山峰定义:高度大于相邻位置的高度,或在地图边界且高度大于相邻的高度)。登山者…...

深入理解Python密码学:使用PyCrypto库进行加密和解密

深入理解Python密码学&#xff1a;使用PyCrypto库进行加密和解密 引言 在现代计算领域&#xff0c;信息安全逐渐成为焦点话题。密码学&#xff0c;作为信息保护的关键技术之一&#xff0c;允许我们加密&#xff08;保密&#xff09;和解密&#xff08;解密&#xff09;数据。P…...

MMSegmentation笔记

如何训练自制数据集&#xff1f; 首先需要在 mmsegmentation/mmseg/datasets 目录下创建一个自制数据集的配置文件&#xff0c;以我的苹果叶片病害分割数据集为例&#xff0c;创建了mmsegmentation/mmseg/datasets/appleleafseg.py 可以看到&#xff0c;这个配置文件主要定义…...

Python基础语法:变量和数据类型详解(整数、浮点数、字符串、布尔值)①

文章目录 变量和数据类型详解&#xff08;整数、浮点数、字符串、布尔值&#xff09;一、变量二、数据类型1. 整数&#xff08;int&#xff09;2. 浮点数&#xff08;float&#xff09;3. 字符串&#xff08;str&#xff09;4. 布尔值&#xff08;bool&#xff09; 三、类型转换…...

【C++航海王:追寻罗杰的编程之路】关联式容器的底层结构——红黑树

目录 1 -> 红黑树 1.1 -> 红黑树的概念 1.2 -> 红黑树的性质 1.3 -> 红黑树节点的定义 1.4 -> 红黑树的结构 1.5 -> 红黑树的插入操作 1.6 -> 红黑树的验证 1.8 -> 红黑树与AVL树的比较 2 -> 红黑树模拟实现STL中的map与set 2.1 -> 红…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...