插入排序
插入排序是通过交换位置来达到排序的目的的，看起来和选择排序差不多，选择排序是每一次循环都找到一个当前的最小值，然后与第一个元素交换位置，这样从0到N，每一个元素依次排好序。插入排序的不同在于它元素交换的次数是不固定的，如果是一个已经排好序的数组，那么就不会交换，考虑最复杂的情况的话，会交换（1 + 2 + ... + N-1），而选择排序会固定交换N-1次，写到这里，好像选择排序可以优化一下，如果本身是排好序的，那么选择排序也不应该做多余的交换：
if(min != i) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
插入排序的代码如下：
private static void insertSort() {
int[] arr = {5, 1, 7, 3, 0, 8, 2, 6, 4, 9};
int N = arr.length;
for(int i=1; i<N; i++) {
for(int j=i; j>0 && arr[j] < arr[j-1]; j--) {
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
}
for(int n=0; n<N; n++) {
System.out.println(arr[n] + " ");
}
}
对于1到N-1之间的每一个i，将arr[i]与arr[0]到arr[i-1]中比它小的所有元素依次有序地交换，在索引i由左向右变化的过程中，它左侧的元素总是有序的，这样直到排序完成。很显然，对于部分有序的数组来说，插入排序效率要更高一些。
