插入排序，感觉挺有意思，可以理解成扑克牌，先取了张12，新取了张15，比12大，放右边；新取了张9，比15小，左移，和15换个位置，比12也小，继续左移
源码
package Love;
/**
* Hello world!
*/
public class App {
public static void insertionSort(int[] arr) {
int len = arr.length;
int preIndex = 0;
int thisNum = 0;
for (int i = 0; i < len - 1; i++) {
preIndex = i;
thisNum = arr[i + 1];
while (preIndex >= 0 && arr[preIndex] > thisNum) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = thisNum;
}
}
public static void main(String[] args) {
int arr[] = {4, 6, 3, 9, 6, 5, 1, 7, 6, 5, 2, 8};
insertionSort(arr);
for(int a : arr){
System.out.print(a + " ");
}
}
}
6比4大，while里不执行，直接arr[1]=6；变成了4 6
3比6小，执行while里的交换，arr[2]=6，preIndex=0；arr[0]=4>3继续成立，执行while里的交换，arr[1]=4，preIndex=-1；接着退出while，arr[0]=3；变成了3 4 6
9比6大，while里不执行，arr[3]=9；变成了3 4 6 9
6比9小，执行while里的交换，arr[4]=9，preIndex=2；arr[2]=6 > 6不成立，因此while结束；arr[3]=6；变成3 4 6 6 9
如此循环最终得到结果
