代码之旅

I love Coding !

Java 8 Stream

Stream 是 Java 8 新特性,可对 Stream 中元素进行函数式编程操作,例如 map-reduce。Stream 表示一个序列,其中的元素支持串行或并行的聚合方法。

1
2
3
4
int sum = widgets.stream()
.filter(b -> b.getColor() == RED)
.mapToInt(b -> b.getWeight())
.sum();
阅读全文 »

数据结构-数组

数组是使用最广泛的基础数据结构。数组是存放在连续内存空间上的相同类型数据的集合,可以方便的通过数字索引的方式获取到索引所对应的数据。需要注意的是数组的索引都是从0开始计算的。下图就是长度为3的字符数组的例子。

内存地址100110021003
数组元素‘a’‘b’‘c’
数组索引012

Java 使用数组

Java中的数组声明很简单:

1
2
3
4
5
// 定义时初始化
int[] array = new int[]{0,0,0};
// 通过长度定义, 元素会被初始化为默认值
// int的默认值是0
int[] array = new int[3];

数组提供了一个length参数,可以获取数组的长度。注意一旦创建数组的长度就不能再变化,只能通过重建新的数组扩容。访问数组元素通过索引方式访问和更新。

1
2
3
4
int[] array = new int[3];
int arrayLength = array.length;
int head = array[0];
array[1] = 3;

数组的查找和删除就稍微麻烦一点。对于查找,需要遍历数组,将目标值和每个元素对比。

1
2
3
4
5
6
7
8
int search(int[] arr,int target) {
for (int i = 0; i < arr.length; i++) {
if(arr[i] == target){
return i;
}
}
throw new IllegalArgumentException("not found");
}

对于删除,如果不知道索引的情况下,删除需要遍历数组,如果知道索引,可以通过指定索引的方式删除。但是这还没有结束,数组删除完值后,会留下一个空洞,如果不想有空洞存在,需要将后面的元素依次向前移动。

有序数组

假设一个数组,其元素按照值的固定顺序排序(升序或降序),那么这种数组被称为有序数组。在实际的算法使用中常常会对数组先进行排序,然后在进行处理。下面我们来介绍下一些排序算法。

排序算法

算法代码位置

简单排序算法

常见的简单排序算法有冒泡排序、选择排序、插入排序。

冒泡排序

  1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  3. 针对所有的元素重复以上的步骤,除了最后一个;
  4. 重复步骤1~3,直到排序完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void bubbleSort(int[] arr) {
int temp = 0;
for (int i = arr.length - 1; i > 0; i--) {
// 每次需要排序的长度
for (int j = 0; j < i; j++) {
// 从第一个元素到第i个元素
if (arr[j] > arr[j + 1]) { // 此处是大于,相等的情况不交换位置
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

在相邻元素相等时,它们并不会交换位置,所以,冒泡排序是稳定排序。在数据完全有序的时候展现出最优时间复杂度,为 O(n)O(n)。其他情况下,几乎总是 O(n2)O(n^2)。因此,算法在数据基本有序的情况下,性能最好。

要使算法在最佳情况下有 O(n)O(n) 复杂度,需要做一些改进,增加一个swap的标志,当前一轮没有进行交换时,说明数组已经有序,没有必要再进行下一轮的循环了,直接退出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void bubbleSort(int[] arr) {
int temp = 0;
boolean swap;
for (int i = arr.length - 1; i > 0; i--) {
// 每次需要排序的长度
swap=false;
for (int j = 0; j < i; j++) {
// 从第一个元素到第i个元素
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swap=true;
}
}
if (swap==false){
break;
}
}
}

选择排序

  1. 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
  2. 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
  3. 重复第二步,直到所有元素均排序完毕。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void selectionSort(int[] arr) {
int temp, min = 0;
for (int i = 0; i < arr.length - 1; i++) {
min = i;
// 循环查找最小值
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i) {
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}

用数组实现(就地排序)的选择排序是不稳定的,用链表实现(或者新开辟数组空间)的选择排序是稳定的。不过,一般提到排序算法时,大家往往会默认是数组实现(就地排序),所以选择排序是不稳定的。

1
2
3
2a 2b 1 3
选择排序后 1 2b 2a 3
显然是不稳定的

插入排序

  1. 把待排序的数组分成已排序和未排序两部分,初始的时候把第一个元素认为是已排好序的。
  2. 从第二个元素开始,在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
  3. 重复上述过程直到最后一个元素被插入有序子数组中。
1
2
3
4
5
6
7
8
9
10
11
public static void insertionSort(int[] arr){
for (int i=1; i<arr.length; ++i){
int value = arr[i];
int position=i;
while (position>0 && arr[position-1]>value){
arr[position] = arr[position-1];
position--;
}
arr[position] = value;
}
}

由于只需要找到不大于当前数的位置而并不需要交换,因此,直接插入排序是稳定的排序方法。

归并排序

  • 递归法(Top-down)
    1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
    2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
    3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
    4. 重复步骤3直到某一指针到达序列尾
    5. 将另一序列剩下的所有元素直接复制到合并序列尾
  • 迭代法(Bottom-up)
    1. 将序列每相邻两个数字进行归并操作,形成ceil(n/2)个子序列,排序后每个序列包含两/一个元素
    2. 若此时子序列数不是1个则将上述序列再次归并,形成ceil(n/4)个子序列,每个序列包含四/三个元素
    3. 重复步骤2,直到所有元素排序完毕,即子序列数为1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 递归法
public static void mergeSort(int[] arr){
int[] temp =new int[arr.length];
internalMergeSort(arr, temp, 0, arr.length-1);
}
private static void internalMergeSort(int[] arr, int[] temp, int left, int right){
//当left==right的时,已经不需要再划分了
if (left<right){
int middle = (left+right)/2;
internalMergeSort(arr, temp, left, middle); //左子数组
internalMergeSort(arr, temp, middle+1, right); //右子数组
mergeSortedArray(arr, temp, left, middle, right); //合并两个子数组
}
}
// 合并两个有序子序列
private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
int i=left;
int j=middle+1;
int k=0;
while (i<=middle && j<=right){
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <=middle){
temp[k++] = arr[i++];
}
while ( j<=right){
temp[k++] = arr[j++];
}
//把数据复制回原数组
for (i=0; i<k; ++i){
arr[left+i] = temp[i];
}
}

因为我们在遇到相等的数据的时候必然是按子序列顺序“抄写”到辅助数组上的,所以,归并排序同样是稳定算法。归并排序在数据量比较大的时候也有较为出色的表现(效率上),但是,其空间复杂度O(n)使得在数据量特别大的时候(例如,1千万数据)几乎不可接受。而且,考虑到有的机器内存本身就比较小,因此,采用归并排序一定要注意。

参考

算法 QuickStart

什么是算法?

从一个步骤开始,按照既定的顺序执行完所有的步骤,最终结束得到结果的一个过程。

  • 确定性,算法的每个步骤都是明确的,对结果的预期也是确定的
  • 有穷性,算法必须是由有限个步骤组成的过程,步骤的数量可以是几个,也可以是几百万个,但是必须有一个确定的结束条件
  • 可行性,一般来说我们期望算法得出的是正确的结果,这意味着算法的每个步骤都是可行的,只要有一个步骤不可行,算法就是失败的,或者不能被称为某种算法。
  • 输入和输出,算法总是要解决特定的问题,问题的来源就是算法的输入,期望的结果就是算法的输出。

程序 = 算法+ 数据结构.

将问题抽象为数学模型,输入输出方法和算法步骤是编写计算机算法程序的三大关键要素。对于非常复杂的问题,建立数学模型是很困难的事情,但是对简单的计算机算法而言,建立数学模型实际上就是设计合适的数据结构的问题,同时,输入输出方式和算法步骤的设计都是基于相应的数据结构设计的。

阅读全文 »

Java 类加载

在java代码中,类型的加载,连接与初始化过程都是在程序运行期间完成的(类class文件信息在编译期间已经确定好)。

类从被加载到虚拟机内存中开始,到卸载出内存为止,它的整个生命周期包括:加载Loading、验证Verification、准备Preparation、解析Resolution、初始化Initialization、使用Using和卸载Unloading7个阶段。其中准备、验证、解析3个部分统称为连接Linking

加载、验证、准备、初始化和卸载这5个阶段的顺序是确定的,类的加载过程必须按照这种顺序按部就班地开始,而解析阶段则不一定:它在某些情况下可以在初始化阶段之后再开始,这是为了支持Java语言的运行时绑定(也称为动态绑定或晚期绑定)。

注意,本文的JDK版本是Java 1.8,在Java 9 引进模块化后,ClassLoader也有了一些变化。

阅读全文 »

IEEE 754 标准

浮点数是计算机科学中一种对于实数的近似数值表示法,由一个有效数字(尾数)加上幂数来表示,即二进制的科学计数法。IEEE 协会为了规范统一(方便CPU指令制造,各平台兼容等等)出台了 IEEE Standard for Floating-Point Arithmetic(IEEE-754)二进制浮点数算数标准,选用了浮点数作为储存和算数标准。 该标准描述了包括"浮点数的格式"、“一些特殊数值”、“浮点数的运算”、“舍入规则与例外情况” 等等内容。

阅读全文 »

Java,循环还是递归?

开始比较前,先来了解下循环和递归的定义。

  • 循环是一段在程序中只出现一次,但可能会连续执行多次的代码。循环中的代码会执行特定的次数(例如for),或者是执行到特定条件成立时结束循环(例如while),或者是针对某一集合中的所有项目都执行一次。
  • 递归指在函数的定义中使用函数自身的方法,即一个函数不断调用自身的行为。

在一些函数编程语言(例如Haskell和Scheme)中会使用递归或不动点组合子来达到循环的效果。

阅读全文 »

Java虚拟机-虚拟机栈

在前面的Java虚拟机-内存布局一文中我们简单介绍了虚拟机栈:

  • java虚拟机栈是线程私有的,他与线程的声明周期同步。虚拟机栈描述的是java方法执行的内存模型。
  • 每个方法执行都会创建一个栈帧,栈帧包含局部变量表、操作数栈、动态连接、方法出口等。

本文将继续详细介绍虚拟机栈。

阅读全文 »