插入排序（Insertion sort）是一種簡單直觀且穩定的排序算法。如果有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入後此數據序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用於少量數據的排序，時間複雜度為O(n^2)。是穩定的排序方法。插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最後一個元素除外（讓數組多一個空間才有插入的位置），而第二部分就只包含這一個元素（即待插入元素）。在第一部分排序完成後，再將這個最後元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步將一個待排序的記錄，按其關鍵碼值的大小插入前面已經排序的檔案中適當位置上，直到全部插入完為止。
基本介紹
- 中文名：插入排序
- 外文名：Insertion sort
- 類型：排序方法
- 分類：直接插入排序，二分插入排序
相關術語,關鍵碼,內部排序和外部排序,分類,直接插入排序,折半插入排序（二分插入排序）,原理,設計步驟,描述,實現,偽代碼,C語言,PHP版本,Java版本,JavaScript版本,C#版本,Pascal版本,Ruby版本,Scala版本,python版本,算法複雜度,穩定性,
相關術語
關鍵碼
關鍵碼是數據元素中某個數據項的值，用它可以標示一個數據元素。通常會用記錄來標示數據元素，一個記錄可以有若干數據項組成。例如，一個學生的信息就是一條記錄，它包括學號，姓名，性別等若干數據項。主關鍵碼可以唯一的標示一個記錄的關鍵碼，如學號。次關鍵碼是可以標示若干記錄的關鍵字，如性別、姓名。
假設一個檔案有n條記錄{}，對應的關鍵碼是{}，排序家就是將此n個記錄按照關鍵碼的大小遞增（或遞減）的次序排列起來，使這些記錄由無序變為有序的一種操作。排序後的序列若為{}時，其對應的關鍵碼值滿足{}或{}。
若在待排序的記錄中，存在兩個或兩個以上的關鍵碼值相等的記錄，經排序後這些記錄的相對次序仍然保持不變，則稱相應的排序方法是穩定的方法，否則是不穩定的方法。
內部排序和外部排序
根據排序過程中涉及的存儲器不同，可以將排序方法分為兩大類：一類是內部排序，指的是待排序的幾率存放在計算機隨機存儲器中進行的排序過程；另一類的外部排序，指的是排序中要對外存儲器進行訪問的排序過程。
內部排序是排序的基礎，在內部排序中，根據排序過程中所依據的原則可以將它們分為5類：插入排序、交換排序、選擇排序、歸併排序和基數排序；根據排序過程的時間複雜度來分，可以分為三類：簡單排序、先進排序、基數排序。
評價排序算法優劣的標準主要是兩條：一是算法的運算量，這主要是通過記錄的比較次數和移動次數來反應；另一個是執行算法所需要的附加存儲單元的的多少。
分類
直接插入排序
直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。
例如,已知待排序的一組記錄是：
60,71,49,11,24,3,66
假設在排序過程中，前3個記錄已按關鍵碼值遞增的次序重新排列，構成一個有序序列：
49,60,71
將待排序記錄中的第4個記錄（即11）插入上述有序序列，以得到一個新的含4個記錄的有序序列。首先，應找到11的插入位置，再進行插入。可以將11放入數組的第一個單元r[0]中，這個單元稱為監視哨，然後從71起從右到左查找，11小於71，將71右移一個位置，11小於60，又將60右移一個位置，11小於49，又再將49右移一個位置，這時再將11與r[0]的值比較，11≥r[0]，它的插入位置就是r[1]。假設11大於第一個值r[1]。它的插入位置應該在r[1]和r[2]之間，由於60已經右移了，留出來的位置正好留給11.後面的記錄依照同樣的方法逐個插入到該有序序列中。若記錄數n,續進行n-1趟排序，才能完成。
直接插入排序的算法思路：
（1） 設定監視哨r[0]，將待插入記錄的值賦值給r[0]；
（2） 設定開始查找的位置j；
（3） 在數組中進行搜尋，搜尋中將第j個記錄後移，直至r[0].key≥r[j].key為止；
（4） 將r[0]插入r[j+1]的位置上。
直接插入排序算法：
public void zjinsert (Redtype r[],int n)
{
int I,j;
Redtype temp;
for (i=1;i<n;i++)
{
temp = r[i];
j=i-1;
while (j>-1 &&temp.key<r[j].key)
{
r[j+1]=r[j];
j--;
}
r[j+1]=temp;
}
}
折半插入排序（二分插入排序）
將直接插入排序中尋找A[i]的插入位置的方法改為採用折半比較，即可得到折半插入排序算法。在處理A[i]時，A[0]……A[i-1]已經按關鍵碼值排好序。所謂折半比較，就是在插入A[i]時，取A[i-1/2]的關鍵碼值與A[i]的關鍵碼值進行比較，如果A[i]的關鍵碼值小於A[i-1/2]的關鍵碼值，則說明A[i]只能插入A[0]到A[i-1/2]之間，故可以在A[0]到A[i-1/2-1]之間繼續使用折半比較；否則只能插入A[i-1/2]到A[i-1]之間，故可以在A[i-1/2+1]到A[i-1]之間繼續使用折半比較。如此擔負，直到最後能夠確定插入的位置為止。一般在A[k]和A[r]之間採用折半，其中間結點為A[k+r/2]，經過一次比較即可排除一半記錄，把可能插入的區間減小了一半，故稱為折半。執行折半插入排序的前提是檔案記錄必須按順序存儲。
折半插入排序的算法思想：
算法的基本過程：
（1）計算 0 ~ i-1 的中間點，用 i 索引處的元素與中間值進行比較，如果 i 索引處的元素大，說明要插入的這個元素應該在中間值和剛加入i索引之間，反之，就是在剛開始的位置 到中間值的位置，這樣很簡單的完成了折半；
（2）在相應的半個範圍裡面找插入的位置時，不斷的用（1）步驟縮小範圍，不停的折半，範圍依次縮小為 1/2 1/4 1/8 .......快速的確定出第 i 個元素要插在什麼地方；
（3）確定位置之後，將整個序列後移，並將元素插入到相應位置。
3 希爾排序法
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數，把待排序檔案中所有記錄分成個組，所有距離為的記錄分在同一組內，並對每一組內的記錄進行排序。然後，取，重複上述分組和排序的工作。當到達=1時，所有記錄在統一組內排好序。
各組內的排序通常採用直接插入法。由於開始時s的取值較大，每組內記錄數較少，所以排序比較快。隨著不斷增大，每組內的記錄數逐步增多，但由於已經按排好序，因此排序速度也比較快。
原理
將n個元素的數列分為已有序和無序兩個部分，如下所示：
插入排序過程示例
插入排序過程示例{{a1}，{a2，a3，a4，…，an}}
{{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}
…
{{a1(n-1），a2(n-1) ，…},{an(n-1)}}
每次處理就是將無序數列的第一個元素與有序數列的元素從後往前逐個進行比較，找出插入位置，將該元素插入到有序數列的合適位置中。
假設在一個無序的數組中，要將該數組中的數按插入排序的方法從小到大排序。假設啊a[]={3,5,2,1,4};插入排序的思想就是比大小，滿足條件交換位置，一開始會像冒泡排序一樣，但會比冒泡多一步就是交換後（a[i]=a[i+1]後）原位置（a[i]）會繼續和前面的數比較滿足條件交換，直到a[i+1]前面的數組是有序的。比如在第二次比較後數組變成a[]={2,3,5,1,4};
設計步驟
算法設計有很多方法。插入排序使用的是增量（incremental）方法；在排好子數組A[1..j-1]後，將A[j]插入，形成排好序的子數組A[1..j]；
步驟
⒈從有序數列和無序數列{a2,a3，…，an}開始進行排序；
⒉處理第i個元素時（i=2,3，…，n），數列{a1,a2，…，ai-1}是已有序的，而數列{ai,ai+1，…，an}是無序的。用ai與ai-1，a i-2，…，a1進行比較，找出合適的位置將ai插入；
⒊重複第二步，共進行n-i次插入處理，數列全部有序。
思路
假定這個數組的序是排好的，然後從頭往後，如果有數比當前外層元素的值大，則將這個數的位置往後挪，直到當前外層元素的值大於或等於它前面的位置為止.這具算法在排完前k個數之後，可以保證a[1…k]是局部有序的，保證了插入過程的正確性.
描述
一般來說，插入排序都採用in-place在數組上實現。具體算法描述如下：
⒈ 從第一個元素開始，該元素可以認為已經被排序
⒉ 取出下一個元素，在已經排序的元素序列中從後向前掃描
⒊ 如果該元素（已排序）大於新元素，將該元素移到下一位置
⒋ 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
⒌ 將新元素插入到下一位置中
⒍ 重複步驟2~5
實現
偽代碼
INSERTION-SORT(A)
1forj=2tolength[A]
2dokey=A[j]
3 //InsertA[j] into the sorted sequenceA[1..j-1].
4 i=j-1
5 whilei>0 andA[i] >key
6 doA[i+1] =A[i]
7 i=i-1
8 A[i+1] =key
C語言
示例代碼為C語言，輸入參數中，需要排序的數組為array[ ]，起始索引為first（數組有序部分最後一個的下標，或者直接標 0），終止索引為last（數組元素的最後一個的下標）。示例代碼的函式採用insert-place排序，調用完成後，array[]中從first到last處於升序排列。
void insertion_sort(int array[],int first,int last){ int i,j; int temp; for(i=first+1;i<last;i++) { temp=array[i]; j=i-1; //與已排序的數逐一比較，大於temp時，該數移後 while((j>=0)&&(array[j]>temp)) { array[j+1]=array[j]; j--; } //存在大於temp的數 if(j!=i-1) array[j+1]=temp; }}這個更好：
void insert_sort(int *array,unsigned int n){ int i,j; int temp; for(i=1;i<n;i++) { temp=*(array+i); for(j=i;j>0&&*(array+j-1)>temp;j--) { *(array+j)=*(array+j-1); } *(array+j)=temp; }}c++版本
#include<iterator>template<typename biIter>void insertion_sort (biIter begin,biIter end){ typedef typename std::iterator_traits<biIter>::value_type value_type; biIter bond=begin; std::advance(bond,1); for(;bond!=end;std::advance(bond,1)) { value_type key=*bond; biIter ins=bond; biIter pre=ins; std::advance(pre,-1); while(ins!=begin&&*pre>key) { *ins=*pre; std::advance(ins,-1); std::advance(pre,-1); } *ins=key; }}PHP版本
functioninsertSort($arr){for($i=1;$i<count($arr);$i++){$tmp=$arr[$i];$key=$i-1;while($key>=0&&$tmp<$arr[$key]){$arr[$key+1]=$arr[$key];$key--;}if(($key+1)!=$i)$arr[$key+1]=$tmp;}return$arr;}Java版本
/***插入排序*@paramarr*@return*/private static int[] insertSort(int[]arr){if(arr == null || arr.length < 2){ return arr;}for(inti=1;i<arr.length;i++){for(intj=i;j>0;j--){if(arr[j]<arr[j-1]){//TODO:int temp=arr[j];arr[j]=arr[j-1];arr[j-1]=temp;//}else{//接下來是無用功break;}}}return arr;}/***插入排序,上面的todo交換很頻繁,增加很多步驟*@paramarr*@return*/private static int[] insertSort(int[]arr){if(arr == null || arr.length < 2){ return arr;}for(inti=1;i<arr.length;i++){int temp = arr[i];int indx = 0;for(intj=i;j>0;j--){if(arr[j]<arr[j-1]){//TODO:arr[j] = arr[j-1];indx = j-1;}else{//接下來是無用功break;}arr[indx]=temp;}}return arr;}運行軟體：eclipse
JavaScript版本
//測試數組var arr = new Array(1, 3, 2, 8, 9, 1, 5);//插入排序function InsertionSort(arr) { if (arr == null || arr.length < 2) { return arr; } for (let i = 1; i < arr.length; i++) { for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } return arr;}//控制台輸出console.log(arr);InsertionSort(arr);console.log(arr);C#版本
classProgram{staticvoidMain(string[]args){InsertionSort();}///<summary>///插入排序法///</summary>privatestaticvoidInsertionSort(){Console.WriteLine("插入排序法");inttemp=0;int[]arr={23,44,66,76,98,11,3,9,7};Console.WriteLine("排序前的數組：");foreach(intiteminarr){Console.Write(item+",");}Console.WriteLine();varlength=arr.Length;for(inti=1;i<length;i++){for(intj=i;j>0;j--){if(arr[j]>arr[j-1]){temp=arr[j];arr[j]=arr[j-1];arr[j-1]=temp;}}//每次排序後數組PrintResult(arr);}Console.ReadKey();}///<summary>///列印結果///</summary>///<paramname="arr"></param>privatestaticvoidPrintResult(IEnumerable<int>arr){foreach(intiteminarr){Console.Write(item+",");}Console.WriteLine();}}Pascal版本
procedure insertsort(var R:filetype);
//對R[1..N]按遞增序進行插入排序，R[0]是監視哨
begin
for I := 2 To n do //依次插入R[2],...,R[n]
begin
R[0]:=R[I];j:=l-1;
while R[0] < R[J] Do //查找R[I]的插入位置
begin
R[j+1]:=R[j]; //將大於R[I]的元素後移
j:=j-1;
end;
R[j+1]:=R[0] ; //插入R[I]
end;
end; //InsertSort
(運行軟體：Free Pascal IDE 2.6.4)
Ruby版本
def insertion_sort(array) array.each_with_index do |element, index| next if index == 0 #第一個元素默認已排序 j = index - 1 while j >= 0 && array[j] > element array[j + 1] = array[j] j -= 1 end array[j + 1] = element end arrayend
Scala版本
definsertSort(ilist:Array[Int]){for(i<-1untililist.length){for(j<-(0untili).reverse){if(ilist(j+1)<ilist(j)){valtmp=ilist(j+1)ilist(j+1)=ilist(j)ilist(j)=tmp}}}}python版本
import randomRange = 100Length = 5list = random.sample(range(Range),Length) #在指定序列中隨機獲取指定長度片段print('before sort:',list)for i in range(1,Length): #默認第一個元素已經在有序序列中，從後面元素開始插入 for j in range(i,0,-1): #逆向遍歷比較，交換位置實現插入 if list[j] < list[j-1]: list[j],list[j-1] = list[j-1],list[j]print('after sort:',list)算法複雜度
如果目標是把n個元素的序列升序排列，那么採用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需（n-1）次即可。最壞情況就是，序列是降序排列，那么此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數加上 (n-1）次。平均來說插入排序算法的時間複雜度為O(n^2）。因而，插入排序不適合對於數據量比較大的排序套用。但是，如果需要排序的數據量很小，例如，量級小於千，那么插入排序還是一個不錯的選擇。
穩定性
插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其後面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的後面。所以，相等元素的前後順序沒有改變，從原無序序列出去的順序就是排好序後的順序，所以插入排序是穩定的。
