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

数据结构——八大排序(下)

        数据结构中的八大排序算法是计算机科学领域经典的排序方法,它们各自具有不同的特点和适用场景。以下是这八大排序算法的详细介绍:

五、选择排序(Selection Sort)

  • 核心思想:每一轮从未排序的元素中选择最小(或最大)的元素,放到已排序的序列末尾。
  • 时间复杂度:O(n^2),因为每一轮都需要遍历整个未排序的数组。
  • 空间复杂度:O(1)。
  • 稳定性:不稳定,因为选择最小(或最大)元素时可能会破坏相同元素的相对位置。

package 排序;import java.util.Arrays;public class Selection{//选择排序public  static void main(String[] args) {int[] arr= {15,27,34,62,30,16};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int j=0;j<arr.length;j++) {int min=arr[j];int minIndex=j;for(int i=j;i<arr.length;i++) {if(arr[i]<min) {min=arr[i];minIndex=i;}}arr[minIndex]=arr[j];arr[j]=min;}	}
}

六、堆排序(Heap Sort)

  • 核心思想:利用堆这种数据结构进行排序。首先构建一个大顶堆(或小顶堆),然后依次将堆顶元素(最大或最小)与堆底元素交换,并减少堆的大小。最后,对剩余的元素重新调整成堆,直到整个数组有序。
  • 时间复杂度:O(nlogn),因为构建堆和调整堆的时间复杂度都是O(logn),而需要构建和调整n次。
  • 空间复杂度:O(1),因为排序过程中只需要常量的额外空间(用于交换元素)。
  • 稳定性:不稳定,因为堆的调整过程中可能会破坏相同元素的相对位置。
package 排序;import java.util.Arrays;public class Heap{
//堆排序public static void main(String[] args) {int[] arr= {5,7,4,2,0,1,6};//一、构建大顶堆for (int p=arr.length-1;p>=0;p--) {sort(arr, p, arr.length);}//二、堆底堆顶元素进行交换for(int i=arr.length-1;i>0;i--) {int temp=arr[i];arr[i]=arr[0];arr[0]=temp;sort(arr, 0, i);}//打印System.out.println("堆排序的结果为:");System.out.println(Arrays.toString(arr));}//堆的维护public static void sort(int[] arr,int parent,int length) {//定义左孩子int child=2*parent+1;while(child<length) {//定义右孩子int rchild=child+1;if(rchild<length && arr[rchild]>arr[child]) {child++;}//child指向左右孩子中的最大值//父子节点进行比较if(arr[parent]<arr[child]) {//父子节点进行交换int temp=arr[parent];arr[parent]=arr[child];arr[child]=temp;//parent指向child,child继续指向左右孩子中的最大值parent=child;child=2*child+1;}else {break;}}}
}

七、归并排序(Merge Sort)

  • 核心思想:将数组分成两部分,分别进行排序,然后将两部分合并成一个有序数组。这个过程可以递归地进行。
  • 时间复杂度:O(nlogn),因为每次合并都需要遍历两个有序数组。
  • 空间复杂度:O(n),因为需要额外的空间来存储合并后的有序数组(虽然可以使用原地归并算法来减少空间复杂度,但实现起来较为复杂)。
  • 稳定性:稳定,因为合并过程中相同元素会保持相对位置不变。
package 排序;import java.util.Arrays;public class Merge{public static void main(String[] args) {int[] arr= {11,22,33,55,2,11,24,63};mergeSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}//拆分public static void mergeSort(int[] arr, int left, int right) {//递归出口if(left==right) {return;}int mid=(left+right)/2;//向左拆分mergeSort(arr,left,mid);//向右拆分mergeSort(arr,mid+1,right);//合并merge(arr,left,right,mid);}public static void merge(int[] arr,int left,int right,int mid) {//定义第一段和第二段的开始int s1=left;int s2=mid+1;//定义临时空间int[] temp =new int[right-left+1];int index=0;//定义游标遍历临时空间//判断s1和s2指向的数据大小,将其存入临时数组while(s1<=mid&&s2<=right) {if(arr[s1]<arr[s2]) {temp[index]=arr[s1];s1++;index++;}else {temp[index]=arr[s2];s2++;index++;}}//判断s1中是否有数据,如果有将其放入临时数组当中while(s1<=mid) {temp[index]=arr[s1];s1++;index++;}//判断s2中是否有数据,如果有将其放入临时数组当中while(s2<=right) {temp[index]=arr[s2];s2++;index++;}//将临时数组中的数据写回原数组for(int i=0;i<temp.length;i++) {arr[left+i] = temp[i];}}
}

八、基数排序(Radix Sort)

  • 核心思想:基数排序是一种非比较型排序算法,它根据元素的位数(或字符)进行排序。通常从最低有效位(或字符)开始,依次对每一位(或字符)进行计数排序或桶排序,直到最高有效位(或字符)为止。
  • 时间复杂度:O(d(n+r)),其中d是位数(或字符数),n是待排序元素的个数,r是基数(如对于十进制数,r=10)。
  • 空间复杂度:O(n+r),因为需要额外的空间来存储桶或计数数组。
  • 稳定性:稳定,因为每一位(或字符)的排序过程中都保持相同元素的相对位置不变。
package 排序;import java.util.Arrays;public class Radix{//基数排序,注意,基数排序只能排整数。适用于数据位数不多,但数据量大的数据集public static void main(String[] args) {int[] arr= {50,17,41,20,101,11,26,35,47,63,214,63,88};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {//取最大值,计算最大值的位数int max=arr[0];for(int j=0;j<arr.length;j++) {if(arr[j]>max) {max=arr[j];}}int maxLen=(max+"").length();//返回最大值的位数System.out.println("最大值的位数为"+maxLen);//定义桶(本质上定义二维数组)int[][] bucket=new int[10][arr.length];//定义桶记录工具(一维数组,长度为10)int[] elementCounts=new int[10];int n=1;//放入取出来来回回执行maxLen遍for(int m=0;m<maxLen;m++) {//遍历数组,将数组中的数据放入桶中for(int i=0;i<arr.length;i++) {//个位开始排序int element =arr[i]/n%10;  //element代表个位数值,也代表要被放在哪个桶//读取桶记录工具中的数值int count=elementCounts[element];//数据放入bucket[element][count]=arr[i];elementCounts[element]++;}//将桶中的数据取出int index=0;//定义index游标,遍历数组,将桶中数据存入数组里for(int k=0;k<elementCounts.length;k++) {if(elementCounts[k]!=0) {//不为0桶中有数据,将数据取出for(int l=0;l<elementCounts[k];l++) {arr[index]=bucket[k][l];index++;}}//清理桶记录elementCounts[k]=0;}n=n*10;}}	}

综上所述,这八大排序算法各有优缺点和适用场景。在实际应用中,需要根据待排序数据的特点和具体需求来选择合适的排序算法。

相关文章:

数据结构——八大排序(下)

数据结构中的八大排序算法是计算机科学领域经典的排序方法&#xff0c;它们各自具有不同的特点和适用场景。以下是这八大排序算法的详细介绍&#xff1a; 五、选择排序&#xff08;Selection Sort&#xff09; 核心思想&#xff1a;每一轮从未排序的元素中选择最小&#xff0…...

Linux系统:Ubuntu上安装Chrome浏览器

Ubuntu系统版本&#xff1a;23.04 在Ubuntu系统上安装Google Chrome浏览器&#xff0c;可以通过以下步骤进行&#xff1a; 终端输入以下命令&#xff0c;先更新软件源&#xff1a; sudo apt update 或 sudo apt upgrade终端输入以下命令&#xff0c;下载最新的Google Chrome .…...

Redis位图BitMap

一、为什么使用位图&#xff1f; 使用位图能有效实现 用户签到 等行为&#xff0c;用数据库表记录签到&#xff0c;将占用很多存储&#xff1b;但使用 位图BitMap&#xff0c;就能 大大减少存储占用 二、关于位图 本质上是String类型&#xff0c;最小长度8位&#xff08;一个字…...

YOLOv11改进策略【卷积层】| ParNet 即插即用模块 二次创新C3k2

一、本文介绍 本文记录的是利用ParNet中的基础模块优化YOLOv11的目标检测网络模型。 ParNet block是一个即插即用模块,能够在不增加深度的情况下增加感受野,更好地处理图像中的不同尺度特征,有助于网络对输入数据更全面地理解和学习,从而提升网络的特征提取能力和分类性能…...

学习threejs,网格深度材质MeshDepthMaterial

&#x1f468;‍⚕️ 主页&#xff1a; gis分享者 &#x1f468;‍⚕️ 感谢各位大佬 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍⚕️ 收录于专栏&#xff1a;threejs gis工程师 文章目录 一、&#x1f340;前言1.1 ☘️网格深度材质MeshDepthMate…...

算法时间、空间复杂度(二)

目录 大O渐进表示法 一、时间复杂度量级的判断 定义&#xff1a; 例一&#xff1a;执行2*N&#xff0b;1次 例二&#xff1a;执行MN次 例三&#xff1a;执行已知次数 例四:存在最好情况和最坏情况 顺序查找 冒泡排序 二分查找 例五&#xff1a;阶乘递归 ​编辑 例…...

高级java每日一道面试题-2024年10月11日-数据库篇[Redis篇]-Redis都有哪些使用场景?

如果有遗漏,评论区告诉我进行补充 面试官: Redis都有哪些使用场景? 我回答: Redis 是一个开源的、基于键值对的数据结构存储系统&#xff0c;&#xff0c;它支持多种数据类型&#xff0c;包括字符串、散列、列表、集合和有序集合。它可以用作数据库、缓存和消息中间件。由于…...

0047__【python打包分发工具】setuptools详解

【python打包分发工具】setuptools详解-CSDN博客...

自定义拦截器处理token

目录 1、WebConfig 配置类 2、TSUserContext 把用户信息放到context中 3、自定义拦截器 4、在controller中可以使用 5、参考链接 1、WebConfig 配置类 @Configuration public class WebConfig implements WebMvcConfigurer {@Autowiredprivate AccessControlInterceptor …...

Scrapy | 使用Scrapy进行数据建模和请求

scrapy数据建模与请求 数据建模1.1 为什么建模1.2 如何建模1.3如何使用模板类1.4 开发流程总结 目标&#xff1a; 1.应用在scrapy项目中进行建模 2.应用构造Request对象&#xff0c;并发送请求 3.应用利用meta参数在不同的解析函数中传递数据 数据建模 | 通常在做项目的过程中…...

学习笔记——交换——STP(生成树)基本概念

三、基本概念 1、桥ID/网桥ID (Bridege ID&#xff0c;BID) 每一台运行STP的交换机都拥有一个唯一的桥ID(BID)&#xff0c;BID(Bridge ID/桥ID)。在STP里我们使用不同的桥ID标识不同的交换机。 (2)BID(桥ID)组成 BID(桥ID)组成(8个字节)&#xff1a;由16位(2字节)的桥优先级…...

机器学习笔记-2

文章目录 一、Linear model二、How to represent this function三、Function with unknown parameter四、ReLU总结、A fancy name 一、Linear model 线性模型过于简单&#xff0c;有很大限制&#xff0c;我们需要更多复杂模式 蓝色是线性模型&#xff0c;线性模型无法去表示…...

SpringSecurity(一)——认证实现

一、初步理解 SpringSecurity的原理其实就是一个过滤器链&#xff0c;内部包含了提供各种功能的过滤器。 当前系统中SpringSecurity过滤器链中有哪些过滤器及它们的顺序。 核心过滤器&#xff1a; &#xff08;认证&#xff09;UsernamePasswordAuthenticationFilter:负责处理…...

VMWare NAT 模式下 虚拟机上不了网原因排查

vmware 按照了Linux之后 无法上网&#xff0c;搞定后&#xff0c;记录一些信息。 window有两个虚拟网卡 VMnet1 对应的是 Host-Only&#xff08;仅主机模式&#xff09; VMnet8 对应的是 NAT&#xff08;网络地址转换模式&#xff09; 在NAT模式中&#xff0c;需要设置NAT和D…...

R语言手工实现主成分分析 PCA | 奇异值分解(svd) 与PCA | PCA的疑问和解答

几个问题: pca可以用相关系数矩阵做吗?效果比协方差矩阵比怎么样?pca做完后变量和样本的新坐标怎么旋转获得?pca做不做scale和center对结果有影响吗?pca用因子分解和奇异值分解有啥区别?后者怎么获得变量和样本的新坐标?1. 用R全手工实现 PCA(对比 prcomp() ) 不借助包…...

第三届OpenHarmony技术大会在上海成功举办

10月12日&#xff0c;以“技术引领筑生态&#xff0c;万物智联创未来”为主题的第三届OpenHarmony技术大会&#xff08;以下简称“大会”&#xff09;在上海成功举办。本次大会由OpenAtom OpenHarmony&#xff08;以下简称“OpenHarmony”&#xff09;项目群技术指导委员会&…...

数字化:IT部门主导还是业务部门主导?

在这个瞬息万变的数字化时代&#xff0c;企业如同在大海中航行的小船&#xff0c;面对波涛汹涌的市场竞争&#xff0c;数字化转型已成为生存的必经之路。然而&#xff0c;在这条充满挑战的航线上&#xff0c;常常会出现一个让人纠结的问题&#xff1a;数字化转型究竟应该由IT部…...

MySQL表的基本查询下/分组聚合统计

1&#xff0c;update 对查询到的结果进行列值更新&#xff0c;可以和older by&#xff0c;where&#xff0c;limit合并使用&#xff0c;为了方便讲解&#xff0c;将会以题目练习的方式进行说明&#xff1a; 1&#xff0c;将孙悟空同学的数学成绩变更为 80 分 本道题和where联…...

条款3: 理解decltype

目录 一、decltype + 变量 二、decltype + 表达式 三、decltype 使用场景 一、decltype + 变量 🥭 所有的信息都会保留,数组和函数也不会退化 const int &&carref = std::move(ca); decltype(carref) bb; // bb推导为const int &&,不会被忽略掉co…...

TCP:过多的TIME_WAIT

过多的TIME_WAIT 线上问题紧急处理方式tcp_tw_reuse启用主要特点&#xff1a;源码 线上问题 线上机器出现了几万个TIME_WAIT&#xff0c;怎么办&#xff1f; 紧急处理方式 tcp_tw_reuse 启用 默认情况下tcp_tw_reuse是关闭状态&#xff0c;使用sysctl -w net.ipv4.tcp_tw_…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...