在這篇文章中讳苦，你將看到最容易理解的一種排序方法：直接插入排序。
請(qǐng)保證你有連續(xù)的20分鐘來看這個(gè)算法批狐，如果你用2分鐘就看明白了扇售，好吧，你一定是超人嚣艇。
首先來描述下直接插入排序的算法承冰，我們以升序?yàn)槔?/p>
數(shù)據(jù)準(zhǔn)備：一個(gè)無序的整形數(shù)組： {5, 8, 2, 7, 11, 20, 9, 1}
算法介紹：
-
當(dāng)某個(gè)數(shù)組中只有一個(gè)元素的時(shí)候，我們認(rèn)為此數(shù)組是有序的食零。
比如：{5}困乒，他只有一個(gè)元素，那他就是有序的贰谣，ok娜搂？
從需要排序的數(shù)組的第二個(gè)元素開始迁霎，我們將對(duì)他進(jìn)行插入排序；
在上面的數(shù)組中第二個(gè)元素是 8 對(duì)吧百宇？
真正的排序馬上開始考廉；
-
我們拿到了 8， 同他前面所有的有序的子數(shù)組的每個(gè)元素進(jìn)行比較携御，
對(duì)于我們的例子來講昌粤，8 前面的“有序的子數(shù)組”就是 {5}，
那么 8 會(huì)跟 5 去比較啄刹。
比較的結(jié)果是 8 > 5涮坐，則不做任何處理；
8 接下來跟子數(shù)組的其他元素比較誓军，我們發(fā)現(xiàn)已經(jīng)比較完了袱讹，
那么ok，對(duì) 8 這個(gè)元素谭企，因?yàn)樗?相比，本身就是升序评肆，所以我們沒有做任何移動(dòng)债查；
-
到此，你會(huì)不會(huì)說我在說廢話瓜挽？沒關(guān)系盹廷，好戲馬上開始了。
8 的下一個(gè)元素是2久橙。
2 也會(huì)跟他前面的“有序的子數(shù)組” 進(jìn)行比較俄占，此時(shí)這個(gè)子數(shù)組是 {5， 8}淆衷，
所以這次需要跟兩個(gè)元素進(jìn)行比較缸榄。
那么先跟誰比呢？答案是先跟 8 比較祝拯，具體過程如下,
1) 2 > 8 嗎甚带？不大于，好的佳头，2 和 8 交換位置鹰贵。
啊康嘉？不是吧碉输？你不知道交換位置是怎么回事嗎？那我先說下這個(gè)吧:
比如 你有兩個(gè)瓶子亭珍，一個(gè)瓶子裝著醋敷钾，一個(gè)瓶子裝著醬油枝哄，現(xiàn)在你突然發(fā)神經(jīng)，想要把這倆瓶子換換個(gè)闰非。
怎么辦呢膘格？好辦，你去找一個(gè)你喝過的雪碧的瓶子财松，你會(huì)這么做：
把醋倒到雪碧瓶子瘪贱，那么醋瓶子就空了；
把醬油倒到醋瓶子辆毡，那么醬油瓶子就空了菜秦，此時(shí)醋瓶子里面裝了醬油哈；
把雪碧瓶子的醋倒到醬油瓶子里舶掖，那么雪碧瓶子空了球昨，此時(shí)醬油瓶子就裝了醋了。
則交換后數(shù)組看起來是這樣：
{5, 2, 8, ...} 眨攘，...代表剩下的未經(jīng)排序的元素主慰，因?yàn)闀簳r(shí)還不涉及他們，故省略鲫售；
2) 那么接下來共螺，2 和 5 比較，2 > 5 嗎情竹？不大于藐不，同理，2 和 5交換秦效，交換后變成這樣：
{2, 5, 8, ...}
3) 接下來還要比較嗎雏蛮？不用了，因?yàn)閧5, 8}這兩個(gè)元素已經(jīng)比較完了阱州。
好的挑秉，到此為止，我們看到的數(shù)組是這樣的：
{2, 5, 8, 7, 11, 20, 9, 1}
下面的問題就以此類推了苔货，很簡(jiǎn)單衷模，我們繼續(xù)啰嗦下下一個(gè)元素： 7 的排序過程：
7的前面的“有序的子數(shù)組”是{2, 5, 8}，因此蒲赂，他需要比較3次阱冶。
同理，從后往前做比較滥嘴，先跟8比：
1) 7 > 8 嗎木蹬？不大于，好的交換，則為{2, 5, 7, 8};
2) 7 > 5 嗎镊叁？是的尘颓，大于，好的晦譬，到此疤苹，我們可以停下來了；
3) 呃敛腌？你是說break嗎卧土？是的，就是break像樊，為什么可以break呢尤莺？因?yàn)槲覀冎来容^的子數(shù)組是有序的，
所以呢生棍，5前面的數(shù)字一定比5胁（當(dāng)然也可能等于，本例中沒有出現(xiàn)這個(gè)情況而已涂滴，不管怎么樣友酱，他一定是小于等于5的）
那么，我們可以百分百確定柔纵，7不會(huì)出現(xiàn)在5的前面缔杉，所以就不跟前面的數(shù)字進(jìn)行比較了。
我相信首量，如果你按照上面的自己一步步讀下來壮吩，一定可以把最初的數(shù)組排序成功进苍。
算法講完了加缘，那么我們來了解下他的時(shí)間復(fù)雜度是多少呢？
時(shí)間復(fù)雜度觉啊，是O(n^2)拣宏；這個(gè)時(shí)間復(fù)雜度我說不太清了，大家還是百度或谷歌吧杠人。
空間復(fù)雜度勋乾，就是O(1)吧，因?yàn)槲覀冎挥昧艘粋€(gè)臨時(shí)空間嗡善。
說到最后還是要用代碼來實(shí)現(xiàn)辑莫，這是我的Java實(shí)現(xiàn)：
static void insertSort(int[] array) {
int tmp = 0;
for (int i = 1; i < array.length; i++) {
tmp = array[i];
for (int j = i - 1; j >= 0; j--) {
if (array[j] > tmp) {
array[j+1] = array[j];
array[j] = tmp;
}
else {
break;
} // End of else
} // End of for (j)
} // End of for (i)
} // End of insertSort(..)
能看懂嗎？
簡(jiǎn)單描述下：
第三行的for循環(huán)從 1 開始罩引，咦各吨？為什么是 1 呢? 數(shù)組下標(biāo)不是從 0 開始嗎？
對(duì)袁铐，你說的是對(duì)的揭蜒，數(shù)組下標(biāo)是從 0 開始横浑，但對(duì)于我們的算法來講，
從 0 開始屉更，0 號(hào)元素前面是沒有任何 “有序的子數(shù)組” 的徙融，故我們從 1 開始，
那么 1 號(hào)元素前面的“有序的子數(shù)組”就是 {0號(hào)元素}瑰谜。
接下來欺冀，我們?cè)诘谒男校?i 號(hào)元素的值保存到 tmp 了似舵；
下面第6行又是一個(gè)循環(huán)脚猾，在這個(gè)循環(huán)中，我們從 i - 1 開始砚哗，比較 i - 1 元素的值與 tmp 之間的關(guān)系龙助。
如果要比較的元素 大于 tmp 了，那么就把他們換換位置蛛芥；
否則呢提鸟，就break。
這里break的原因在上面已經(jīng)講到了仅淑。
此講結(jié)束称勋，下一講準(zhǔn)備是來說說 直接插入排序的改進(jìn)算法：希爾排序。
不知道你看完并理解整個(gè)過程花了多長(zhǎng)時(shí)間呢涯竟？20分鐘夠嗎赡鲜？如果不夠，原因是什么庐船，是我寫的不夠詳細(xì)看不明白银酬？還是我寫的太多了，光讀文字就花了半小時(shí)呢 嘿嘿筐钟。
Anyway, hope this helps.
