插入排序

插入排序是通过交换位置来达到排序的目的的，看起来和选择排序差不多，选择排序是每一次循环都找到一个当前的最小值，然后与第一个元素交换位置，这样从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由左向右变化的过程中，它左侧的元素总是有序的，这样直到排序完成。很显然，对于部分有序的数组来说，插入排序效率要更高一些。