3分钟速读原著《Java数据结构与算法》(二)

第三章 简单排序

1.简单排序的种类

• 1.1 冒泡排序:算法运行速度非常慢,简单来说就是每两个元素都需要执行一次比较,最终得出结果.
• 1.2 选择排序:选择排序就是把每个数都和其中的一个固定值进行比较,大的一边,小的一边,可以理解为拿一个固定的最小值,将所有的值都和这个值进行比较,最终排出完整的顺序
• 1.3 插入排序:条件是必须要局部有序,冒泡排序和选择排序当中都是不存在局部有序的,插入排序简单来说就是将其中一个做为标记,将被标记的这个元素插入到局部有序的队列当中,因此而不断轮换对应的标记元素,从而完成所有的排序
• 1.4 对象排序:根据对象当中的某个属性来排序
• 1.5 单词排序:字母顺序排序,根据字母表的字母顺序进行排序

2.简单排序之间的比较

• 2.1 一般情况下不使用冒泡排序,数据量很小的时候有用
• 2.2 选择排序虽然吧交换次数降到了最低,单词书仍然很大,当数据量小的时候,并且交换数据相对于比较数据更加耗时的情况下,可以使用选择排序
• 2.3 大多数情况下,假设当数据量比较小,或者说基本上有序的时候,插入排序算法是三种简单排序算法中最好的选择

3.小结

• 3.1 本章提及的排序算法都是嘉定了数组作为数据存储的结构
• 3.2 排序包括比较数组中数据项的关键字和移动响应的数据项
• 3.3 本章所有的算法的时间负责度都是O(n2),n表示元素个数,O表示复杂度(详见大O表示法)
• 3.4 不变性指的是算法运行时保持不变的条件
• 3.5 冒泡排序算法是效率最差的算法,但是最简单
• 3.6 如果具有相同关键字的数据项,经过排序他它们的顺序保持不变,这笔昂的排序就是稳定的

第四章 栈和队列

一、栈

举例说明:在邮局经常需要去处理邮件,邮件会从下至上堆积成为一个栈,此时处理的方式就是先处理最上面的邮件,这种方式只有能够在合理的时间内从容处理完所有的信件,这种工作方式才不会产生太大麻烦,否则最底层的信件就将会永远无法得到处理

1.栈的实战示例

• 1.1 单词逆序:简单来说就是依据栈后进先出的特点,将单词的每个字符都压进栈空间,然后再一个个的输出,此时就形成了倒着排序的效果
• 1.2 分隔符匹配:例如使用栈空间来进行解析Java文件是否合法,每个大括号和小括号都是需要一对对的对应着的,可以将每个左边的小括号或者大括号压到栈当中,每当读取到下一个右小括号或者右大括号时就弹出,没有匹配成功,则报错
• 1.3 栈的效率:数据入栈和出栈的书剑复杂度为常数O(1),也就说明栈操作所消耗的时间不依赖于栈中数据项的个数,因此操作时间很短.栈不需要比较哦和移动操作

2.队列

特性就是FIFO

3.优先级队列

优先级队列的方式就是在每个入队的元素当中加上关键字的判断,使得这个优先级的队列进行内部排序,使得整个队列变成一个有序队列,优先级队列可以保证重要的任务先执行,但是如果不断的向优先级队列当中插入优先级高的任务,可能导致所有优先级低的队列永远都得不到执行的机会

4.小结

• 4.1 栈 , 队列, 优先级队列经常用于简化某些程序操作的数据结构
• 4.2.这些数据结构中, 只有一个数据项可以被访问
• 4.3 栈允许访问最后一个插入的数据项
• 4.4 栈当中最重要的操作就是在栈顶插入一个数据项,以及从栈顶移除一个数据项
• 4.5 队列只允许访问第一个插入的数据项
• 4.6 队列的重要操作就是在对位插入数据和在队头移除数据项
• 4.7 队列可以实现为循环队列,它基于数组,数组下标可以从数组末端回绕到数组的开始位置
• 4.8 优先级队列只允许访问最小的或者最大的数据项

第五章 链表

链表就好像是火车,它的每个链表对象都会引用下一个或者上一个链表对象,所以链表相比于数组的优点就是增加一个链表节点或者删除一个链表节点都会比数组的快,相对来说数组的根据索引查询就会比链表快,但是如果是不知道索引的线性搜索查询,其实本质上速度跟链表并没有什么区别

1.单向链表

单向链表类似于栈,特点:

• 1.1 只能在链表头插入一个数据项
• 1.2 也只能在链表头部删除一个数据项
• 1.3 遍历链表显示它的内容

2.双向链表

就是在双向链表的对象当中引入了对最后一个节点的引用,针对于最后一个节点也可以像对第一个节点一样的进行相对应的引用操作,并且在每个链表节点当中不仅可以找到它的上一个节点,也可以找到他的下一个节点

3.链表的效率

• 3.1 插入和删除快,只需要改变引用值,所有花费O(1)的时间
• 3.2 链表比数组的另一个优越性是需要多少内存就可以使用多少内存,数组的内存一般是在初始化的时候就已经固定了,所以会经常出现由于数组太大而效率过于低下或者是数组太小而导致空间溢出的问题,所以从这个角度上看,虽然后来的ArrayList自动扩容解决了数组初始化时固定大小的缺陷,但是也会因为他的扩容过大而没有再插入数据,导致空间浪费的可能性,相比之下,链表的特性就是需要多少就拓展多少,可能拓展的次数会比较多了,但是内存的利用率会更高了

4.有序链表

简单来说就是有顺序的链表结构

• 4.1 有序链表的效率

在有序链表当中插入或者删除某一项最多需要O(N)次比较,平均是N/2次,因为必须要沿着链表一步步走才能找到正确的位置,可以在O(1)时间内找到或者删除最小值,因为它总是在表头,如果需求时一个应用频繁的存取最小值,而且不需要快速的插入,那么有序链表是一个非常有效的方案选择,例如优先级队列就可以使用有序链表来进行实现

5.双端链表

双向链表要区分于双端链表,双端链表是可以找到该节点的上一个节点的,但是双向链表只是能够从链表的两端同时进行遍历,并不能够找到任意一个节点的上一个节点

6.小结

• 6.1 链表包含了一个LinkedList对象和许多Link对象
• 6.2 LinkedList对象包含一个引用,这个引用通常叫做first,它指向链表的第一个节点
• 6.3 每个Link对象包含数据和一个引用,通常叫做next,它指向链表的下一个链节点
• 6.4 Next字段为null意味着链表的结尾
• 6.5 在表头插入链节点需要把新链节点的next字段指向原来的第一个链节点,然后让first指向新节点
• 6.6 在表头删除链节点要把first指向first.next
• 6.7 为了遍历链表,都是使用每个链表的next字段找到下一个节点
• 6.8 通过遍历链表可以找到拥有特定值的链节点,一旦找到,可以显示,删除或者用其他方式操作该链节点
• 6.9 新的链节点可以可以插在某个特定值的链节点的前面或者后面,首先要遍历找到这个链节点

备注:有序数组查询快,无序数组索引查询快,链表增加和删除快

• 6.10 有序链表当中,链节点按照关键值升序或者降序排列
• 6.11 双向链表当中,每个链节点都包含了对其挨个链节点的引用,同时又有对后一个链节点的引用
• 6.12 双向链表允许反向遍历,并且可以从表尾删除
• 6.13 迭代器是一个引用,它被封装在类对象中,这个引用指向相关联的链表中的链节点