好程序員Java培訓分享Java常見排序算法之插入排序

好程序員Java培訓分享Java常見排序算法之插入排序，之前我們說過排序是算法中的一部分。所以我們學習排序也是算法的入門，為了能讓大家感受到排序是算法的一部分，我舉個例子證明一下：比如麻 將游戲，發完牌之后需要對手上的牌進行排序，大家想想，麻 將排序如何排呢？它有什么特點呢？而且在摸牌打 牌的過程中，我們要不斷的排序，如何排序呢？選擇什么排序算法最快呢？

以上這種情況我們就可以分析選擇哪種排序算法更高效。比如下圖已經有一副固定順序的牌了：

此時輪到我們摸牌，摸到的牌如下：

此時，要將這個“三同”放到上面的一副牌中，就存在如下規律：

1、正?！?同”應該放到“2同”和”4同“中間。

2、跟其他花色的牌沒有關系，甚至跟”5同“也沒有關系。只需要把”3同“放到”2同“和”4同“中間就行。至于”2同”和”4同”在哪里不要緊。

我們前面學習了選擇排序，如果使用選擇排序對上面這副牌進行排序是否合適呢？顯然是不合適的，因為選擇排序必須從“七萬”開始比較，選擇最小牌跟頭一張牌交換位置，依次類推。但是此處麻 將牌的“3同”跟”七萬“沒有關系，不需要影響”7萬“。所以使用選擇排序不合適，因為時間負責度很高；此處使用插入排序會更好，什么是插入排序呢？就是本節需要介紹的內容。

二、插入排序

插入排序屬于簡單排序的一種，通常指的簡單排序只是因為其算法思路比較容易理解，不代表其用途很簡單。為了讓大家掌握插入排序，我們先看看插入排序的原理。

2.1、插入排序的原理

首先有一個待排序的數組如下：

以上數組中只有一個數字0的順序需要排列，其他數字的順序都是對的。這種數組使用插入排序的效率更高，下面介紹此數組使用插入排序的流程。

1、先比較1和2，如果2比1小則交換位置。否則不交換位置。此數組不需要交換位置。

2、再比較2和3，如果3比2小，則交換位置。但是實際3比2大所以不交換位置，保持不變。

3、同理，3和4比較也不需要交換位置，保持不變

4、接來下，4和0比較，0小于4，所以交換位置

交換位置之后的數組如下：

5、因為3的鄰居發生變化，所以3和0再次比較，0比3小，交換位置，交換之后的數組如下：

6、依次類推，0分別和2交換位置之后的數組如下：

0再和1交換位置的數組如下：

這樣一個數組的順序就對了，但是循環還沒有完成，因為我們剛才僅僅循環到數字4這個位置，數字5還沒有比較。

7、最后比較4和5，如果5比4小則交換位置，但是5比4大，所以位置不變。數組循環完畢，最終排序如下：

上面就是插入排序的原理。

2.2、插入排序和選擇排序的區別

比如就上面這個例子而言，插入排序是將0從索引為4的位置移動到索引3、2、1、0，最終才算結束。而選擇排序是找到最小的值0，直接跟1進行交換，0到1的位置，1到0的位置。大家可以翻看前面關于選擇排序的介紹。

三、插入排序的代碼實現

以下是java代碼的實現：

/**

* 插入排序

*/

public static void algorithm5(){

//原始數組

int[] array={1,2,3,4,0,5};

//數組的長度

int length=array.length;

//對數組進行遍歷 for (int i = 0; i < length; i++) {

//第二個循環僅僅是將當前數據跟自己左邊的數字進行比較，如果小于左邊數字則交換位置，否則位置不變。

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;

}

}

//將排好序的數組打印輸出

for (int i = 0; i < length; i++) {

System.out.print(array[i]+"，");

}

}

以上是插入排序的java代碼實現，代碼中的第二個for循環是重點，第二個for循環是只比較當前數據左邊的值，如果比左邊的值小則交換位置，否則位置不變。

3.1 插入排序的時間復雜度

插入排序的時間復雜度有兩種：

1、當數組本身是有序的，比如{1，2，3，4，5}，則采用插入排序的時間復雜度是O(n)。原因：如果數組本身是有序，插入排序需要每兩個挨著的數字進行比較一次，總共比較N-1次，所以時間復雜度是O(n)。

2、當數組是無序的，最壞的情況下需要比較(n^2)/2次，所以時間復雜度是O(n^2)。

四、總結

根據插入排序的時間復雜度來看，插入排序適合如下類型的數組：

1、數組中的每一個元素距離其最終的位置都不遠。比如{1,0,2,3,4,5}，這個數組中0最終位置應該是頭1個位置，0此時的位置距離1位置不遠。

2、一個有序的大數組中融入一個小數組。比如有序大數組{1,2,3,4,5,6}，融入一個小數組{0,1}。

3、數組中只有幾個元素的位置不正確。

上述這三種情況的數組適合使用插入排序算法。打過麻 將的同學想想，打麻 將過程中不停地摸牌、打 牌、整理牌的過程是不是就是一次插入排序呢！

排序是算法的基礎，排序的用途很多?？赐瓯竟潈热葜?，大家不妨自己動手寫個代碼將無需的撲 克 牌進行排序，看更適合哪種排序算法。