插入排序

插入排序是通過交換位置來達(dá)到排序的目的的，看起來和選擇排序差不多，選擇排序是每一次循環(huán)都找到一個(gè)當(dāng)前的最小值，然后與第一個(gè)元素交換位置，這樣從0到N，每一個(gè)元素依次排好序。插入排序的不同在于它元素交換的次數(shù)是不固定的，如果是一個(gè)已經(jīng)排好序的數(shù)組，那么就不會(huì)交換，考慮最復(fù)雜的情況的話，會(huì)交換（1 + 2 + ... + N-1），而選擇排序會(huì)固定交換N-1次，寫到這里，好像選擇排序可以優(yōu)化一下，如果本身是排好序的，那么選擇排序也不應(yīng)該做多余的交換：

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] + " ");
    }
}

對(duì)于1到N-1之間的每一個(gè)i，將arr[i]與arr[0]到arr[i-1]中比它小的所有元素依次有序地交換，在索引i由左向右變化的過程中，它左側(cè)的元素總是有序的，這樣直到排序完成。很顯然，對(duì)于部分有序的數(shù)組來說，插入排序效率要更高一些。