何謂‘插入排序’玄组？ 其概念如是說：每次將一個(gè)待排序的記錄整以，按其關(guān)鍵字大小插入到前面已經(jīng)排序好的序列中胧辽，直到全部記錄插入完成為止。
概念的東西總是有些抽象公黑，也可稱其為基本思想邑商。上述插入排序的概念同樣也可說是插入排序的基本思想。抽象的東西理解起來總是有些困難凡蚜，因此這里需要的是將抽象的概念具體化人断。
我們不妨將其轉(zhuǎn)換成整隊(duì)問題：開始會(huì)有兩隊(duì)，其中一隊(duì)是按從低到高的順序排列的朝蜘，將其命名為A隊(duì)恶迈。另一隊(duì)是無序的，將其命名為B隊(duì)谱醇。如下圖：
現(xiàn)在把B隊(duì)的第一個(gè)人（不妨稱其為jack）放到A隊(duì)中暇仲，并且保持A隊(duì)依然是有序的步做，為了保持A隊(duì)依然有序就需要在A隊(duì)中找一個(gè)適當(dāng)?shù)奈恢媒ojack，這個(gè)位置前面的人要比jack矮奈附，后面的人要比jack高∪龋現(xiàn)在就可以讓jack站到這個(gè)位置上面，此時(shí)A中依然有序桅狠。
然后再把B隊(duì)的第二個(gè)人（稱其為tom）放到A隊(duì)讼载，方式和jack相同，要保證A隊(duì)依然有序中跌。
依次類推直到B隊(duì)的人全部站到A隊(duì)當(dāng)中咨堤。到此為止，兩隊(duì)合成了一隊(duì)漩符，而且這一隊(duì)是有序的一喘。
看到這對(duì)插入排序應(yīng)該有一個(gè)比較清晰的認(rèn)識(shí)了。但是這里還存在著一個(gè)疑問嗜暴，排序問題是對(duì)一個(gè)隊(duì)列進(jìn)行排序凸克，何來的兩隊(duì)呢。我們不妨再來轉(zhuǎn)換一下闷沥，起初的時(shí)候A萎战、B兩隊(duì)站在同一列，并且A隊(duì)整體在B隊(duì)前面舆逃，并且A隊(duì)是一個(gè)人蚂维。對(duì)于一個(gè)人的隊(duì)列肯定是有序的。
然后再向代碼方面靠近一下路狮，不妨將A虫啥、B兩隊(duì)映射成數(shù)組。有這樣一個(gè)數(shù)組
其中 3 就表示 剛開始的A隊(duì) 奄妨，5涂籽、2…. 表示剛開始的B隊(duì)。而5 就是 Jack砸抛， 2 就是Tom评雌。
我當(dāng)時(shí)學(xué)習(xí)插入排序的時(shí)候就是按照這個(gè)思路來理解的。到這里我對(duì)插入排序的思想基本上已經(jīng)完全掌握了锰悼。
思想的東西轉(zhuǎn)換成代碼柳骄，不同的方式也會(huì)產(chǎn)生不同的‘派系’。好比《春秋經(jīng)》讀起來總是有些難懂箕般，這時(shí)就有人出來為春秋作傳耐薯，不同的人作出來的傳也是不同的，有《左傳》，有《公羊傳》曲初，有《谷梁傳》 体谒。 雖然有所不同，但是整體都是傳承的《春秋》的思想 臼婆。
現(xiàn)在回到我們的插入排序上來抒痒，既然思想的東西都已經(jīng)明了了，無非就是實(shí)現(xiàn)方式的差別颁褂。關(guān)鍵的地方還是在于A隊(duì)故响，當(dāng)在A隊(duì)為B隊(duì)的人查找適當(dāng)位置的時(shí)候，查找的方式有很多種颁独。
1彩届、每次開始從頭遍歷查找位置 稱其為 直接插入排序
2、用二分法查找位置 稱其為 二分插入排序/折半插入排序
以上兩種方式 都是在一個(gè)隊(duì)列中查找和移動(dòng)元素誓酒，主要時(shí)間花費(fèi)在查找和移動(dòng)兩個(gè)方面樟蠕。
還有第三種方式就是借助額外的隊(duì)列，來做一個(gè)映射靠柑，這樣可以省去了移動(dòng)所花費(fèi)的時(shí)間寨辩。
就是用空間換時(shí)間的做法，這種方式被稱為：
3歼冰、表插入排序
這里面又涉及到了兩個(gè)概念 時(shí)間復(fù)雜度 和 空間復(fù)雜度 在本篇不對(duì)這兩個(gè)概念進(jìn)行說明靡狞，我會(huì)在其他博文中來闡述一下我是如何理解這兩個(gè)概念的。
由于篇幅問題本章不涉及到任何代碼隔嫡，僅僅分享一下自己對(duì)插入排序的理解耍攘。后續(xù)在其他的文章中為大家奉上本人寫的每一種方法的實(shí)現(xiàn)代碼。
