算法思路
插入排序就是每一步都將一個(gè)待排數(shù)據(jù)按其大小插入到已經(jīng)排序的數(shù)據(jù)中的適當(dāng)位置，直到全部插入完畢。 非常類似于打牌時(shí)候一邊抓牌一遍理牌的情形。
插入排序方法分直接插入排序和折半插入排序兩種，這里只介紹直接插入排序。
??文字說(shuō)比較抽象, 下面有個(gè)動(dòng)態(tài)圖鏈接??幫助理解:
插入排序動(dòng)態(tài)演示圖
算法實(shí)現(xiàn)
public class InsertionSort {
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) // i表示現(xiàn)在正在遍歷元素的下標(biāo)
//從遍歷的那個(gè)元素開(kāi)始向前進(jìn)行比較，碰到比之前一個(gè)元素小就交換，
//不然直接break(因?yàn)樽筮厖^(qū)域已經(jīng)有序，若a[j]比a[j-1]大那么一定比a[j-2],a[j-3]...大，那就不用比較交換了)
for (int j = i; j > 0; j--)
if (less(a, j, j - 1))
swap(a, j, j - 1);
else
break;
}
private static boolean less(Comparable[] a, int i, int j) {
if (a[i].compareTo(a[j]) < 0)
return true;
else
return false;
}
private static void swap(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
}
性能分析
??首先給一個(gè)前提，插入排序性能是有最好情況和最壞情況的，不一樣。
??那哪種情況是最好情況？相信你猜出來(lái)了就是已經(jīng)有序的待排數(shù)組的情況。如果數(shù)組已經(jīng)有序, 那么看代碼，里層循環(huán)永遠(yuǎn)不會(huì)執(zhí)行(會(huì)執(zhí)行break語(yǔ)句)，所以只有外層循環(huán)起作用那么時(shí)間復(fù)雜度就是O(N)。
??那哪種情況是最好情況？相信你也猜出來(lái)了就是完全逆序的待排數(shù)組的情況。數(shù)組完全逆序，插入第2個(gè)元素時(shí)要比較交換前1個(gè)元素，插入第3個(gè)元素時(shí)，要比較交換前2個(gè)元素，……，插入第N個(gè)元素，要比較交換前 N - 1 個(gè)元素。因此，最壞情況下的比較次數(shù)是 1 + 2 + 3 + ... + (N - 1)，等差數(shù)列求和，結(jié)果為 N^2 / 2，所以最壞情況下的時(shí)間復(fù)雜度為 O(N^2)?？臻g復(fù)雜度則很直觀O(1)。
??綜上所述，通過(guò)某些數(shù)學(xué)證明(我目前不懂那個(gè)證明，還請(qǐng)網(wǎng)友告知)已經(jīng)證明出，對(duì)于一個(gè)完全random且元素不重復(fù)的帶排序數(shù)組，用插入排序平均需要 ? N^2 次比較和? N^2 交換操作。
??我大概只能從下面這張插入排序步驟圖大概看出? N^2 這個(gè)數(shù)字的來(lái)源。因?yàn)槊啃谢疑氖敲看味疾灰苿?dòng)已經(jīng)排序好的元素，黑色的是移動(dòng)的元素，可以看出移動(dòng)的元素面積大概是所有面積的1/4，這就是平均需要 ? N^2 次比較和? N^2 交換操作的直觀證明。(但是我不知道怎么具體證明......)
拓展
??如果數(shù)組中倒序的元素?cái)?shù)量小于數(shù)組大小的某個(gè)倍數(shù)，那么我們就說(shuō)這個(gè)數(shù)組部分有序。
有幾種典型的部分有序數(shù)組：
- 數(shù)組中每個(gè)元素距離它最終位置不遠(yuǎn);
- 一個(gè)基本有序的大數(shù)組接一個(gè)無(wú)序小數(shù)組;
- 數(shù)組中只有幾個(gè)元素位置不對(duì);
這些數(shù)組都適合用插入排序。
??逆序?qū)?/em>:
對(duì)于一個(gè)包含N個(gè)非負(fù)整數(shù)的數(shù)組A[1..n]，如果有i < j，且A[ i ]>A[ j ]，則稱(A[ i] ,A[ j] )為數(shù)組A中的一個(gè)逆序?qū)Α?/p>
比如
上面這個(gè)數(shù)組就有6個(gè)逆序?qū)Α?br> 這里有個(gè)定理: 插入排序需要的swap操作和數(shù)組中逆序?qū)€(gè)數(shù)是一樣的，需要compare操作的個(gè)數(shù)大于等于逆序?qū)?shù)目,但小于等于逆序?qū)由蠑?shù)組大小減1。
