排序算法(二)
1.希尔排序-Shell Sort
1.算法原理
将未排序序列按照增量gap的不同分割为若干个子序列,然后分别进行插入排序,得到若干组排好序的序列;
缩小增量gap,并对分割为的子序列进行插入排序;最后一次的gap=1,即整个序列,但此时已经基本有序,对整个序列使用插入排序,得到最终排好序的序列
公式表示:gap={n/2,(n/2)/2,...,1} = {t1,t2,...,tk}
即一共排序k次,增量gap称作希尔增量
算法图解可以参考以下两种:


2.算法复杂度
时间复杂度:最优复杂度:O(nlogn);最差复杂度:O(n2);平均复杂度:O(nlogn)
空间复杂度:O(1)
3.算法实现-Java
public int[] shellSort(int[] arr){int len = arr.length;int gap = len / 2;while(gap > 0){for(int i = gap; i < len; i++){int currentValue = arr[i];int preIndex = i - gap;while(preIndex >= 0 && arr[preIndex] > currentValue){arr[preIndex + gap] = arr[preIndex];preIndex -= gap;}arr[preIndex + gap] = currentValue;}gap = gap / 2;}return arr;
}
2.归并排序-Merge Sort
1.算法原理
将未排序序列的所有元素分为若干组,每个元素为一组;将每组元素进行两两合并,合并时按照从小到大(或者从大到小)对元素进行排序,排序时比较每一组元素的头部即可;重复此步骤,直到最终只剩下一组数据,则排序完成
2.算法复杂度
时间复杂度:最优复杂度:O(nlogn);最差复杂度:O(nlogn);平均复杂度:O(nlogn)
空间复杂度:O(1)
3.算法实现-Java
public class MergeSort {public static void main(String[] args) {int[] a = {9, 6, 2, 3, 7, 4, 8, 5,1,0};int L = 0;int R = a.length - 1;mergSort(a, L, R);System.out.println(Arrays.toString(a));}static void mergSort(int[] arr, int L, int R) {//只有一个数,直接返回if (L == R) {return;} else {int M = (L + R) / 2;mergSort(arr, L, M);mergSort(arr, M + 1, R);merge(arr, L, M + 1, R);}}static void merge(int[] arr, int L, int M, int R) {int left_size = M - L;int right_size = R - M + 1;int[] L_arr = new int[left_size];int[] R_arr = new int[right_size];// 1 填充左边的数组for (int i = L; i < M; i++) {L_arr[i - L] = arr[i];}// 2 填充右边的数组for (int i = M; i <= R; i++) {R_arr[i - M] = arr[i];}// 3 合并int i = 0, j = 0, k = L;while (i < left_size && j < right_size) {if (L_arr[i] > R_arr[j]) {arr[k] = R_arr[j];k++;j++;} else {arr[k] = L_arr[i];i++;k++;}}// 4 若右边数组已空,把剩余左边数组补上while (i < left_size) {arr[k] = L_arr[i];i++;k++;}// 5 若左边数组已空,同上while (j < right_size) {arr[k] = R_arr[j];k++;j++;}}
}
3.快速排序-Quick Sort
1.算法原理
在未排序的序列中选择一个数作为基准(一般选择序列的第一个数),序列的最左侧和最右侧设置两个指针L和R;
其中L从左往右移动,R从右往左移动;
首先R从右向左移动一位,若指向的元素小于(大于)基准,则将其移动到序列的最左边(最右边),然后L从左向右移动一位,指向的元素与基准比较后,执行相同操作;
直到L与R移动到同一位置,说明第一次排序完成,此时相遇的位置就是基准元素的位置;
接下来,在基准的左右两边序列各选一个基准,执行上述操作,直到排序完成
2.算法复杂度
时间复杂度:最优复杂度:O(nlogn);最差复杂度:O(nlogn);平均复杂度:O(nlogn)
空间复杂度:O(1)
3.算法实现-Java
public static void quickSort(int[] arr,int low,int high){int i,j,temp,t;if(low > high){return;}i = low;j = high;//temp为基准元素temp = arr[low];while (i < j) {//右边,依次往左递减while (temp <= arr[j] && i < j) {j--;}//左边,依次往右递增while (temp >= arr[i] && i < j) {i++;}//如果满足条件则交换if (i < j) {t = arr[j];arr[j] = arr[i];arr[i] = t;}}//最后将基准为与i和j相等位置的数字交换arr[low] = arr[i];arr[i] = temp;//递归调用左半数组quickSort(arr, low, j-1);//递归调用右半数组quickSort(arr, j+1, high);}
相关文章:
排序算法(二)
1.希尔排序-Shell Sort 1.算法原理 将未排序序列按照增量gap的不同分割为若干个子序列,然后分别进行插入排序,得到若干组排好序的序列; 缩小增量gap,并对分割为的子序列进行插入排序;最后一次的gap1,即整个…...
CVPR 2023 | 无监督深度概率方法在部分点云配准中的应用
注1:本文系“计算机视觉/三维重建论文速递”系列之一,致力于简洁清晰完整地介绍、解读计算机视觉,特别是三维重建领域最新的顶会/顶刊论文(包括但不限于 Nature/Science及其子刊; CVPR, ICCV, ECCV, NeurIPS, ICLR, ICML, TPAMI, IJCV 等)。本次介绍的论文是:2023年,CVPR,…...
HTTP隧道识别与防御:机器学习的解决方案
随着互联网的快速发展,HTTP代理爬虫已成为数据采集的重要工具。然而,随之而来的是恶意爬虫对网络安全和数据隐私的威胁。为了更好地保护网络环境和用户数据,我们进行了基于机器学习的HTTP代理爬虫识别与防御的研究。以增强对HTTP代理爬虫的识…...
【MMU】认识 MMU 及内存映射的流程
MMU(Memory Manager Unit),是内存管理单元,负责将虚拟地址转换成物理地址。除此之外,MMU 实现了内存保护,进程无法直接访问物理内存,防止内存数据被随意篡改。 目录 一、内存管理体系结构 1、…...
Clion开发Stm32之存储模块(W25Q64)驱动编写
前言 涵盖之前文章: Clion开发STM32之HAL库SPI封装(基础库) W25Q64驱动 头文件 #ifndef F1XX_TEMPLATE_MODULE_W25Q64_H #define F1XX_TEMPLATE_MODULE_W25Q64_H#include "sys_core.h" /* Private typedef ---------------------------------------------------…...
SpringBoot动态切换数据源
SpringBoot整合多数据源,动态添加新数据源并切换 1.需求2.创建数据源配置类3.切换数据源4.切换数据源管理类5.使用案例5.AOP切面拦截 1.需求 低代码服务需要给多套系统进行功能配置,要求表结构必须生成在对应系统的数据库中,所以表结构的生成…...
[C++项目] Boost文档 站内搜索引擎(4): 搜索的相关接口的实现、线程安全的单例index接口、cppjieba分词库的使用、综合调试...
有关Boost文档搜索引擎的项目的前三篇文章, 已经分别介绍分析了: 项目背景: 🫦[C项目] Boost文档 站内搜索引擎(1): 项目背景介绍、相关技术栈、相关概念介绍…文档解析、处理模块parser的实现: 🫦[C项目] Boost文档 站内搜索引擎(2): 文档文本解析模块…...
SAP ABAP元素域值描述通过函数(DD_DOMVALUE_TEXT_GET)获取
代码如下: PERFORM FRM_GET_DOMVALUE_TEXT USING ZMMD_ZFLZQ <GFS_DATA>-ZFLZQ CHANGING <GFS_DATA>-ZZQTEXT .IF <GFS_DATA>-ZXYLX IS NOT INITIAL .PERFORM FRM_GET_DOMVALUE_TEXT USING ZMMD_ZXYLX <GFS_DATA>-ZXYLX CHANGING <GFS_…...
原型模式与享元模式:提升系统性能的利器
原型模式和享元模式,前者是在创建多个实例时,对创建过程的性能进行调优;后者是用减 少创建实例的方式,来调优系统性能。这么看,你会不会觉得两个模式有点相互矛盾呢? 在有些场景下,我们需要重复…...
uniapp封装手写签名
组件代码 cat-signature <template><view v-if"visibleSync" class"cat-signature" :class"{visible:show}" touchmove.stop.prevent"moveHandle"><view class"mask" tap"close" /><view c…...
掌握 JVM 调优命令
常用命令 1、jps查看当前 java 进程2、jinfo实时查看和调整 JVM 配置参数3、jstat查看虚拟机统计信息4、jstack查看线程堆栈信息5、jmap查看堆内存的快照信息 JVM 日常调优总结起来就是:首先通过 jps 命令查看当前进程,然后根据 pid 通过 jinfo 命令查看…...
扩增子分析流程——Lotus2: 一行命令完成所有分析
为什么介绍lotus2 因为快,作者比较了lotus2流程和qiime2、dada2、vsearch等,lotus2的速度最快、占用内存最小。 因为方便,只需要一行代码,即可完成全部分析。 lotus2 -i Example/ -m Example/miSeqMap.sm.txt -o myTestRun而且分…...
微服务 云原生:搭建 Harbor 私有镜像仓库
Harbor官网 写在文前: 本文中用到机器均为虚拟机 CentOS-7-x86_64-Minimal-2009 镜像。 基础设施要求 虚拟机配置达到最低要求即可,本次系统中使用 docker 24.0.4、docker-compose 1.29.2。docker 及 docker-compose 的安装可以参考上篇文章 微服务 &am…...
Ceph入门到精通-远程开发Windows下使用SSH密钥实现免密登陆Linux服务器
工具: win10、WinSCP 服务器生成ssh密钥: 打开终端,使账号密码登录,输入命令 ssh-keygen -t rsa Winscp下载 Downloading WinSCP-6.1.1-Setup.exe :: WinSCP window 生成密钥 打开powershell ssh-keygen -t rsa 注意路径 …...
APP外包开发的开发语言对比
在开发iOS APP时有两种语言可以选择,Swift(Swift Programming Language)和 Objective-C(Objective-C Programming Language),它们是两种不同的编程语言,都被用于iOS和macOS等苹果平台的软件开发…...
基于Python++PyQt5马尔科夫模型的智能AI即兴作曲—深度学习算法应用(含全部工程源码+测试数据)
目录 前言总体设计系统整体结构图系统流程图 运行环境Python 环境PC环境配置 模块实现1. 钢琴伴奏制作1)和弦的实现2)和弦级数转为当前调式音阶3)根据预置节奏生成伴奏 2. 乐句生成1)添加音符2)旋律生成3)节…...
Android中简单封装Livedata工具类
Android中简单封装Livedata工具类 前言: 之前讲解过livedata和viewmodel的简单使用,也封装过room工具类,本文是对livedata的简单封装和使用,先是封装了一个简单的工具类,然后实现了一个倒计时工具类的封装. 1.LiveD…...
国内大模型在局部能力上已超ChatGPT
中文大模型正在后来居上,也必须后来居上。 数科星球原创 作者丨苑晶 编辑丨大兔 从GPT3.5彻底出圈后,大模型的影响力开始蜚声国际。一段时间内,国内科技公司可谓被ChatGPT按在地上打,毫无还手之力。 彼时,很多企业…...
监控设置ip地址怎么设置
监控设备的IP地址设置是保障监控系统正常工作的基础。通过设置IP地址,我们可以确定监控设备在局域网内的位置,并远程访问监控设备进行实时查看、存储视频等操作。下面虎观代理小二二将介绍具体步骤。 方法一: 和电脑连接在一起,…...
力扣:56. 合并区间(Python3)
题目: 以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。 来源:力扣(Lee…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
莫兰迪高级灰总结计划简约商务通用PPT模版
莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...
