算法思想：
直接插入排序的基本思想是每一步將右邊一個(gè)待排序的記錄杯聚，插入到左邊已經(jīng)排好序的有序序列中去囚霸，直到插完數(shù)組中的所有元素為止。
上圖：
1024555-20161126000335346-416319390.png
代碼實(shí)現(xiàn)
public class Insertion{
//插入排序
public static void sort(int[] arr){
for(int i = 0;i<arr.length;i++){
//最壞的比較次數(shù)：1+2+3+...+(N-1)=(N-1+1)*(N-1)/2=N*(N-1)/2 約為N^2/2
//最好的比較次數(shù)為N-1次
//平均比較次數(shù)約為N^2/4
for(int j = i;j>0 && arr[j]<arr[j-1];j--){
swap(arr,j.j-1)
}
}
}
//交換指定元素
public static void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
