当前位置: 首页 > 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 -> 红…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

CppCon 2015 学习:Time Programming Fundamentals

Civil Time 公历时间 特点&#xff1a; 共 6 个字段&#xff1a; Year&#xff08;年&#xff09;Month&#xff08;月&#xff09;Day&#xff08;日&#xff09;Hour&#xff08;小时&#xff09;Minute&#xff08;分钟&#xff09;Second&#xff08;秒&#xff09; 表示…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究

摘要&#xff1a;在消费市场竞争日益激烈的当下&#xff0c;传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序&#xff0c;探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式&#xff0c;分析沉浸式体验的优势与价值…...

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献

Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译&#xff1a; ### 胃肠道癌症的发病率呈上升趋势&#xff0c;且有年轻化倾向&#xff08;Bray等人&#xff0c;2018&#x…...