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

排序算法(二)

1.希尔排序-Shell Sort

1.算法原理

        将未排序序列按照增量gap的不同分割为若干个子序列,然后分别进行插入排序,得到若干组排好序的序列;

        缩小增量gap,并对分割为的子序列进行插入排序;最后一次的gap=1,即整个序列,但此时已经基本有序,对整个序列使用插入排序,得到最终排好序的序列

        公式表示:gap={n/2,(n/2)/2,...,1} = {t1,t2,...,tk}

        即一共排序k次,增量gap称作希尔增量

算法图解可以参考以下两种:

shell_sort

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的不同分割为若干个子序列&#xff0c;然后分别进行插入排序&#xff0c;得到若干组排好序的序列&#xff1b; 缩小增量gap&#xff0c;并对分割为的子序列进行插入排序&#xff1b;最后一次的gap1&#xff0c;即整个…...

CVPR 2023 | 无监督深度概率方法在部分点云配准中的应用

注1:本文系“计算机视觉/三维重建论文速递”系列之一,致力于简洁清晰完整地介绍、解读计算机视觉,特别是三维重建领域最新的顶会/顶刊论文(包括但不限于 Nature/Science及其子刊; CVPR, ICCV, ECCV, NeurIPS, ICLR, ICML, TPAMI, IJCV 等)。本次介绍的论文是:2023年,CVPR,…...

HTTP隧道识别与防御:机器学习的解决方案

随着互联网的快速发展&#xff0c;HTTP代理爬虫已成为数据采集的重要工具。然而&#xff0c;随之而来的是恶意爬虫对网络安全和数据隐私的威胁。为了更好地保护网络环境和用户数据&#xff0c;我们进行了基于机器学习的HTTP代理爬虫识别与防御的研究。以增强对HTTP代理爬虫的识…...

【MMU】认识 MMU 及内存映射的流程

MMU&#xff08;Memory Manager Unit&#xff09;&#xff0c;是内存管理单元&#xff0c;负责将虚拟地址转换成物理地址。除此之外&#xff0c;MMU 实现了内存保护&#xff0c;进程无法直接访问物理内存&#xff0c;防止内存数据被随意篡改。 目录 一、内存管理体系结构 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整合多数据源&#xff0c;动态添加新数据源并切换 1.需求2.创建数据源配置类3.切换数据源4.切换数据源管理类5.使用案例5.AOP切面拦截 1.需求 低代码服务需要给多套系统进行功能配置&#xff0c;要求表结构必须生成在对应系统的数据库中&#xff0c;所以表结构的生成…...

[C++项目] Boost文档 站内搜索引擎(4): 搜索的相关接口的实现、线程安全的单例index接口、cppjieba分词库的使用、综合调试...

有关Boost文档搜索引擎的项目的前三篇文章, 已经分别介绍分析了: 项目背景: &#x1fae6;[C项目] Boost文档 站内搜索引擎(1): 项目背景介绍、相关技术栈、相关概念介绍…文档解析、处理模块parser的实现: &#x1fae6;[C项目] Boost文档 站内搜索引擎(2): 文档文本解析模块…...

SAP ABAP元素域值描述通过函数(DD_DOMVALUE_TEXT_GET)获取

代码如下&#xff1a; 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_…...

原型模式与享元模式:提升系统性能的利器

原型模式和享元模式&#xff0c;前者是在创建多个实例时&#xff0c;对创建过程的性能进行调优&#xff1b;后者是用减 少创建实例的方式&#xff0c;来调优系统性能。这么看&#xff0c;你会不会觉得两个模式有点相互矛盾呢&#xff1f; 在有些场景下&#xff0c;我们需要重复…...

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 日常调优总结起来就是&#xff1a;首先通过 jps 命令查看当前进程&#xff0c;然后根据 pid 通过 jinfo 命令查看…...

扩增子分析流程——Lotus2: 一行命令完成所有分析

为什么介绍lotus2 因为快&#xff0c;作者比较了lotus2流程和qiime2、dada2、vsearch等&#xff0c;lotus2的速度最快、占用内存最小。 因为方便&#xff0c;只需要一行代码&#xff0c;即可完成全部分析。 lotus2 -i Example/ -m Example/miSeqMap.sm.txt -o myTestRun而且分…...

微服务 云原生:搭建 Harbor 私有镜像仓库

Harbor官网 写在文前&#xff1a; 本文中用到机器均为虚拟机 CentOS-7-x86_64-Minimal-2009 镜像。 基础设施要求 虚拟机配置达到最低要求即可&#xff0c;本次系统中使用 docker 24.0.4、docker-compose 1.29.2。docker 及 docker-compose 的安装可以参考上篇文章 微服务 &am…...

Ceph入门到精通-远程开发Windows下使用SSH密钥实现免密登陆Linux服务器

工具&#xff1a; win10、WinSCP 服务器生成ssh密钥&#xff1a; 打开终端&#xff0c;使账号密码登录&#xff0c;输入命令 ssh-keygen -t rsa Winscp下载 Downloading WinSCP-6.1.1-Setup.exe :: WinSCP window 生成密钥 打开powershell ssh-keygen -t rsa 注意路径 …...

APP外包开发的开发语言对比

在开发iOS APP时有两种语言可以选择&#xff0c;Swift&#xff08;Swift Programming Language&#xff09;和 Objective-C&#xff08;Objective-C Programming Language&#xff09;&#xff0c;它们是两种不同的编程语言&#xff0c;都被用于iOS和macOS等苹果平台的软件开发…...

基于Python++PyQt5马尔科夫模型的智能AI即兴作曲—深度学习算法应用(含全部工程源码+测试数据)

目录 前言总体设计系统整体结构图系统流程图 运行环境Python 环境PC环境配置 模块实现1. 钢琴伴奏制作1&#xff09;和弦的实现2&#xff09;和弦级数转为当前调式音阶3&#xff09;根据预置节奏生成伴奏 2. 乐句生成1&#xff09;添加音符2&#xff09;旋律生成3&#xff09;节…...

Android中简单封装Livedata工具类

Android中简单封装Livedata工具类 前言&#xff1a; 之前讲解过livedata和viewmodel的简单使用&#xff0c;也封装过room工具类&#xff0c;本文是对livedata的简单封装和使用&#xff0c;先是封装了一个简单的工具类&#xff0c;然后实现了一个倒计时工具类的封装. 1.LiveD…...

国内大模型在局部能力上已超ChatGPT

中文大模型正在后来居上&#xff0c;也必须后来居上。 数科星球原创 作者丨苑晶 编辑丨大兔 从GPT3.5彻底出圈后&#xff0c;大模型的影响力开始蜚声国际。一段时间内&#xff0c;国内科技公司可谓被ChatGPT按在地上打&#xff0c;毫无还手之力。 彼时&#xff0c;很多企业…...

监控设置ip地址怎么设置

监控设备的IP地址设置是保障监控系统正常工作的基础。通过设置IP地址&#xff0c;我们可以确定监控设备在局域网内的位置&#xff0c;并远程访问监控设备进行实时查看、存储视频等操作。下面虎观代理小二二将介绍具体步骤。 方法一&#xff1a; 和电脑连接在一起&#xff0c;…...

力扣:56. 合并区间(Python3)

题目&#xff1a; 以数组 intervals 表示若干个区间的集合&#xff0c;其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间&#xff0c;并返回 一个不重叠的区间数组&#xff0c;该数组需恰好覆盖输入中的所有区间 。 来源&#xff1a;力扣&#xff08;Lee…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...