算法思想：
直接插入排序的基本思想是每一步将右边一个待排序的记录，插入到左边已经排好序的有序序列中去，直到插完数组中的所有元素为止。
上图：
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;
}
}
网友评论