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

数据结构排序算详解(动态图+代码描述)

目录

1、直接插入排序(升序)

2、希尔排序(升序) 

3、选择排序(升序)

方式一(一个指针)

方式二(两个指针)

4、堆排序(升序)

 5、冒泡排序(升序)

6、快速排序 (升序)

方式一(Hoare方法)

方式二(挖坑法) 

 快排改进算法(三数取中)

7、归并排序

8、总结


1、直接插入排序(升序)

描述对于一个数组i从第二个数据开始比较,j=i-1,j<0停止,每次i下标元素放到临时变量tmp中与j下标比较,如果大于j下标,tmp还放回原位置,i和j都加加,如果小于j下标,j--,直到找到大于j下标元素,tmp放到j+1下标

时间复杂度:最好情况下O(n),最坏情况O(n^2)

空间复杂度:O(1)

//直接插入排序
//时间复杂度:最好情况下O(n),最坏情况O(n^2)
public class Test1 {public static void sort(int []array){for (int i = 1; i <array.length ; i++) {int tmp=array[i];int j = i-1;for (; j >=0 ; j--) {if(tmp<array[j])array[j+1]=array[j];else break;}array[j+1]=tmp;}}
}

2、希尔排序(升序) 

描述:我们先对数组中数据分组,数组长度即位N,具体先分为gap组,gap=N/2,N/4,N/8.....1。然后对每一组直接插入排序。

时间复杂度:O(n*log2(N)),空间复杂度:O(1)

每种颜色一组例如:

例如:

public static void ShellSort(int [] array){int gap=array.length;//10while (gap>1){gap=gap/2;Sort(array,gap);//5,2,1}}private static void Sort(int [] array,int gap){for (int i = gap; i <array.length ; i++) {int tmp=array[i];int j = i-gap;//每组直接插入排序for (; j >=0 ; j=j-gap) {if (tmp<array[j])array[j+gap]=array[j];else break;}array[j+gap]=tmp;}

3、选择排序(升序)

方式一(一个指针)


描述: 每次找最小值下标,与i下标交换,i++

空间复杂度O(1),时间复杂度:O(N^2)

 public static void selcetSort(int [] array){for (int i = 0; i <array.length ; i++) {int min=i;//记录每次最小值下标for (int j = i+1; j <array.length ; j++)if (array[j]<array[min])min=j;swap(min,i,array);}}private static void swap(int i ,int j,int [] array){int tmp=array[i];array[i]=array[j];array[j]=tmp;}

方式二(两个指针)

思路left,right指向数组的两端,每次遍历找到最大值和最小值,分别赋值给lefgt和right

 public static void selectSort2(int[] array) {int left = 0;int right = array.length-1;int i;while (left < right) {//i  minIndex   maxIndexint minIndex=left,maxIndex=right;i=left+1;for(;i<right;i++){if (array[i]<=array[minIndex])minIndex=i;if (array[i]>array[maxIndex])maxIndex=i;}swap(left,minIndex,array);swap(right,maxIndex,array);left++;right--;}}private static void swap(int i ,int j,int [] array){int tmp=array[i];array[i]=array[j];array[j]=tmp;}

4、堆排序(升序)

思路:先创建成大根堆,每次排序把根节点与最后位置元素交换后向下调整,下一次根节点与end-1下标交换后向下调整,直到end<0;结束

 public static void HeapSort(int[]array){creatHeap(array.length,array);//创建大根堆int end=array.length-1;while (end>0){swap(end,0,array);signHeap(0,end,array);//向下调整不挑最后一个所以后减减end--;}}public static void creatHeap(int end,int [] array){int preheap;//每次的根节点for ( preheap=(end-1-1)/2;preheap>=0;preheap--){signHeap(preheap,end, array);}}//向下调整为大根堆为例private static void signHeap(int preheap,int end,int [] array){//向下调整int child=preheap*2+1;//preheap左子树下标while (child<end){if(child+1<end&&array[child]<array[child+1])child++;//现在child指向孩子节点的最大值if (array[preheap]<array[child]){swap(preheap,child,array);preheap=child;child=child*2+1;}else break;}}private static void swap(int i ,int j,int [] array){int tmp=array[i];array[i]=array[j];array[j]=tmp;}

 5、冒泡排序(升序)

 

时间复杂度:O(N^2),空间复杂度O(1)
 public static void bubbleSort(int [] array){for (int i = 0; i < array.length-1; i++) {boolean flag=false;for (int j = 0; j < array.length-1; j++) {if (array[j]>array[j+1]){swap(j,j+1,array);flag=true;}}if (flag==false)break;}}private static void swap(int i ,int j,int [] array){int tmp=array[i];array[i]=array[j];array[j]=tmp;}

6、快速排序 (升序)

方式一(Hoare方法

描述: 

每次都是最左边的元素是基点,从左边往右找到比基点大的跟从右往左找到比基点小的交换,最后left和right交点和基点交换,这样排完一次后交点左边比交点值小,后边大,分左右递归在排

时间复杂度:O(Nlog2(N)),空间复杂度O(log2(N))
    public static void quick(int [] array){int start=0,end=array.length-1;quickSort(array,start,end);}private static void quickSort(int [] array,int start,int end){if(start>=end)return;int mid=sort(array,start,end);quickSort(array,start,mid-1);quickSort(array,mid+1,end);}private static int sort(int [] array,int left,int right){int tmp=array[left];//基准int i=left;//先写右的right--,否则一遍走到left==right后与i下标交换的那一次且仅仅一次将会不有序while (left<right) {while (left < right && tmp <=array[right]) right--;//找到比tmp小的数while (left < right && tmp >= array[left]) left++;//找到比tmp大的数swap(right, left, array);}swap(left,i,array);return left;//left==right==mid}private static void swap(int i ,int j,int [] array){int tmp=array[i];array[i]=array[j];array[j]=tmp;}

方式二(挖坑法) 

 思想:每次都是最左边的元素是基点,保存基点下标,此处就是一个坑,从右往左找到比基点小的放到基点下标,放到坑处 ,刚从右边放过来的元素位置就有是一个新的坑,我们再从左往右找到比基点大的元素放到新坑,当然这里又是一个坑。。。

时间复杂度:O(Nlog2(N)),空间复杂度O(log2(N))

    public static void quick(int [] array){int start=0,end=array.length-1;quickSort(array,start,end);}private static void quickSort(int [] array,int start,int end){if(start>=end)return;int mid=sort(array,start,end);quickSort(array,start,mid-1);quickSort(array,mid+1,end);}private static int sort(int [] array,int left,int right){int tmp=array[left];//基准int i=left;//先写右的right--,否则一遍走到left==right后与i下标交换后的那一次将会不有序while (left<right) {while (left < right && tmp <=array[right]) right--;//找到比tmp小的数array[left]=array[right];while (left < right && tmp >= array[left]) left++;//找到比tmp大的数array[right]=array[left];}array[left]=tmp;//最后入坑return left;//left==right==mid}

 快排改进算法(三数取中)

思想:三数取中法,index是每次左右短点和中间点第二大的数字,防止分组不太对称,成为串,这样时间复杂度变高
public static void quick(int [] array){int start=0,end=array.length-1;quickSort(array,start,end);}private static void quickSort(int [] array,int start,int end){if(start>=end)return;//三数取中法,index是每次左右短点和中间点第二大的数字//防止分组不太对称,成为串,这样时间复杂度变高int index=indexleNum(array,start,end);//快排排序开始int mid=sort(array,start,end);quickSort(array,start,mid-1);quickSort(array,mid+1,end);}//挖坑法private static int sort(int [] array,int left,int right){int tmp=array[left];//基准int i=left;//先写右的right--,否则一遍走到left==right后与i下标交换的那一次且仅仅一次将会不有序while (left<right) {while (left < right && tmp <=array[right]) right--;//找到比tmp小的数array[left]=array[right];while (left < right && tmp >= array[left]) left++;//找到比tmp大的数array[right]=array[left];}array[left]=tmp;//最后入坑return left;//left==right==mid}private static int indexleNum(int [] array,int left,int right){int index=left+((left+right)/2);//也就三个数据,空间复杂度不高,所以可以建立一个新的数组,用冒泡int [] b=new int[3];for (int i = 0; i < b.length-1; i++) {boolean flag=false;for (int j = 0; j < array.length-1; j++) {if (array[j]>array[j+1]){swap(j,j+1,array);flag=true;}}if (flag==false)break;}return b[1];}private static void swap(int i ,int j,int [] array){int tmp=array[i];array[i]=array[j];array[j]=tmp;}

7、归并排序

时间复杂度:O(Nlog2(N)),空间复杂度O(N)

 

 public static void mergerSort(int [] array){mergeFunc(array,0,array.length-1);}private static void mergeFunc(int [] array,int left,int right){if(left>=right){return;}int mid=left+((right-left)>>1);mergeFunc(array,left,mid);mergeFunc(array,mid+1,right);//左右拆分完毕,开始合并merge(array,mid,left,right);}private static void merge(int []array,int mid,int left,int right){int start1=left;int end1=mid;int start2=mid+1;int end2=right;int [] tmp=new int[right-left+1];int k=0;//保证两个表都有数据while (start1<=end1&&start2<=end2){if (array[start1]<=array[start2])tmp[k++]=array[start1++];else {tmp[k++]=array[start2++];}}//如果s2没有数据了但是s1中还有数据while (start1<=end1)tmp[k++]=array[start1++];//如果s1没有数据了但是s2中还有数据while (start2<=end2)tmp[k++]=array[start2++];//放回到原来数组for (int i = 0; i < k; i++) {array[i+left]=tmp[i];//i+left防止覆盖数据}}

8、总结

相关文章:

数据结构排序算详解(动态图+代码描述)

目录 1、直接插入排序&#xff08;升序&#xff09; 2、希尔排序&#xff08;升序&#xff09; 3、选择排序&#xff08;升序&#xff09; 方式一&#xff08;一个指针&#xff09; 方式二&#xff08;两个指针&#xff09; 4、堆排序&#xff08;升序&#xff09; 5、冒…...

2024-01-25 力扣高频SQL50题目1174. 即时食物配送

题目如下&#xff1a; 配送表: Delivery -------------------------------------- | Column Name | Type | -------------------------------------- | delivery_id | int | | customer_id | int | | order_date…...

java web 校园健康管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 java Web校园健康管理系统是一套完善的java web信息管理系统 &#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为 TOMCAT7.0,Myeclipse8.5开发&#xff0c;数据库为Mysq…...

回归预测 | Matlab基于SSA-SVR麻雀算法优化支持向量机的数据多输入单输出回归预测

回归预测 | Matlab基于SSA-SVR麻雀算法优化支持向量机的数据多输入单输出回归预测 目录 回归预测 | Matlab基于SSA-SVR麻雀算法优化支持向量机的数据多输入单输出回归预测预测效果基本描述程序设计参考资料 预测效果 基本描述 1.Matlab基于SSA-SVR麻雀算法优化支持向量机的数据…...

Java转成m3u8,hls格式

Java转成m3u8,hls格式 需求分析 大致思路 循环文件夹下面所有文件判断当前文件是否是视频文件&#xff0c;如果是视频文件先转为ts文件 因为听别人说先转成ts之后再切片会快很多 转成ts文件&#xff0c;并为这些文件单独生成一个目录&#xff0c;如果目录不存在则新建一个目…...

jmeter之接口测试实现参数化(利用函数助手),参数值为1-9(自增的数字)

1.前言 思考&#xff1a;为什么不用postman&#xff0c;用postman的话就得导入csv文件/json文件 如果不想导入文件&#xff0c;postman是实现不了&#xff0c;因为postman每次只会运行一次 2.jmeter函数助手实现参数化 &#xff08;1&#xff09;新建“线程组”--新建“http…...

如何在 Ubuntu 22.04 上安装 Apache Web 服务器

前些天发现了一个人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;最重要的屌图甚多&#xff0c;忍不住分享一下给大家。点击跳转到网站。 如何在 Ubuntu 22.04 上安装 Apache Web 服务器 介绍 Apache HTTP 服务器是世界上使用最广泛的 Web 服务器。它…...

【python爬虫】爬虫编程技术的解密与实战

​&#x1f308;个人主页&#xff1a;Sarapines Programmer&#x1f525; 系列专栏&#xff1a; 爬虫】网络爬虫探秘⏰诗赋清音&#xff1a;云生高巅梦远游&#xff0c; 星光点缀碧海愁。 山川深邃情难晤&#xff0c; 剑气凌云志自修。 目录 &#x1f33c;实验目的 &#x1f…...

VisualSVN Server下载安装和使用方法、服务器搭建、使用TortoiseSvn将项目上传到云端服务器、各种错误解决方法

VisualSVN Server下载安装和使用方法、服务器搭建、使用TortoiseSvn将项目上传到云端服务器、各种错误解决方法 0.写在前面00.电脑配置01.思路 1.VisualSVN Server下载安装01.下载02.安装03.电脑命名不能有中文04.制作VisualSVN Server快捷方式05.License limits exceeded, Som…...

Python模块与包:扩展功能、提高效率的利器

文章目录 一、引言1.1 模块与包对于Python开发的重要性1.2 Python作为拥有丰富生态系统的编程语言 二、为什么学习模块与包2.1 复用代码&#xff1a;利用现有模块与包加速开发过程2.2 扩展功能&#xff1a;通过模块与包提供的功能增强应用的能力 三、模块的使用3.1 导入模块&am…...

【每日一题】4.LeetCode——杨辉三角

&#x1f4da;博客主页&#xff1a;爱敲代码的小杨. ✨专栏&#xff1a;《Java SE语法》 ❤️感谢大家点赞&#x1f44d;&#x1f3fb;收藏⭐评论✍&#x1f3fb;&#xff0c;您的三连就是我持续更新的动力❤️ &#x1f64f;小杨水平有限&#xff0c;欢迎各位大佬指点&…...

蓝桥杯(Python)每日练Day5

题目 OJ1229 题目分析 题目完全符合栈的特征&#xff0c;后进先出。如果能够熟练使用列表的9种方法那么这道题很容易解出。 题解 a[]#存衣服 nint(input()) for i in range(n):llist(input().split())#判断每一步的操作if len(l[0])2:a.append(l[1])else:while a.pop()!l…...

SpringCloud(二)

Spring Cloud 文章目录 Spring Cloud任务三&#xff1a;Spring Cloud与微服务架构1.Spring Cloud课程内容介绍2.单体应用架构2.1 互联网应用架构演进2.2 单体应用架构 3.垂直应用架构4.SOA应用架构5.微服务应用架构介绍6.微服务架构核心思想及优缺点7.微服务架构的核心概念8.Sp…...

【java】常见的面试问题

目录 一、异常 1、 throw 和 throws 的区别&#xff1f; 2、 final、finally、finalize 有什么区别&#xff1f; 3、try-catch-finally 中哪个部分可以省略&#xff1f; 4、try-catch-finally 中&#xff0c;如果 catch 中 return 了&#xff0c;finally 还会执行吗&#…...

虚幻UE 插件-像素流送实现和优化

本笔记记录了像素流送插件的实现和优化过程。 UE version&#xff1a;5.3 文章目录 一、像素流送二、实现步骤1、开启像素流送插件2、设置参数3、打包程序4、打包后的程序进行像素流参数设置5、下载NodeJS6、下载信令服务器7、对信令服务器进行设置8、启动像素流送 三、优化1、…...

Vue2 props组件通信

一、父组件向子组件传值 1、流程图 2、父组件代码 <template><div class"app"><UserInfo:usernameusername:ageage:isSingleisSingle:carcar:hobbyhobby></UserInfo></div> </template><script> import UserInfo from .…...

重构改善既有代码的设计-学习(三):重新组织数据

1、拆分变量&#xff08;Split Variable&#xff09; 有些变量用于保存一段冗长代码的运算结果&#xff0c;以便稍后使用。这种变量应该只被赋值一次。 如果它们被赋值超过一次&#xff0c;就意味它们在函数中承担了一个以上的责任。如果变量承担多个责任&#xff0c;它就应该被…...

群狼调研(长沙品牌忠诚度测试)|广告效果测评方法

广告效果测评方法可以根据具体的目标和需求而有所差异&#xff0c;以下是一些常见的广告效果测评方法&#xff1a; 1.品牌调研和调查&#xff1a;通过定量或定性的调研和调查方法&#xff0c;评估广告对品牌认知、品牌形象和品牌偏好的影响&#xff0c;包括品牌知名度、品牌关联…...

Gradle学习笔记:Gradle的使用方法

文章目录 1.初始化项目2.构建脚本语言选择3.项目命名4.项目构建过程 1.初始化项目 创建一个test空文件夹&#xff0c;在该文件夹下打开终端&#xff0c;并执行命令&#xff1a;gradle init. 会有一个选项让你选择项目的类型。下面是每个选项的含义和用途&#xff1a; basic&am…...

少儿编程 2023年12月电子学会图形化编程等级考试Scratch二级真题解析(选择题)

2023年12月scratch编程等级考试二级真题 选择题(共25题,每题2分,共50分) 1、在制作推箱子游戏时,地图是用数字形式储存在电脑里的,下图是一个推箱子地图,地图表示如下:第一行( 111111)第二行( 132231) 第三行( 126621) 第四行( ) 第五行( 152321) 第六行( 111111 ) 根…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...

DL00871-基于深度学习YOLOv11的盲人障碍物目标检测含完整数据集

基于深度学习YOLOv11的盲人障碍物目标检测&#xff1a;开启盲人出行新纪元 在全球范围内&#xff0c;盲人及视觉障碍者的出行问题一直是社会关注的重点。尽管技术不断进步&#xff0c;许多城市的无障碍设施依然未能满足盲人出行的实际需求。尤其是在复杂的城市环境中&#xff…...

Java高级 |【实验八】springboot 使用Websocket

隶属文章&#xff1a;Java高级 | &#xff08;二十二&#xff09;Java常用类库-CSDN博客 系列文章&#xff1a;Java高级 | 【实验一】Springboot安装及测试 |最新-CSDN博客 Java高级 | 【实验二】Springboot 控制器类相关注解知识-CSDN博客 Java高级 | 【实验三】Springboot 静…...

创客匠人:如何通过创始人IP打造实现知识变现与IP变现的长效增长?

在流量红利逐渐消退的当下&#xff0c;创始人IP的价值愈发凸显。它不仅能够帮助中小企业及个人创业者突破竞争壁垒&#xff0c;还能成为企业品牌影响力的核心资产。然而&#xff0c;市场上IP孵化机构鱼龙混杂&#xff0c;如何选择一家真正具备长期价值的合作伙伴&#xff1f;创…...