【jdk8源码】Arrays.sort插入排序
最近再看数据结构与算法相关的书籍，想着看有没有什么现实中应用的案例结果就在jdk源码中发现了插入排序的身影。
插入排序的核心思想；
插入排序（insertionsort）算法适用于包括向量与列表在内的任何序列结构。算法的思路可简要描述为：始终将整个序列视作并切分为两部分：有序的前缀，无序的后缀；通过迭代，反复地将后缀的首元素转移至前缀中。
由此亦可看出插入排序算法的不变性:
Z在任何时刻，相对于当前节点e = S[r]，前缀S[0, r)总是业已有序
在任何时刻，当前节点以前的数据都是有序的，后面是无序的可以看一个简单的案例；
所以总结算法就是如何对已经遍历的数据进行插入排序的问题，核心思想我们都知道了，看看jdk大佬怎么写的
int list8[] = {44, 22, 33, 11};
Arrays.sort(list8);
跟踪代码，可以找到
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
if (length < INSERTION_SORT_THRESHOLD) {当长度小于47时进行插入排序
if (leftmost) {
/*
* Traditional (without sentinel) insertion sort,
* optimized for server VM, is used in case of
* the leftmost part.*/
for (int i = left, j = i; i < right; j = ++i) {
int ai = a[i + 1];取出当前节点的下一个节点
while (ai < a[j]) {在已经排好序的数字中，选择一个正确位置进行插入，
a[j + 1] = a[j]; 大的数字往后移动一位
if (j-- == left) {指针左移一位，直到找到该插入的位置。这种做法也避免了没必要的遍历。
break;
}
}
a[j + 1] = ai;
}
} else {
/*其他代码
虽然代码不长，但是也是通过自己写的测试案例，简单跟踪了下代码，才理解了这段插入排序的代码，对于这段代码，其实对于一个逆序数组来说，其实时间复杂度还是O(n2),这个通过两层循环也可以看出。