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

news/2024/11/16 16:45:07/

在这里插入图片描述

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

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

🍪插入排序:

🍰直接插入排序:

在这里插入图片描述

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

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

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

java">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去划分数据,时间复杂度也就相应的可能会不同,所以希尔排序的时间复杂度不太好计算。

稳定性:不稳定

java"> 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;}

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

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

🍰选择排序

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

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

java">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;}

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

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

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

java">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. 稳定性:不稳定

🍰堆排序

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

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

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

java">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;}}}

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

java"> 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. 稳定性:不稳定
好了今天就带大家学习这么多了,下次带大家学习剩下的几种排序,觉得文章对你有帮助的话,一键三连,支持一下,同时欢迎评论区留下你宝贵的建议~~~


http://www.ppmy.cn/news/1446731.html

相关文章

Java自定义工具类中使用RedisTemplate的遇到空指针问题

话不多说&#xff0c;上错误代码&#xff0c;以下是我在静态方法里使用RedisTemplate类&#xff0c;这里加了Autowired ****省略import包**** Component public class CommonUtils {Autowiredprivate static RedisTemplate redisTemplate;public static String test() {String…

【图论】图论基础

图论不同地方讲的不太一样&#xff0c;本文仅限作者的理解 定义 图一般由点集 V V V 和边集 E E E 组成。 对于 v ∈ V v\in V v∈V&#xff0c;称 v v v 为该图的一个节点。 对于 e ∈ E e\in E e∈E&#xff0c;一般用二元组 ( u , v ) (u,v) (u,v) 表示 e e e&…

Visual Studio中怎样更改Nuget程序包源

场景 Visual Studio 2019 在使用NuGet添加依赖包时&#xff0c;在预览中搜索不到程序包。 排查下NuGet的程序包源为本地。 将程序包源修改下。 实现 在解决方案上右击选择管理解决方案中的NuGet程序包(在 Visual Studio 中打开“工具”>“选项”>“NuGet 包管理器”…

设备能源数据采集新篇章

在当今这个信息化、智能化的时代&#xff0c;设备能源数据的采集已经成为企业高效运营、绿色发展的重要基石。而今天&#xff0c;我们要向大家介绍的就是一款颠覆传统、引领未来的设备能源数据采集神器——HiWoo Box网关&#xff01; 一、HiWoo Box网关&#xff1a;一站式解决…

xcode 15.3 连接iphone 14PM真机提示 is not available because it is unpair

错误提示&#xff1a;iPhone 14PM is not available because it is unpaired&#xff0c;Pair with the device in the XcodeDevices Window, and respond to anypairing prompts on the device. 1、退出XCode,断开连接设备 2 、在终端执行 sudo pkill usbmuxd 3 、重新打开x…

深度学习在金融交易中的应用:构建智能投资决策系统

&#x1f680; 深度学习在金融交易中的应用&#xff1a;未来投资的智能导航系统 &#x1f31f; 引言 随着人工智能技术的飞速发展&#xff0c;深度学习已经成为金融交易领域中一个强大的工具。通过构建复杂的神经网络模型&#xff0c;我们能够从海量的金融数据中学习并预测市…

Codigger数据篇(下):数据安全的全方位保障

在数字化浪潮中&#xff0c;数据已成为现代企业的核心财富。Codigger作为领先的数据服务平台&#xff0c;深知数据安全对于用户的重要性&#xff0c;因此在深挖数据价值的同时&#xff0c;我们始终坚守数据安全防线。 一、双重加密技术保障 Codigger平台运用先进的加密通信和…

手撕spring框架(2)

相关系列 java中spring底层核心原理解析&#xff08;1&#xff09;-CSDN博客 java中spring底层核心原理解析(2)-CSDN博客 手撕spring框架&#xff08;1&#xff09;-CSDN博客 依赖注入原理 依赖注入(Dependency Injection&#xff0c;简称DI)是一种设计模式&#xff0c;它允许我…