Java 8 Stream
数据结构-数组
数据结构-数组
数组是使用最广泛的基础数据结构。数组是存放在连续内存空间上的相同类型数据的集合,可以方便的通过数字索引的方式获取到索引所对应的数据。需要注意的是数组的索引都是从0开始计算的。下图就是长度为3的字符数组的例子。
内存地址 | 1001 | 1002 | 1003 |
---|---|---|---|
数组元素 | ‘a’ | ‘b’ | ‘c’ |
数组索引 | 0 | 1 | 2 |
Java 使用数组
Java中的数组声明很简单:
1 | // 定义时初始化 |
数组提供了一个length参数,可以获取数组的长度。注意一旦创建数组的长度就不能再变化,只能通过重建新的数组扩容。访问数组元素通过索引方式访问和更新。
1 | int[] array = new int[3]; |
数组的查找和删除就稍微麻烦一点。对于查找,需要遍历数组,将目标值和每个元素对比。
1 | int search(int[] arr,int target) { |
对于删除,如果不知道索引的情况下,删除需要遍历数组,如果知道索引,可以通过指定索引的方式删除。但是这还没有结束,数组删除完值后,会留下一个空洞
,如果不想有空洞
存在,需要将后面的元素依次向前移动。
有序数组
假设一个数组,其元素按照值的固定顺序排序(升序或降序),那么这种数组被称为有序数组。在实际的算法使用中常常会对数组先进行排序,然后在进行处理。下面我们来介绍下一些排序算法。
简单排序算法
常见的简单排序算法有冒泡排序、选择排序、插入排序。
冒泡排序
- 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
- 针对所有的元素重复以上的步骤,除了最后一个;
- 重复步骤1~3,直到排序完成。
1 | public static void bubbleSort(int[] arr) { |
在相邻元素相等时,它们并不会交换位置,所以,冒泡排序是稳定排序。在数据完全有序的时候展现出最优时间复杂度,为 O(n)。其他情况下,几乎总是 O(n2)。因此,算法在数据基本有序的情况下,性能最好。
要使算法在最佳情况下有 O(n) 复杂度,需要做一些改进,增加一个swap的标志,当前一轮没有进行交换时,说明数组已经有序,没有必要再进行下一轮的循环了,直接退出。
1 | public static void bubbleSort(int[] arr) { |
选择排序
- 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
- 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
- 重复第二步,直到所有元素均排序完毕。
1 | public static void selectionSort(int[] arr) { |
用数组实现(就地排序)的选择排序是不稳定的,用链表实现(或者新开辟数组空间)的选择排序是稳定的。不过,一般提到排序算法时,大家往往会默认是数组实现(就地排序),所以选择排序是不稳定的。
1 | 2a 2b 1 3 |
插入排序
- 把待排序的数组分成已排序和未排序两部分,初始的时候把第一个元素认为是已排好序的。
- 从第二个元素开始,在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
- 重复上述过程直到最后一个元素被插入有序子数组中。
1 | public static void insertionSort(int[] arr){ |
由于只需要找到不大于当前数的位置而并不需要交换,因此,直接插入排序是稳定的排序方法。
归并排序
- 递归法(Top-down)
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
- 迭代法(Bottom-up)
- 将序列每相邻两个数字进行归并操作,形成ceil(n/2)个子序列,排序后每个序列包含两/一个元素
- 若此时子序列数不是1个则将上述序列再次归并,形成ceil(n/4)个子序列,每个序列包含四/三个元素
- 重复步骤2,直到所有元素排序完毕,即子序列数为1
1 | // 递归法 |
因为我们在遇到相等的数据的时候必然是按子序列顺序“抄写”到辅助数组上的,所以,归并排序同样是稳定算法。归并排序在数据量比较大的时候也有较为出色的表现(效率上),但是,其空间复杂度O(n)使得在数据量特别大的时候(例如,1千万数据)几乎不可接受。而且,考虑到有的机器内存本身就比较小,因此,采用归并排序一定要注意。
参考
算法 QuickStart
算法 QuickStart
什么是算法?
从一个步骤开始,按照既定的顺序执行完所有的步骤,最终结束得到结果的一个过程。
- 确定性,算法的每个步骤都是明确的,对结果的预期也是确定的
- 有穷性,算法必须是由有限个步骤组成的过程,步骤的数量可以是几个,也可以是几百万个,但是必须有一个确定的结束条件
- 可行性,一般来说我们期望算法得出的是正确的结果,这意味着算法的每个步骤都是可行的,只要有一个步骤不可行,算法就是失败的,或者不能被称为某种算法。
- 输入和输出,算法总是要解决特定的问题,问题的来源就是算法的输入,期望的结果就是算法的输出。
程序 = 算法+ 数据结构.
将问题抽象为数学模型,输入输出方法和算法步骤是编写计算机算法程序的三大关键要素。对于非常复杂的问题,建立数学模型是很困难的事情,但是对简单的计算机算法而言,建立数学模型实际上就是设计合适的数据结构的问题,同时,输入输出方式和算法步骤的设计都是基于相应的数据结构设计的。
Java 类加载
Java 类加载
在java代码中,类型的加载,连接与初始化过程都是在程序运行期间完成的(类class文件信息在编译期间已经确定好)。
类从被加载到虚拟机内存中开始,到卸载出内存为止,它的整个生命周期包括:加载Loading
、验证Verification
、准备Preparation
、解析Resolution
、初始化Initialization
、使用Using
和卸载Unloading
7个阶段。其中准备、验证、解析3个部分统称为连接Linking
。
加载、验证、准备、初始化和卸载这5个阶段的顺序是确定的,类的加载过程必须按照这种顺序按部就班地开始,而解析阶段则不一定:它在某些情况下可以在初始化阶段之后再开始,这是为了支持Java语言的运行时绑定(也称为动态绑定或晚期绑定)。
注意,本文的JDK版本是Java 1.8,在Java 9 引进模块化后,ClassLoader也有了一些变化。