插入排序的演算法特別好理解，與我們的日常生活緊密相連，或者說它來源於對日常生活的感悟。插入排序也是用得最多的一種排序方法。但原因不是因為它好理解，而是因為在實際程式設計中資料往往都是已經排好序的，所以一般都是往排好序的序列中按順序插入一個資料。此時用插入排序就會特別快。
那麼插入排序到底是怎樣的呢？比如有十個人從左往右無序地排列，現在要你按身高從低到高排列，你會怎麼排？
首先第二個人和第一個人比，如果第二個人比第一個人矮，那麼它們互換位置，否則不動，此時前兩個人的順序就排好了；然後第三個人再與前兩個已經排好的比，怎麼比？第三個人先站出來，看看前面在哪個位置中自己比左邊的高比右邊的矮，然後就插進去，如果自己與前面的人相比是最高的，那麼就不動，此時前三個人的順序就排好了……就這樣一直往後比較。
那麼怎麼找比左邊高比右邊矮的那個位置呢？因為左邊都是已經排好序的，所以依次與左邊的比，直到遇到一個比他矮的，那麼那個位置就是比左邊高比右邊矮的位置。如果沒找到一個比他矮的那麼他就是最矮的，那麼他就排在最左邊。那麼是怎麼插入的呢？因為每個與左邊一個一個比較的那個人都是先站出來的，所以他的那個位置是空的。這時在找到比他矮的那個人之前，每比完一個，與他進行比較的那個人就往右挪一個位置，將空依次補上。直到找到比他矮的人，那時比他矮的那個人的前面就空出了一個位置，然後他就可以插進去。所以在程式中要先用一個變數儲存這個“站出來的”數。
下面來寫一個插入排序的演算法實現從小到大排序。
# include <stdio.h>
int main(void)
{
int i, j;
int temp; //用於儲存站出來的數
int a[] = {900, 2, 3, -58, 34, 76, 32, 43, 56, -70, 35, -234, 532, 543, 2500};
int n = sizeof(a) / sizeof(a[0]); //存放陣列a中元素的個數
for (i=1; i<n; i++) /*i從1開始, 即從第二個人開始比, 每回圈一次比較一輪*/
{
temp = a[i];
j = i - 1; //與它前一個數比較
while ((j>=0) && (a[j]>temp)) /*與左邊所有人都比完了或找到一個比他矮的為止*/
{
a[j+1] = a[j]; //與他比完之後比它高的向右挪一個位置
--j; /*最經典的地方, 每次減1, 再與前一個比較, 直到與左邊所有的都比完或比到有一個數小於等於它為止, while迴圈退出, 此時左邊形成一個新的有序序列*/
}
if (j != i-1) /*這句也很經典, j != i-1說明執行過上面的while, 並且找到位置了, 那麼就插進去；如果j = i-1, 則說明沒有執行過while, 說明他和左邊的相比是最高的, 則不用換位置*/
{
a[j+1] = temp; /*之所以j要加1是因為while在退出之前又執行了一次--j*/
}
}
for (i=0; i <15; ++i)
{
printf("%dx20", a[i]);
}
printf("n");
return 0;
}
輸出結果是：
-234 -70 -58 2 3 32 34 35 43 56 76 532 543 900 2500
總結
氣泡排序是從左往右比，而插入排序是從右往左比，但也是一輪一輪地比較。原序列中從左邊第二個數開始，每輪比較一個數。每個數依次與它左邊的所有數相比較，左邊的都是已經排好的序列，該數與這些排好的序列逐個比較，然後插入其中，形成一個新的排好的序列。
從程式中也可以看出，如果是將一個資料插入已經排好的序列中，使用插入排序無疑是最好的選擇。此時計算量只不過是氣泡排序的一輪比較而已。比如向序列“1 3 4 5 7 9 11 13 20”插入一個 6，用插入排序就非常簡單了。程式如下：
# include <stdio.h>
int main(void)
{
int a[10] = {1, 3, 4, 5, 7, 9, 11, 13, 20};
int i = 8; //儲存陣列有效資料的最大下標
int data = 0; //儲存要插進來的數
printf("請輸入要插進來的數:");
scanf("%d", &data);
while ((i>=0) && (a[i]>data)) /*找到data應該插入的位置, 並把那個位置空出來*/
{
a[i+1] = a[i];
--i;
}
a[i+1] = data; //將data插入那個位置
for (i=0; i<10; ++i)
{
printf("%dx20", a[i]);
}
printf("n");
return 0;
}
輸出結果是：
請輸入要插進來的數:6
1 3 4 5 6 7 9 11 13 20
需要注意的是，前面的程式中陣列的長度都沒有手動指定，而上面這個程式是手動指定了陣列的長度為 10。這是為什麼？
這是因為，如果不手動給定還是寫成“int a[]={1，3，4，5，7，9，11，13，20};”這種形式的話，那麼系統就會根據初始化資料的個數認為該陣列的長度為 9。但是現在要往該陣列中插入一個元素，那麼陣列的長度至少是 10，不然插入資料後，陣列的最後一個元素就會向後覆蓋一個 int 型的未分配給它的記憶體空間。
所以為了避免這種情況的發生，就只能手動指定陣列的長度。但是這樣的話就意味著不能再通過 sizeof(a)/sizeof(a[0]) 來計算陣列中存放的有意義的資料的長度，因為 sizeof(a)/sizeof(a[0]) 計算的是陣列的總長度。這也就意味著只能通過手動的方式指定陣列中存放有意義的資料的元素的最大下標 i。
綜上所述，這種情況就需要程式設計師自己手動維護陣列的長度。這也從某一方面體現出了陣列的缺陷，即它無法動態地擴充長度。動態陣列和連結串列就不存在陣列的這個缺陷，這兩種結構後續會講。