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

排序算法基本原理及实现1

                                                                                             

                                   📑打牌 : da pai ge的个人主页
                                   🌤️个人专栏 : da pai ge的博客专栏
                                  ☁️宝剑锋从磨砺出,梅花香自苦寒来

📑插入排序

📑直接插入排序-原理

整个区间被分为
1. 有序区间
2. 无序区间
每次选择无序区间的第一个元素,在有序区间内选择合适的位置插入

📑实现

public static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {// 有序区间: [0, i)// 无序区间: [i, array.length)int v = array[i]; // 无序区间的第一个数int j = i - 1;// 不写 array[j] == v 是保证排序的稳定性for (; j >= 0 && array[j] > v; j--) {array[j + 1] = array[j];}array[j + 1] = v;}
}
时间复杂度
空间复杂度
最好O(n)
平均 最坏 O(n^2)
数据有序
数据逆序

📑性能分析

稳定性:稳定
插入排序,初始数据越接近有序,时间效率越高。

📑折半插入排序

在有序区间选择数据应该插入的位置时,因为区间的有序性,可以利用折半查找的思想。
public static void bsInsertSort(int[] array) {for (int i = 1; i < array.length; i++) {int v = array[i];int left = 0;int right = i;// [left, right)// 需要考虑稳定性while (left < right) {int m = (left + right) / 2;if (v >= array[m]) {left = m + 1;} else {right = m;}}// 搬移for (int j = i; j > left; j--) {array[j] = array[j - 1];}

📑希尔排序

📑原理

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有
距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达 =1 时,
所有记录在统一组内排好序。
1. 希尔排序是对直接插入排序的优化。
2. gap > 1 时都是预排序,目的是让数组更接近于有序。当 gap == 1 时,数组已经接近有序的了,这样就会很
快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
array [ left ] = v ;
时间复杂度
空间复杂度
最好O(n)
平均O(n^1.3)
最坏O(n^2)
数据有序
比较难构造

📑性能分析

稳定性:不稳定

📑选择排序

📑直接选择排序-原理

public static void shellSort(int[] array) {int gap = array.length;while (gap > 1) {insertSortGap(array, gap);gap = (gap / 3) + 1; // OR gap = gap / 2;}insertSortGap(array, 1);
}
private static void insertSortGap(int[] array, int gap) {for (int i = 1; i < array.length; i++) {int v = array[i];int j = i - gap;for (; j >= 0 && array[j] > v; j -= gap) {array[j + gap] = array[j];}array[j + gap] = v;}
}

时间复杂度
空间复杂度
O(n^2)
O(1)
数据不敏感
数据不敏感
每一次从无序区间选出最大(或最小)的一个元素,存放在无序区间的最后(或最前),直到全部待排序的数据元素
排完 。
public static void selectSort(int[] array) {for (int i = 0; i < array.length - 1; i++) {// 无序区间: [0, array.length - i)// 有序区间: [array.length - i, array.length)int max = 0;for (int j = 1; j < array.length - i; j++) {if (array[j] > array[max]) {max = j;}}int t = array[max];array[max] = array[array.length - i - 1];array[array.length - i - 1] = t;}
}
int[] a = { 9, 2, 5a, 7, 4, 3, 6, 5b };
// 交换中该情况无法识别,保证 5a 还在 5b 前边
public static void selectSortOP(int[] array) {

📑性能分析

稳定性:不稳定

📑双向选择排序

每一次从无序区间选出最小 + 最大的元素,存放在无序区间的最前和最后,直到全部待排序的数据元素排完 。

📑堆排序

📑原理

基本原理也是选择排序,只是不在使用遍历的方式查找无序区间的最大的数,而是通过堆来选择无序区间的最大的

数。
注意: 排升序要建大堆;排降序要建小堆。
 
 int low = 0;int high = array.length - 1;// [low, high] 表示整个无序区间// 无序区间内只有一个数也可以停止排序了while (low <= high) {int min = low;int max = low;for (int i = low + 1; i <= max; i++) {if (array[i] < array[min]) {min = i;}if (array[i] > array[max]) {max = i;}}swap(array, min, low);// 见下面例子讲解if (max == low) {max = min;}swap(array, max, high);}
}
private void swap(int[] array, int i, int j) {int t = array[i];array[i] = array[j];array[j] = t;
}
array = { 9, 5, 2, 7, 3, 6, 8 }; // 交换之前
// low = 0; high = 6
// max = 0; min = 2
array = { 2, 5, 9, 7, 3, 6, 8 }; // 将最小的交换到无序区间的最开始后
// max = 0,但实际上最大的数已经不在 0 位置,而是被交换到 min 即 2 位置了
// 所以需要让 max = min 即 max = 2
array = { 2, 5, 8, 7, 3, 6, 9 }; // 将最大的交换到无序区间的最结尾后

📑实现

public static void heapSort(int[] array) {createHeap(array);for (int i = 0; i < array.length - 1; i++) {// 交换前// 无序区间: [0, array.length - i)// 有序区间: [array.length - i, array.length)swap(array, 0, array.length - i - 1);// 交换后// 无序区间: [0, array.length - i - 1)// 有序区间: [array.length - i - 1, array.length)// 无序区间长度: array.length - i - 1shiftDown(array, array.length - i - 1, 0);}
}

相关文章:

排序算法基本原理及实现1

&#x1f4d1;打牌 &#xff1a; da pai ge的个人主页 &#x1f324;️个人专栏 &#xff1a; da pai ge的博客专栏 ☁️宝剑锋从磨砺出&#xff0c;梅花香自苦寒来 &#x1f4d1;插入排序 &#x1f4…...

Unity 轨道展示系统(DollyMotion)

DollyMotion &#x1f371;功能展示&#x1f959;使用&#x1f4a1;设置路径点&#x1f4a1;触发点位切换&#x1f4a1;动态更新路径点&#x1f4a1;事件触发&#x1f4a1;设置路径&#x1f4a1;设置移动方案固定速度方向最近路径方向 &#x1f4a1;设置移动速度曲线 传送门 &a…...

优维低代码实践:搜索功能

优维低代码技术专栏&#xff0c;是一个全新的、技术为主的专栏&#xff0c;由优维技术委员会成员执笔&#xff0c;基于优维7年低代码技术研发及运维成果&#xff0c;主要介绍低代码相关的技术原理及架构逻辑&#xff0c;目的是给广大运维人提供一个技术交流与学习的平台。 优维…...

C# ReadOnlyRef Out

C# ReadOnly ReadOnly先看两种情况1.值类型2.引用类型 结论 Ref Out ReadOnly官方文档 ReadOnly 先看两种情况 1.值类型 当数据是值类型时&#xff0c;标记为Readonly时&#xff0c;如果再次设置值&#xff0c;会提示报错&#xff0c;无法分配到只读字段 public class A {pri…...

linux 服务 下 redis 安装和 启动

官网下载 https://redis.io/download/ 安装步骤&#xff1a; 1.安装redis 所需要的依赖 yum install -y gcc tcl2.上传安装包并解压&#xff0c;下载安装包&#xff0c;上传到/usr/local/src目录&#xff0c;解压 tar -zxvf redis-7.2.3.tat.gz进入安装目录&#xff0c;运行…...

ECharts与Excel的结合实战

引言&#xff1a;本文是一篇ECharts和Excel实战的记录。将Excel与ECharts产生火花&#xff0c;从Excel读取数据然后在ECharts上展示。 1.柱状图前端代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title…...

UDP的特点及应用场景

目录 UDP特点 应用场景 总结 User Datagram Protocol&#xff08;UDP&#xff0c;用户数据报协议&#xff09;是互联网协议套件中的一种传输层协议。与TCP不同&#xff0c;UDP是一种无连接的、不可靠的协议。 UDP特点 要知道UDP可以用来做什么&#xff0c;首先我们要知道它…...

Python开发——工具篇 Pycharm的相关配置,Python相关操作 持续更新

前言 本篇博客是python开发的工具篇相关&#xff0c;介绍pycharm的使用和相关配置&#xff0c;收录python的相关操作&#xff0c;比如如何启动jupyter。 目录 前言引出Pycharmpycharm如何不同等级日志显示不同颜色设置不同pycharm的python环境 Python操作如何启动Jupyter 总结…...

【深度学习】卷积神经网络结构组成与解释

卷积神经网络是以卷积层为主的深度网路结构&#xff0c;网络结构包括有卷积层、激活层、BN层、池化层、FC层、损失层等。卷积操作是对图像和滤波矩阵做内积&#xff08;元素相乘再求和&#xff09;的操作。 1. 卷积层 常见的卷积操作如下&#xff1a; 卷积操作解释图解标准卷…...

从源码解析Containerd容器启动流程

从源码解析Containerd容器启动流程 本文从源码的角度分析containerd容器启动流程以及相关功能的实现。 本篇containerd版本为v1.7.9。 更多文章访问 https://www.cyisme.top 本文从ctr run命令出发&#xff0c;分析containerd的容器启动流程。 ctr命令 查看文件cmd/ctr/comman…...

引迈-JNPF低代码项目技术栈介绍

从 2014 开始研发低代码前端渲染&#xff0c;到 2018 年开始研发后端低代码数据模型&#xff0c;发布了JNPF开发平台。 谨以此文针对 JNPF-JAVA-Cloud微服务 进行相关技术栈展示&#xff1a; 1. 项目前后端分离 前端采用Vue.js&#xff0c;这是一种流行的前端JavaScript框架&a…...

如何处理枚举类型(下)

作者简介&#xff1a;大家好&#xff0c;我是smart哥&#xff0c;前中兴通讯、美团架构师&#xff0c;现某互联网公司CTO 联系qq&#xff1a;184480602&#xff0c;加我进群&#xff0c;大家一起学习&#xff0c;一起进步&#xff0c;一起对抗互联网寒冬 上一篇我们通过编写MyB…...

wsj0数据集原始文件.wv1.wv2转换成wav文件

文章目录 准备一、获取WSJO数据集二、安装sph2pipe三、转换代码四、结果展示 ​ 最近做语音分离实验需要用到wsj0-2mix数据集&#xff0c;但是从李宏毅语音分离教程里面获取的wsj0-2mix只有一部分。从网上获取到了完整的WSJO数据集后&#xff0c;由于原始的语音文件后缀是wv1或…...

Flask Session 登录认证模块

Flask 框架提供了强大的 Session 模块组件&#xff0c;为 Web 应用实现用户注册与登录系统提供了方便的机制。结合 Flask-WTF 表单组件&#xff0c;我们能够轻松地设计出用户友好且具备美观界面的注册和登录页面&#xff0c;使这一功能能够直接应用到我们的项目中。本文将深入探…...

【运维】hive 高可用详解: Hive MetaStore HA、hive server HA原理详解;hive高可用实现

文章目录 一. hive高可用原理说明1. Hive MetaStore HA2. hive server HA 二. hive高可用实现1. 配置2. beeline链接测试3. zookeeper相关操作 一. hive高可用原理说明 1. Hive MetaStore HA Hive元数据存储在MetaStore中&#xff0c;包括表的定义、分区、表的属性等信息。 hi…...

C#开发的OpenRA游戏之属性SelectionDecorations(13)

C#开发的OpenRA游戏之属性SelectionDecorations(13) 在前面分析SelectionDecorations属性类时,会发现它有下面这个属性: public class SelectionDecorations : SelectionDecorationsBase, IRender { readonly Interactable interactable; 它是定义了一个Interactabl…...

接手了一个外包开发的项目,我感觉我的头快要裂开了~

嗨&#xff0c;大家好&#xff0c;我是飘渺。 最近&#xff0c;我和小伙伴一起接手了一个由外包团队开发的微服务项目&#xff0c;这个项目采用了当前流行的Spring Cloud Alibaba微服务架构&#xff0c;并且是基于一个“大名鼎鼎”的微服务开源脚手架&#xff08;附带着模块代…...

git常规使用方法,常规命令

Git是一种分布式版本控制系统&#xff0c;它可以记录软件的历史版本&#xff0c;并提供了多人协作开发、版本回退等功能。以下是Git的基本使用方法&#xff1a; 安装Git&#xff1a;下载安装包并进行安装&#xff0c;安装完成后在命令行中输入 git --version 进行验证。 初始化…...

【JavaScript】3.3 JavaScript工具和库

文章目录 1. 包管理器2. 构建工具3. 测试框架4. JavaScript 库总结 在你的 JavaScript 开发之旅中&#xff0c;会遇到许多工具和库。这些工具和库可以帮助你更有效地编写和管理代码&#xff0c;提高工作效率。在本章节中&#xff0c;我们将探讨一些常见的 JavaScript 工具和库&…...

开发基于 ChatGPT 分析热点事件并生成文章的网站应用【热点问天】把百度等热点用chatGPT来对热点事件分析海量发文章 开发步骤 多种方式获取利润

这样做的优点&#xff1a; 1.不用每个人都问chatGPT同样的问题。 2.已经生成的&#xff0c;反应快速。 3.内容分析的客观&#xff0c;真实&#xff0c;基于数据&#xff0c;无法造假。 4.无其它目的这种基于 ChatGPT 分析热点事件并生成文章的网站&#xff0c;可以通过多种方式…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

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

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

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...