java 實現(xiàn)排序算法系列
這是 Java 實現(xiàn)排序算法的第三篇文章——插入排序算法删铃。插入排序可以說成是「一類」簡單的排序算法，因為插入排序可以有變種火欧，比如二分查找插入排序算法，本文講述的是直接插入排序。
如文中出現(xiàn)錯誤响鹃，請在公眾號「ikook」聊天窗口留言，十分感謝案训。
插入排序
插入排序「Insertion Sort」是一種簡單直觀的排序算法买置。它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)强霎，在已排序序列中從后向前掃描忿项，找到相應位置并插入。
來看一下插入排序算法的思路：
- 將需排序的數(shù)據(jù)分成已排序和未排序兩部分城舞，從第一個元素開始轩触，并將該元素看做已排序。
- 取得下一個元素家夺，即第二個元素脱柱，在已排序的序列中由后向前掃描，找出合適的位置將該元素插入拉馋。
- 重復上述步驟褐捻，直到最后一個元素被插入到已排序序列中。
- 排序完成椅邓。
使用插入排序為一列數(shù)字進行排序的過程示意圖（來自維基百科）：
<center>
</center>
插入排序算法示意圖（來自維基百科）：
<center>
</center>
代碼實現(xiàn)
從上面可以看到柠逞，算法思路非常簡單，但是代碼就不那么簡單易寫了景馁。算法本身是沒有問題的板壮，之所以不易寫我覺得是由于編程語言的問題。這里我們使用 Java 來實現(xiàn)合住，那就拿 Java 來講绰精。
在上述思路中我們可以提出幾個問題撒璧，先來看下。首先笨使，我們該如何判斷合適的位置卿樱？邊界條件該怎么處理？在數(shù)組中插入元素硫椰，必然會移動數(shù)據(jù)繁调，如何控制數(shù)據(jù)的移動？
為了解決這些問題靶草，我們可以在算法思路的第二步做手腳蹄胰，將第二步細化。我們不在已排序的序列起始位置開始比較奕翔，從已排序序列的尾部開始逆序比較裕寨，只要比待插入的數(shù)據(jù)大，那就向后移動派继，直到不大于該數(shù)據(jù)宾袜，此時空出來的位置就放入待插入數(shù)據(jù)。
上代碼：
private static void insertionSort(int[] arr){
for (int i=1; i<arr.length; i++){
int value = arr[i];
int position=i;
while (position>0 && arr[position-1]>value){
arr[position] = arr[position-1];
position--;
}
arr[position] = value;
}
}
如果在代碼的理解上遇到困難驾窟，可以利用 IDE 的調(diào)試功能來學習试和。如下圖（IntelliJ IDEA）：
<center>
</center>
算法復雜度
從上述內(nèi)容容易看出，無論輸入的數(shù)據(jù)怎樣纫普，插入排序算法總會進行 n-1 次排序阅悍。
由于每個元素插入點的不確定性，該算法復雜度并不是一定的昨稼。假設我們要將 n 個元素的序列升序排序节视，這時存在最好情況和最壞情況。
最好情況就是假栓，序列已經(jīng)是升序排列了（即數(shù)據(jù)本身的順序和我們需要的順序相同）寻行。此時，需要進行的比較操作需（n-1）次即可匾荆，時間復雜度為 O(n)拌蜘。
最壞情況很顯然，序列為逆序排列時牙丽，即降序排序時為最壞简卧。此時，需要進行的比較共有 1/2n(n-1) 次烤芦，時間復雜度為 O(n^2)举娩。
平均來說，插入排序算法復雜度為 O(n^2)。插入排序的賦值操作是比較操作的次數(shù)加上（n-1）次铜涉。
空間復雜度智玻，插入排序所有的數(shù)據(jù)移動均在內(nèi)部進行，唯一的開銷是我們使用了一個臨時變量芙代，則空間復雜度為 O(1)吊奢。
插入排序算法分析
算法穩(wěn)定性：
拿本文中的例子來講，只需要找到需插入元素的位置即可纹烹，并不需要交換页滚，則直接插入排序是穩(wěn)定排序算法。
適用場景：
從算法復雜度可以看出滔韵，該排序算法不適合數(shù)據(jù)較大的情況，數(shù)量級小于千時掌实，插入排序是一個不錯的選擇陪蜻。在 STL 的 sort 算法和 stdlib 的 qsort 算法中，都將插入排序作為快速排序的補充贱鼻，用于少量數(shù)據(jù)的排序宴卖。
其他
關于插入排序算法的變種大家有興趣的自己 Google 一下，本文只講述了基本的直接插入排序邻悬。插入排序的變種大概有這幾種：二分查找插入排序症昏、2 - 路插入排序、表插入排序父丰。二分查找插入排序有的文獻叫做折半插入排序肝谭，2 - 路插入排序和表插入排序可以參考《數(shù)據(jù)結(jié)構(gòu)》（嚴蔚敏、吳偉民著）一書蛾扇。
完攘烛。
相關閱讀：
Java 實現(xiàn)「冒泡排序」
Java 實現(xiàn)「選擇排序」
PS：如果你覺得本文對你有一點幫助，點贊镀首、轉(zhuǎn)發(fā)坟漱，不勝感激。
