排序算法--直接插入排序

算法思想：

直接插入排序的基本思想是每一步将右边一个待排序的记录，插入到左边已经排好序的有序序列中去，直到插完数组中的所有元素为止。
上图：

1024555-20161126000335346-416319390.png

代码实现

public class Insertion{
  //插入排序
  public static void sort(int[] arr){
   for(int i = 0;i<arr.length;i++){
         //最坏的比较次数：1+2+3+...+(N-1)=(N-1+1)*(N-1)/2=N*(N-1)/2 约为N^2/2
          //最好的比较次数为N-1次
          //平均比较次数约为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;
  }


}