一、概述
上一節(jié)我們說過排序是算法中的一部分。所以我們學(xué)習(xí)排序也是算法的入門，為了能讓大家感受到排序是算法的一部分，我舉個(gè)例子證明一下：比如麻將游戲，發(fā)完牌之后需要對(duì)手上的牌進(jìn)行排序，大家想想，麻將排序如何排呢？它有什么特點(diǎn)呢？而且在摸牌打牌的過程中，我們要不斷的排序，如何排序呢？選擇什么排序算法最快呢？
以上這種情況我們就可以分析選擇哪種排序算法更高效。比如下圖已經(jīng)有一副固定順序的牌了：
此時(shí)輪到我們摸牌，摸到的牌如下：
此時(shí)，要將這個(gè)“三同”放到上面的一副牌中，就存在如下規(guī)律：
1、正?！?同”應(yīng)該放到“2同”和”4同“中間。
2、跟其他花色的牌沒有關(guān)系，甚至跟”5同“也沒有關(guān)系。只需要把”3同“放到”2同“和”4同“中間就行。至于”2同”和”4同”在哪里不要緊。
我們前面學(xué)習(xí)了選擇排序，如果使用選擇排序?qū)ι厦孢@副牌進(jìn)行排序是否合適呢？顯然是不合適的，因?yàn)檫x擇排序必須從“七萬”開始比較，選擇最小牌跟第一張牌交換位置，依次類推。但是此處麻將牌的“3同”跟”七萬“沒有關(guān)系，不需要影響”7萬“。所以使用選擇排序不合適，因?yàn)闀r(shí)間負(fù)責(zé)度很高；此處使用插入排序會(huì)更好，什么是插入排序呢？就是本節(jié)需要介紹的內(nèi)容。
二、插入排序
插入排序?qū)儆诤唵闻判虻囊环N，通常指的簡單排序只是因?yàn)槠渌惴ㄋ悸繁容^容易理解，不代表其用途很簡單。為了讓大家掌握插入排序，我們先看看插入排序的原理。
2.1、插入排序的原理
首先有一個(gè)待排序的數(shù)組如下：
以上數(shù)組中只有一個(gè)數(shù)字0的順序需要排列，其他數(shù)字的順序都是對(duì)的。這種數(shù)組使用插入排序的效率更高，下面介紹此數(shù)組使用插入排序的流程。
1、先比較1和2，如果2比1小則交換位置。否則不交換位置。此數(shù)組不需要交換位置。
2、再比較2和3，如果3比2小，則交換位置。但是實(shí)際3比2大所以不交換位置，保持不變。
3、同理，3和4比較也不需要交換位置，保持不變
4、接來下，4和0比較，0小于4，所以交換位置
交換位置之后的數(shù)組如下：
5、因?yàn)?的鄰居發(fā)生變化，所以3和0再次比較，0比3小，交換位置，交換之后的數(shù)組如下：
6、依次類推，0分別和2交換位置之后的數(shù)組如下：
0再和1交換位置的數(shù)組如下：
這樣一個(gè)數(shù)組的順序就對(duì)了，但是循環(huán)還沒有完成，因?yàn)槲覀儎偛艃H僅循環(huán)到數(shù)字4這個(gè)位置，數(shù)字5還沒有比較。
7、最后比較4和5，如果5比4小則交換位置，但是5比4大，所以位置不變。數(shù)組循環(huán)完畢，最終排序如下：
上面就是插入排序的原理。
2.2、插入排序和選擇排序的區(qū)別
比如就上面這個(gè)例子而言，插入排序是將0從索引為4的位置移動(dòng)到索引3、2、1、0，最終才算結(jié)束。而選擇排序是找到最小的值0，直接跟1進(jìn)行交換，0到1的位置，1到0的位置。大家可以翻看前面關(guān)于選擇排序的介紹。
三、插入排序的代碼實(shí)現(xiàn)
以下是java代碼的實(shí)現(xiàn)：
/** * 插入排序 */ public static void algorithm5(){ //原始數(shù)組 int[] array={1,2,3,4,0,5}; //數(shù)組的長度 int length=array.length; //對(duì)數(shù)組進(jìn)行遍歷 for (int i = 0; i < length; i++) { //第二個(gè)循環(huán)僅僅是將當(dāng)前數(shù)據(jù)跟自己左邊的數(shù)字進(jìn)行比較，如果小于左邊數(shù)字則交換位置，否則位置不變。 for (int j = i; j > 0 && array[j]<array[j-1]; j--) { int temp = 0; temp = array[j-1]; array[j-1]=array[j]; array[j]=temp; } } //將排好序的數(shù)組打印輸出 for (int i = 0; i < length; i++) { System.out.print(array[i]+"，"); } }
以上是插入排序的java代碼實(shí)現(xiàn)，代碼中的第二個(gè)for循環(huán)是重點(diǎn)，第二個(gè)for循環(huán)是只比較當(dāng)前數(shù)據(jù)左邊的值，如果比左邊的值小則交換位置，否則位置不變。
3.1 插入排序的時(shí)間復(fù)雜度
插入排序的時(shí)間復(fù)雜度有兩種：
1、當(dāng)數(shù)組本身是有序的，比如{1，2，3，4，5}，則采用插入排序的時(shí)間復(fù)雜度是O(n)。原因：如果數(shù)組本身是有序，插入排序需要每兩個(gè)挨著的數(shù)字進(jìn)行比較一次，總共比較N-1次，所以時(shí)間復(fù)雜度是O(n)。
2、當(dāng)數(shù)組是無序的，最壞的情況下需要比較(n^2)/2次，所以時(shí)間復(fù)雜度是O(n^2)。
四、總結(jié)
根據(jù)插入排序的時(shí)間復(fù)雜度來看，插入排序適合如下類型的數(shù)組：
1、數(shù)組中的每一個(gè)元素距離其最終的位置都不遠(yuǎn)。比如{1,0,2,3,4,5}，這個(gè)數(shù)組中0最終位置應(yīng)該是第一個(gè)位置，0此時(shí)的位置距離第一個(gè)位置不遠(yuǎn)。
2、一個(gè)有序的大數(shù)組中融入一個(gè)小數(shù)組。比如有序大數(shù)組{1,2,3,4,5,6}，融入一個(gè)小數(shù)組{0,1}。
3、數(shù)組中只有幾個(gè)元素的位置不正確。
上述這三種情況的數(shù)組適合使用插入排序算法。打過麻將的同學(xué)想想，打麻將過程中不停地摸牌、打牌、整理牌的過程是不是就是一次插入排序呢！
排序是算法的基礎(chǔ)，排序的用途很多。看完本節(jié)內(nèi)容之后，大家不妨自己動(dòng)手寫個(gè)代碼將無需的撲克牌進(jìn)行排序，看更適合哪種排序算法。
轉(zhuǎn)自知乎： 一一哥寫JAVA
