【java数据结构之八大排序(上)-直接插入排序,希尔排序,选择排序,堆排序,向下调整(大根堆,小根堆)等知识详解】

本文主要是介绍【java数据结构之八大排序(上)-直接插入排序,希尔排序,选择排序,堆排序,向下调整(大根堆,小根堆)等知识详解】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述

🌈个人主页:努力学编程’
个人推荐:基于java提供的ArrayList实现的扑克牌游戏 |C贪吃蛇详解
学好数据结构,刷题刻不容缓:点击一起刷题
🌙心灵鸡汤总有人要赢,为什么不能是我呢
在这里插入图片描述

hello,今天带大家学数据结构的一个非常重要的部分,排序!!!,回想博主的学习路程 ,好像真正学过的排序就是冒泡排序,其实数据结构里面有很多的排序的算法,针对不同的数据,我们往往采用不同的排序算法,合适的排序算法处理数据时可能会大大减少内存的消耗,和较短的运行时间。下面就带大家学习几种常见的排序算法。
在这里插入图片描述

🍪插入排序:

🍰直接插入排序:

在这里插入图片描述

直接插入排序是一种简单直观的排序算法,将待排序的元素逐个插入到已经排序好的序列中的适当位置,从而得到一个新的、更长的有序序列。具体的实现呢,给大家列出来了:

1.初始状态:假设第一个元素已经是有序的序列。
遍历未排序部分:从第二个元素开始,逐个遍历未排序的元素。
插入操作:对于当前遍历到的元素,将其与已经排序好的序列中的元素依次比较,找到合适的位置插入。

2.移动元素:如果发现当前元素比已排序序列中的某个元素小(或大,取决于排序顺序),则将该元素后移一位,为当前元素腾出插入位置。
插入元素:找到合适的位置后,将当前元素插入到该位置。
重复:重复上述步骤,直到所有元素都被插入到有序序列中。

public static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int tmp = array[i];int j = i-1;for (; j >= 0 ; j--) {if(array[j] > tmp) {array[j+1] = array[j];}else {array[j+1] = tmp;break;}}array[j+1] = tmp;}}

在这里插入图片描述
直接插入排序的特性总结:

  1. 元素集合越接近有序,直接插入排序算法的时间效率越高
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1),它是一种稳定的排序算法
  4. 稳定性:稳定

🍰希尔排序

希尔排序又称为缩小增量排序,其本质是将所有的数据分成N组,每一组的元素对应的是从第一个开始,每N个的元素后的那个元素进行比较排序,依次对N组元素做同样的处理。

然后对数据重新分组,分为K组(K<N),然后重复上述操作对每组元素比较大小,直到分组为1,完成比较。
在这里插入图片描述
那么你可能会问,每次分组的时候,有什么依据吗,总不能想怎么分就怎么分吧,
在这里插入图片描述在这里插入图片描述
我们这里为了方便期间,采用gap=[N/2]的处理方法,向下取整,将数据划分直到化为1为止。完成排序。由于不同的人可能采用不同的gap去划分数据,时间复杂度也就相应的可能会不同,所以希尔排序的时间复杂度不太好计算。

稳定性:不稳定

 public static void shellSort(int[] array) {int gap = array.length;//nwhile (gap > 1) {gap = gap/3 + 1;shell(array,gap);}}/*** 每组进行插入排序* @param array* @param gap*/private static void shell(int[] array,int gap) {//i++ 交替进行插入排序for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i-gap;for (; j >= 0 ; j -= gap) {if(array[j] > tmp) {array[j+gap] = array[j];}else {break;}}array[j+gap] = tmp;}}private static void swap(int[] array,int i,int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}

这里还是给大家具体演示一下,帮助大家理解。
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

🍰选择排序

定义:每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。

在这里插入图片描述
这里先给大家这个简单比较容易理解的版本:

public void selectSort(int[] array){for(int i=0;i<array.length;i++){int minindex=i;for(int j=i+1;j<array.length;j++){if(array[minindex]>array[j]){minindex=j;}}swap(array,minindex,i);}}public void swap(int[]array,int i,int j){int tmp=array[i];array[i]=array[j];array[j]=tmp;}

进行测试:
完成测试
测试成功!!!

👋当然我们还有一种选择排序的另一种实现方法,我们每次遍历的时候,都选择两个元素,一个是这次遍历的最小元素,一个是最大的元素,分别放到数组的最左和最有端,然后就和上面的逻辑一样,继续遍历,更新最大值和最小值,遍历结束。

这里也把代码给大家,这端代码说起来简单,但是还是有很多的小细节的,大家细细品味一下。

public void selectSort2(int[] array) {int left=0;int right=array.length-1;while(left<right){int minIndex=left;int maxIndex=left;for(int i=left;i<right;i++){if(array[i]>array[maxIndex])  maxIndex=i;if(array[i]<array[minIndex])  minIndex=i;}swap(array,minIndex,left);//[10,6,4,8,7]这个例子大家按照代码的逻辑画个图//就会发现,排序失败原因是maxIndex==left我们在//第一次交换之后就会把maxIndex对应的值交换到minIndex中了//所以必须加一个判断if(left==maxIndex)  maxIndex=minIndex;swap(array,maxIndex,right);left++;right--;}}

我把需要注意的地方注释出来了,希望大家还是可以自己在纸上画一下,这样会对整个过程有一个更加全面的认识。

1.直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
2. 时间复杂度:O(N^2)
3. 空间复杂度:O(1)
4. 稳定性:不稳定

🍰堆排序

堆排序是我们所学的排序当中非常重要的一种排序,它实际上是建立在我们上一篇发布的文章优先级队列的基础上创建的一种排序方式,如果你对堆的概念还没有印象的话我建议你先去看看我的上一篇文章。

堆排序是建立在堆上的一种选择排序的算法,需要大家特别注意的是如果你要建立的是升序的序列的话。那么必须建立大根堆,降序的话,建立的是小根堆。

其实他的本事就是堆 里面的向下调整,我们上一篇文章也已经讲过了,那么他的过程到底是怎么样的,这里给大家演示一下。
在这里插入图片描述
那我们第一步其实是创建一个大根堆,相信这个应该对大家来说不太难,我把代码给大家,里面有详细的注释,大家可以对照看看:

private void createBigHeap(int[] array){for(int parent=(array.length-1-1)/2;parent>0;parent--){//从最后一个叶子节点的父节点开始遍历,向下调整siftDown(parent,array,array.length);}}public void siftDown(int parent,int[] array,int end){int child=parent*2+1;while(child<end){if(child+1<end&&array[child]<array[child+1]){child++;}if(array[child]>array[parent]){swap(array,child,parent);//这里是因为把孩子节点与父节点交换之后可能有问题//所以对树的底层都要检查一下parent=child;child=parent*2+1;}else{break;}}}

接下来按照堆排序的定义,我们以此交换根节点和最后一个叶子节点,然后向下调整,直到结束,下面是完整的代码:

 private void createBigHeap(int[] array){for(int parent=(array.length-1-1)/2;parent>0;parent--){//从最后一个叶子节点的父节点开始遍历,向下调整siftDown(parent,array,array.length);}}public void siftDown(int parent,int[] array,int end){int child=parent*2+1;while(child<end){if(child+1<end&&array[child]<array[child+1]){child++;}if(array[child]>array[parent]){swap(array,child,parent);//这里是因为把孩子节点与父节点交换之后可能有问题//所以对树的底层都要检查一下parent=child;child=parent*2+1;}else{break;}}}public void HeapSort(int[] array){createBigHeap(array);int end=array.length-1;while(end>=0){swap(array,end,0);siftDown(0,array,end);end--;}}

简单测试一下:
在这里插入图片描述
测试成功!!!

1.堆排序使用堆来选数,效率就高了很多。
2. 时间复杂度:O(N*logN)
3. 空间复杂度:O(1)
4. 稳定性:不稳定
好了今天就带大家学习这么多了,下次带大家学习剩下的几种排序,觉得文章对你有帮助的话,一键三连,支持一下,同时欢迎评论区留下你宝贵的建议~~~

这篇关于【java数据结构之八大排序(上)-直接插入排序,希尔排序,选择排序,堆排序,向下调整(大根堆,小根堆)等知识详解】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/941726

相关文章

MySQL中COALESCE函数示例详解

《MySQL中COALESCE函数示例详解》COALESCE是一个功能强大且常用的SQL函数,主要用来处理NULL值和实现灵活的值选择策略,能够使查询逻辑更清晰、简洁,:本文主要介绍MySQL中C... 目录语法示例1. 替换 NULL 值2. 用于字段默认值3. 多列优先级4. 结合聚合函数注意事项总结C

什么是 Java 的 CyclicBarrier(代码示例)

《什么是Java的CyclicBarrier(代码示例)》CyclicBarrier是多线程协同的利器,适合需要多次同步的场景,本文通过代码示例讲解什么是Java的CyclicBarrier,感... 你的回答(口语化,面试场景)面试官:什么是 Java 的 CyclicBarrier?你:好的,我来举个例

Java使用Mail构建邮件功能的完整指南

《Java使用Mail构建邮件功能的完整指南》JavaMailAPI是一个功能强大的工具,它可以帮助开发者轻松实现邮件的发送与接收功能,本文将介绍如何使用JavaMail发送和接收邮件,希望对大家有所... 目录1、简述2、主要特点3、发送样例3.1 发送纯文本邮件3.2 发送 html 邮件3.3 发送带

Java实现数据库图片上传功能详解

《Java实现数据库图片上传功能详解》这篇文章主要为大家详细介绍了如何使用Java实现数据库图片上传功能,包含从数据库拿图片传递前端渲染,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、前言2、数据库搭建&nbsChina编程p; 3、后端实现将图片存储进数据库4、后端实现从数据库取出图片给前端5、前端拿到

Java实现将byte[]转换为File对象

《Java实现将byte[]转换为File对象》这篇文章将通过一个简单的例子为大家演示Java如何实现byte[]转换为File对象,并将其上传到外部服务器,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言1. 问题背景2. 环境准备3. 实现步骤3.1 从 URL 获取图片字节数据3.2 将字节数组

Windows命令之tasklist命令用法详解(Windows查看进程)

《Windows命令之tasklist命令用法详解(Windows查看进程)》tasklist命令显示本地计算机或远程计算机上当前正在运行的进程列表,命令结合筛选器一起使用,可以按照我们的需求进行过滤... 目录命令帮助1、基本使用2、执行原理2.1、tasklist命令无法使用3、筛选器3.1、根据PID

Java捕获ThreadPoolExecutor内部线程异常的四种方法

《Java捕获ThreadPoolExecutor内部线程异常的四种方法》这篇文章主要为大家详细介绍了Java捕获ThreadPoolExecutor内部线程异常的四种方法,文中的示例代码讲解详细,感... 目录方案 1方案 2方案 3方案 4结论方案 1使用 execute + try-catch 记录

国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

《国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)》本文给大家利用deepseek模型搭建私有知识问答库的详细步骤和遇到的问题及解决办法,感兴趣的朋友一起看看吧... 目录1. 第1步大家在安装完ollama后,需要到系统环境变量中添加两个变量2. 第3步 “在cmd中

SpringBoot接收JSON类型的参数方式

《SpringBoot接收JSON类型的参数方式》:本文主要介绍SpringBoot接收JSON类型的参数方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、jsON二、代码准备三、Apifox操作总结一、JSON在学习前端技术时,我们有讲到过JSON,而在

MySql中的数据库连接池详解

《MySql中的数据库连接池详解》:本文主要介绍MySql中的数据库连接池方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql数据库连接池1、概念2、为什么会出现数据库连接池3、原理4、数据库连接池的提供商5、DataSource数据源6、DBCP7、C