插入排序原本的实现方式之一：
public int[] sort_ori(int[] ins) {
for (int i = 1; i < ins.length; i++) {
int currentIndex = i;
int currentValue = ins[i];
int switchIndex = -1;
for (int j = 0; j < currentIndex; j++) {
if (ins[j] > currentValue) {
switchIndex = j;
break;
}
}
System.out.println(switchIndex);
if (switchIndex >= 0) {
if (currentIndex - switchIndex >= 0)
System.arraycopy(ins, switchIndex, ins, switchIndex + 1, currentIndex - switchIndex);
ins[switchIndex] = currentValue;
}
}
return ins;
}
插入排序算法对应的比喻例子是打牌时抽牌的过程，如果目标的数据类型为链表的话，用插入排序会特别适合。
这边的目标数据类型是数组，并且是原地算法，更贴切的比喻是按照颜色深浅整理蜡笔盒里的蜡笔。
步骤的话，就是取出某根蜡笔，然后找到它对应的位置，然后将这个位置之后的蜡笔都滚动到下一列。
因此原来的算法中会有3个循环
loop1：从头到尾选择被排列的对象
loop2：在这个位置之前寻找对象应该放置的位置
loop3：将该位置之后原对象位置之前的所有蜡笔滚到右边
嵌套其实是挺反人类的，它通常以一个for循环或者while循环作为标志，但除非将其上下的代码都看一遍，或者看注释，不然很难第一眼就看出这个循环到底要做什么。
通过lambda表达式对插入排序进行重写：
public int[] sort_lambda(int[] ins) {
IntStream.range(1, ins.length).forEach(currentIndex -> {
int currentValue = ins[currentIndex];
IntStream.range(0, currentIndex).filter(j -> ins[j] > currentValue).findFirst().ifPresent(switchIndex -> {
IntStream.iterate(currentIndex, a2 -> a2 - 1).limit(currentIndex - switchIndex).forEach(a2 -> {
ins[a2] = ins[a2 - 1];
});
ins[switchIndex] = currentValue;
});
});
return ins;
}
这里用3个IntStream的操作替代了之前3个loop
其中loop2的代码变成了“IntStream.range(0, currentIndex).filter(j -> ins[j] > currentValue).findFirst().ifPresent(xxx)”
之前一直以为流操作都会从头执行到尾，但今天测试过才发现并不是这样，可以简单测试一下。
@Test
public void run() {
int[] a = new int[]{5, 4, 3, 2, 1};
Arrays.stream(a).filter(a1->{
System.out.println("comparing "+a1);
return a1>3;
}).findFirst();
}
这个方法会去判断数组a中的值，找到第一个大于3的值。原本以为它的执行方式会像它的方法链一样，将[5,4,3,2,1]转换为[5,4]之后再根据findFirst()给出5。
但控制台的输出为：
也就是只执行了第一个比较。。。
然后忽然想起来，之前常的limit。。也是处于方法链的后端（而不是作为参数放到stream的处理中），可能stream底层通过反射的机制，像sql一样有个优化器的实现吧。（妈蛋以前一直以为流会从头执行到尾，很多不需要遍历到底的业务不敢用stream，白担心了）
既然这样，实现loop2就可以放心大胆的使用stream了。
loop2：在这个位置之前寻找对象应该放置的位置
IntStream.range(0,currentIndex) ---- 对于loop1中指定对象之前的位置（左闭右开）
.filter(a1-> ins[a1]>currentValue) ---- 判断其是否大于loop1指定的值
.findFirst() ---- 找到第一个就行了
.ifPresent(loop3) ---- 如果存在的话，执行loop3
能像写sql一样写java，同时性能也不会有损失，挺开心的