相關術語
關鍵碼
關鍵碼是數據元素中某個數據項的值，用它可以标示一個數據元素。通常會用紀錄來标示數據元素，一個紀錄可以有若幹數據項組成。例如，一個學生的信息就是一條紀錄，它包括學号，姓名，性别等若幹數據項。主關鍵碼可以唯一的标示一個紀錄的關鍵碼，如學号。次關鍵碼是可以标示若幹記錄的關鍵字，如性别、姓名。
假設一個文件有n跳紀錄{}，對應的關鍵碼是{}，排序家就是将此n個紀錄按照關鍵碼的大小遞增（或遞減）的次序排列起來，使這些紀錄由無序變為有序的一種操作。排序後的序列若為{}時，其對應的關鍵碼值滿足{}或{}。
若在待排序的紀錄中，存在兩個或兩個以上的關鍵碼值相等的紀錄，經排序後這些記錄的相對次序仍然保持不變，則稱相應的排序方法是穩定的方法，否則是不穩定的方法。
内部排序和外部排序
根據排序過程中涉及的存儲器不同，可以講排序方法分為兩大類：一類是内部排序，指的是待排序的幾率存放在計算機随機存儲器中進行的排序過程；另一類的外部排序，指的是排序中要對外存儲器進行訪問的排序過程。
内部排序是排序的基礎，在内部排序中，根據排序過程中所依據的原則可以将它們分為5類：插入排序、交換排序、選擇排序、歸并排序和基數排序；根據排序過程的時間複雜度來分，可以分為三類：簡單排序、先進排序、基數排序。
評價排序算法優劣的标準主要是兩條：一是算法的運算量，這主要是通過記錄的比較次數和移動次數來反應；另一個是執行算法所需要的附加存儲單元的的多少。
分類
包括：直接插入排序，二分插入排序（又稱折半插入排序），鍊表插入排序，希爾排序（又稱縮小增量排序）。屬于穩定排序的一種（通俗地講，就是兩個相等的數不會交換位置）。
直接插入排序
直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的紀錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的紀錄插入完為止，得到一個新的有序序列。
例如,已知待排序的一組紀錄是：
60,71,49,11,24,3,66
假設在排序過程中，前3個紀錄已按關鍵碼值遞增的次序重新排列，構成一個有序序列：
49,60,71
将待排序紀錄中的第4個紀錄（即11）插入上述有序序列，以得到一個新的含4個紀錄的有序序列。首先，應找到11的插入位置，再進行插入。可以講11放入數組的第一個單元r中，這個單元稱為監視哨，然後從71起從右到左查找，11小于71，将71右移一個位置，11小于60，又将60右移一個位置，11小于49，又再将49右移一個位置，這時再将11與r的值比較，11≥r，它的插入位置就是r。假設11大于第一個值r。它的插入位置應該在r和r之間，由于60已經右移了，留出來的位置正好留給11.後面的紀錄依照同樣的方法逐個插入到該有序序列中。若紀錄數n,續進行n-1趟排序，才能完成。
直接插入排序的算法思路：
（1）設置監視哨r，将待插入紀錄的值賦值給r；
（2）設置開始查找的位置j；
（3）在數組中進行搜索，搜索中将第j個紀錄後移，直至r.key≥r[j].key為止；
（4）将r插入r[j+1]的位置上。
直接插入排序算法：
public void zjinsert (Redtype r[],int n)
{
int I,j;
Redtype temp;
for (i=1;i
{
temp = r[i];
j=i-1;
while (j>-1 &&temp.key
{
r[j+1]=r[j];
j--;
}
r[j+1]=temp;
}
}
折半插入排序（二分插入排序）
将直接插入排序中尋找A[i]的插入位置的方法改為采用折半比較，即可得到折半插入排序算法。在處理A[i]時，A……A[i-1]已經按關鍵碼值排好序。所謂折半比較，就是在插入A[i]時，取A[i-1/2]的關鍵碼值與A[i]的關鍵碼值進行比較，如果A[i]的關鍵碼值小于A[i-1/2]的關鍵碼值，則說明A[i]隻能插入A到A[i-1/2]之間，故可以在A到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）确定位置之後，将整個序列後移，并将元素插入到相應位置。
希爾排序法
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組内，并對每一組内的記錄進行排序。然後，取，重複上述分組和排序的工作。當到達=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};
描述
一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下：
⒈從第一個元素開始，該元素可以認為已經被排序
⒉取出下一個元素，在已經排序的元素序列中從後向前掃描
⒊如果該元素（已排序）大于新元素，将該元素移到下一位置
⒋重複步驟3，直到找到已排序的元素小于或者等于新元素的位置
⒌将新元素插入到下一位置中
⒍重複步驟2~5
如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數目。該算法可以認為是插入排序的一個變種，稱為二分查找排序。
實現
僞代碼
INSERTION-SORT( )
1 for 2 tolength[ ]
2 do = [ ]
3 //Insert [ ] into the sorted sequence [1.. -1].
4 = -1
5 while >0 and [ ] >
6 do [ +1] = [ ]
7 = -1
8 [ +1] =
C語言
示例代碼為C語言，輸入參數中，需要排序的數組為array[ ]，起始索引為first（數組有序部分最後一個的下标，或者直接标 0），終止索引為last（數組元素的最後一個的下标）。示例代碼的函數采用insert-place排序，調用完成後，array[]中從first到last處于升序排列。
這個更好：
c++版本
PHP版本
Java版本
運行軟件：eclipse
C#版本
Pascal版本
procedure insertsort(var R:filetype);
//對R[1..N]按遞增序進行插入排序，R是監視哨
begin
for I := 2 To n do //依次插入R,...,R[n]
begin
R:=R[I];j:=l-1;
while R < R[J] Do //查找R[I]的插入位置
begin
R[j+1]:=R[j]; //将大于R[I]的元素後移
j:=j-1;
end;
R[j+1]:=R;//插入R[I]
end;
end;//InsertSort
(運行軟件：Free Pascal IDE 2.6.4)
Ruby版本
Scala版本
算法複雜度
如果目标是把n個元素的序列升序排列，那麼采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需（n-1）次即可。最壞情況就是，序列是降序排列，那麼此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數加上(n-1）次。平均來說插入排序算法的時間複雜度為O(n^2）。因而，插入排序不适合對于數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小于千，那麼插入排序還是一個不錯的選擇。
穩定性
插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列隻有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其後面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那麼插入元素把想插入的元素放在相等元素的後面。所以，相等元素的前後順序沒有改變，從原無序序列出去的順序就是排好序後的順序，所以插入排序是穩定的。
