当前位置 博文首页 > 如何彻底搞懂 Java 数据结构?CSDN 博文精选_weixin_39742568的
作者 | 张振华.Jack
责编?| 郭芮
出品 |?CSDN 博客
本文和大家一起来重温《Java数据结构》经典之作。Java数据结构
要理解Java数据结构,必须能清楚何为数据结构?数据结构:数据结构在Java的语言体系中按逻辑结构可以分为两大类:线性数据结构和非线性数据结构。
- Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系。
- 而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构。
- 而一个数据结构的设计过程分成抽象层、数据结构层和实现层。
线性数据结构:常见的有一维数组,线性表,栈,队列,双队列,串。1、一维数组 在Java里面常用的util有:String [],int [],ArrayList,Vector,CopyOnWriteArrayList等,及可以通过一维数组[]自己实现不同逻辑结构的Util类,而ArrayList封装了一些[]的基本操作方法。 ArrayList和Vector的区别是:Vector是线程安全的,方法同步。CopyOnWriteArrayList也是线程安全的但效率要比Vector高很多。 数组这种数据结构典型的操作方法,是根据下标进行操作的,所以insert的的时候可以根据下标插入到具体的某个位置,但是这个时候它后面的元素都得往后面移动一位。所以插入效率比较低,更新,删除效率也比较低,而查询效率非常高,查询效率时间复杂度是1。 2、线性表 线性表是有序的储存结构、链式的储存结构。链表的物理储存空间是不连续的,链表的每一个节点都知道上一个节点、或者下一个节点是谁,通常用Node表示。常见的有顺序链表(LinkedList、Linked***),单项链表(里面只有Node类),双向链表(两个Node类),循环链表(多个Node类)等。 操作方法:插入效率比较高,插入的时候只需要改变节点的前后节点的连接即可。而查询效率就比较低了,如果实现的不好,需要整个链路找下去才能找到应该找的元素。所以常见的方法有:add(index,element),addFirst(element),addLast(element),getFirst(),getLast(),get(element)等。 常见的Uitil有:LinkedList,LinkedMap等,而这两个JDK底层也做了N多优化,可以有效避免查询效率低的问题,当自己实现的时候需要注意。 其实树形结构可以说是非线性的链式储存结构。 ? ? 3、栈Stack 栈,最主要的是要实现先进后出,后进先出的逻辑结构。来实现一些场景对逻辑顺序的要求。所以常用的方法有push(element)压栈,pop()出栈。 java.util.Stack就实现了这用逻辑,而Java的Jvm里面也用的到了此种数据结构,就是线程栈,来保证当前线程的执行顺序。 4、队列 队列,队列是一种特殊的线性数据结构,队列只能允许在队头,队尾进行添加和查询等相关操作。队列又有单项有序队列、双向队列、阻塞队列等。 Queue这种数据结构注定了基本操作方法有:add(E e)加入队列,remove(),poll()等方法。 队列在Java语言环境中是使用频率相当高的数据结构,所有其实现的类也很多来满足不同场景。
使用场景也非常多,如线程池、MQ、连接池等。5、串 串:也称字符串,是由N个字符组成的优先序列。在Java里面就是指String,而String里面是由chat[]来进行储存。
KMP算法: 这个算法一定要牢记,Java数据结构这本书里面针对字符串的查找匹配算法也只介绍了一种。关键点就是:在字符串比对的时候,主串的比较位置不需要回退的问题。
非线性数据结构:常见的有:多维数组,集合,树,图,散列表(hash)。1、多维数组 一维数组前面咱也提到了,多维数组无非就是String [][],int[][]等。Java里面很少提供这样的工具类,而Java里面tree和图底层的native方法用了多维数组来储存。 2、集合 由一个或多个确定的元素所构成的整体叫做集合,在Java里面可以去广义的去理解为实现了Collection接口的类都叫集合。 3、树
树形结构,作者觉得它是一种特殊的链形数据结构。最少有一个根节点组成,可以有多个子节点。树,显然是由递归算法组成。树的特点:
红黑树的5条性质:
树总结:?树在Java里面应用的也比较多。非排序树,主要用来做数据储存和展示。而排序树,主要用来做算法和运算,HashMap里面的TreeNode就用到了红黑树算法。而B+树在数据库的索引原理里面有典型的应用。? ??4、Hash Hash概念:
一致性Hash:
我们查看一下HashMap的原理,其实发现Hash很好的解决了单体应用情况下的数据查找和插入的速度问题。但是毕竟单体应用的储存空间是有限的,所有在分布式环境下,应运而生了一致性Hash算法。 用意和hashCode的用意一样,只不过它是取模放在不同的IP机器上而已。具体算法可以找一下相关资料。 而一致性Hash需要注意的就是默认分配的桶比较多些,而当其中一台机器挂了,影响的面比较小一些。 需要注意的是,相同的内容算出来的hash一定是一样的。既:幂等性。 理解了Java数据结构,还必须要掌握一些常见的基本算法。 理解算法之前必须要先理解的几个算法的概念:空间复杂度:一句来理解就是,此算法在规模为n的情况下额外消耗的储存空间。 时间复杂度:一句来理解就是,此算法在规模为n的情况下,一个算法中的语句执行次数称为语句频度或时间频度。 稳定性:主要是来描述算法,每次执行完,得到的结果都是一样的,但是可以不同的顺序输入,可能消耗的时间复杂度和空间复杂度不一样。
????public?static?void?main(String[]?args)?{????????int?srcArray[]?=?{3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};????????System.out.println(binSearch(srcArray,?28));????}????/**
?????*?二分查找普通循环实现
?????*
?????*?@param?srcArray?有序数组
?????*?@param?key?查找元素
?????*?@return
?????*/????public?static?int?binSearch(int?srcArray[],?int?key)?{????????int?mid?=?srcArray.length?/?2;//????????System.out.println("=:"+mid);????????if?(key?==?srcArray[mid])?{????????????return?mid;????????}//二分核心逻辑????????int?start?=?0;????????int?end?=?srcArray.length?-?1;????????while?(start?<=?end)?{//????????????System.out.println(start+"="+end);????????????mid?=?(end?-?start)?/?2?+?start;????????????if?(key?????????????????end?=?mid?-?1;????????????}?else?if?(key?>?srcArray[mid])?{????????????????start?=?mid?+?1;????????????}?else?{????????????????return?mid;????????????}????????}????????return?-1;????}
二分查找算法如果没有用到递归方法的话,只会影响CPU。对内存模型来说影响不大。时间复杂度log2n,2的开方。空间复杂度是2。一定要牢记这个算法。应用的地方也是非常广泛,平衡树里面大量采用。
????public?static?void?main(String[]?args)?{????????int?srcArray[]?=?{3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};????????System.out.println(binSearch(srcArray,?0,15,28));????}????/**
?????*?二分查找递归实现
?????*
?????*?@param?srcArray??有序数组
?????*?@param?start?数组低地址下标
?????*?@param?end???数组高地址下标
?????*?@param?key??查找元素
?????*?@return?查找元素不存在返回-1
?????*/????public?static?int?binSearch(int?srcArray[],?int?start,?int?end,?int?key)?{????????int?mid?=?(end?-?start)?/?2?+?start;????????if?(srcArray[mid]?==?key)?{????????????return?mid;????????}????????if?(start?>=?end)?{????????????return?-1;????????}?else?if?(key?>?srcArray[mid])?{????????????return?binSearch(srcArray,?mid?+?1,?end,?key);????????}?else?if?(key?????????????return?binSearch(srcArray,?start,?mid?-?1,?key);????????}????????return?-1;????}
递归几乎会经常用到,需要注意的一点是:递归不光影响的CPU。JVM里面的线程栈空间也会变大。所以当递归的调用链长的时候需要-Xss设置线程栈的大小。
平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
---|---|---|---|
O(n2) | O(n) | O(n2) | O(1) |
冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n2/2次, 时间复杂度为O(n2). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n2). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).Tips:由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法。
/**
?*?冒泡排序
?*
?*?①. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
?*?②. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
?*?③. 针对所有的元素重复以上的步骤,除了最后一个。
?*?④. 持续每次对越来越少的元素重复上面的步骤①~③,直到没有任何一对数字需要比较。
?*?@param?arr??待排序数组
?*/public?static?void?bubbleSort(int[]?arr){????for?(int?i?=?arr.length;?i?>?0;?i--)?{??????//外层循环移动游标????????for(int?j?=?0;?j?1)?//内层循环遍历游标及之后(或之前)的元素????????????if(arr[j]?>?arr[j+1]){????????????????int?temp?=?arr[j];????????????????arr[j]?=?arr[j+1];????????????????arr[j+1]?=?temp;????????????????System.out.println("Sorting:?"?+?Arrays.toString(arr));????????????}????????}????}}
2、快速排序
快速排序使用分治策略来把一个序列(list)分为两个子序列(sub-lists)。步骤为:
①从数列中挑出一个元素,称为”基准”(pivot)。
②重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
③递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
代码实现:
用伪代码描述如下:
①i = L; j = R; 将基准数挖出形成第一个坑a[i]。
②j--,由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
③i++,由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。
④再重复执行②,③二步,直到i==j,将基准数填入a[i]中。
快速排序采用“分而治之、各个击破”的观念,此为原地(In-place)分区版本。
/**
?*?快速排序(递归)
?*
?*?①. 从数列中挑出一个元素,称为"基准"(pivot)。
?*?②. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
?*?③. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
?*?@param?arr???待排序数组
?*?@param?low???左边界
?*?@param?high??右边界
?*/public?static?void?quickSort(int[]?arr,?int?low,?int?high){????if(arr.length?<=?0)?return;????if(low?>=?high)?return;????int?left?=?low;????int?right?=?high;????int?temp?=?arr[left];???//挖坑1:保存基准的值????while?(left?????????while(left?=?temp){??//坑2:从后向前找到比基准小的元素,插入到基准位置坑1中????????????right--;????????}????????arr[left]?=?arr[right];????????while(left?//坑3:从前往后找到比基准大的元素,放到刚才挖的坑2中????????????left++;????????}????????arr[right]?=?arr[left];????}????arr[left]?=?temp;???//基准值填补到坑3中,准备分治递归快排????System.out.println("Sorting:?"?+?Arrays.toString(arr));????quickSort(arr,?low,?left-1);????quickSort(arr,?left+1,?high);}
以下是快速排序算法复杂度:
平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
---|---|---|---|
O(nlog?n) | O(nlog?n) | O(n2) | O(1)(原地分区递归版) |
热 文?推 荐?
? 微软获批可向华为出口软件; 英特尔因CPU短缺向PC厂商道歉; Spring Tools 4.4.2 发布 | 极客头条 ?只需三种手段,将传统的网站的性能提高 24%! ?揭秘支撑双 11 买买买背后的硬核黑科技!?乔布斯的简历 120 万被拍卖,HR 看了想打人
? 假如有人把支付宝存储服务器炸了?AutoML未来可期,工程师的明天何去何从?
?区块链+“中国制造”:一文看懂区块链如何提升供应链金融活力与效能!
你点的每个“在看”,我都认真当成了喜欢cs