什么是排序
這里是排序算法的第一篇笑跛，那么熬甚，我們先來回顧一下什么是排序逢渔？
顧名思義，排序就是把由一系列元素組成的列表按指定的規(guī)則排列乡括。
什么是插入排序肃廓？為什么要使用？
簡單的說诲泌，插入排序就是把無序的元素插入到有序的元素當(dāng)中盲赊。
插入排序的過程
關(guān)于這個(gè)，《算法導(dǎo)論》中舉了一個(gè)特為形象的例子敷扫，插入排序就如同你在打撲克時(shí)摸牌一樣哀蘑，手里的牌是有序的，而你剛摸得牌是是隨機(jī)的葵第，需要你插入到已經(jīng)排好序的撲克牌中绘迁，這就是插入排序。
YouTube有一個(gè)很好的視頻：https://www.youtube.com/watch?v=DFG-XuyPYUQ
偽代碼
for i ← 1 to length(A) - 1
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
end while
end for
C語言的實(shí)現(xiàn)
//插入排序
void insertSort(RecordList *L)
{
printf("開始插入排序...\n");
//1羹幸、初始時(shí)刻脊髓，第一個(gè)元素本來假設(shè)是有序的
//2、從第二個(gè)元素開始, 依次循環(huán)插入
//3栅受、可以將元素看成兩部分，已經(jīng)排好序的和尚未排序的恭朗，每次從尚未排好序的元素中取出元素和已經(jīng)排好序的比較屏镊，插入到指定位置
for (int i = 1; i < L->length; i++) {
int j = i;
while (j > 0 && (L->record[j-1].key) > (L->record[j].key)) {
int temp;
temp = L->record[j-1].key;
L->record[j-1].key = L->record[j].key;
L->record[j].key = temp;
--j;
}
}
printf("排序完成\n");
}
運(yùn)行結(jié)果：
正在插入數(shù)據(jù)7，其他信息0
插入后當(dāng)前長度：1
正在插入數(shù)據(jù)9痰腮，其他信息1
插入后當(dāng)前長度：2
正在插入數(shù)據(jù)3而芥，其他信息2
插入后當(dāng)前長度：3
正在插入數(shù)據(jù)8，其他信息3
插入后當(dāng)前長度：4
正在插入數(shù)據(jù)0膀值，其他信息4
插入后當(dāng)前長度：5
正在插入數(shù)據(jù)2棍丐，其他信息5
插入后當(dāng)前長度：6
正在插入數(shù)據(jù)4误辑，其他信息6
插入后當(dāng)前長度：7
正在插入數(shù)據(jù)8，其他信息7
插入后當(dāng)前長度：8
正在插入數(shù)據(jù)3歌逢，其他信息8
插入后當(dāng)前長度：9
正在插入數(shù)據(jù)9巾钉，其他信息9
插入后當(dāng)前長度：10
原始記錄表:
關(guān)鍵字 原始位置
7 0
9 1
3 2
8 3
0 4
2 5
4 6
8 7
3 8
9 9
開始插入排序...
排序完成
直接插入排序后的記錄表:
關(guān)鍵字 原始位置
0 0
2 1
3 2
3 3
4 4
7 5
8 6
8 7
9 8
9 9
詳見我的Github：（ https://github.com/terwer/data-structure/tree/master/sort/InsertionSort ），可以直接下載后用XCode打開運(yùn)行秘案。
時(shí)間復(fù)雜度分析
可以看出砰苍，一次循環(huán)就完成了排序，因此插入排序的時(shí)間復(fù)雜度為O(1)
插入排序的優(yōu)缺點(diǎn)總結(jié)
優(yōu)點(diǎn)：
1阱高、插入排序?qū)τ谛?shù)據(jù)集合很有效赚导，這個(gè)很好理解，因?yàn)樾枰闅vlength－1次赤惊，所以數(shù)據(jù)量太大肯定不太高效吼旧。
2、比大多數(shù)O((n^2))的算法（比如冒泡排序未舟、選擇排序）要高效圈暗。
3、自適應(yīng)排序处面，對于若干個(gè)已經(jīng)排好序并且不大于k的集合厂置，它的時(shí)間復(fù)雜度時(shí)是O(nk)
4、穩(wěn)定魂角。插入排序是穩(wěn)定的昵济，排序之后不會改變元素原來的相對順序。
5野揪、原地排序访忿。插入排序的時(shí)間復(fù)雜度為O(1)。
6斯稳、他是在線算法海铆。關(guān)于在線算法，StackOverflow有一個(gè)很好的解答：（ http://stackoverflow.com/questions/11496013/what-is-the-difference-between-an-on-line-and-off-line-algorithm ）挣惰。
