插入排序是把一個(gè)記錄插入到已排序的有序序列中，使整個(gè)序列在插入該記錄后仍然有序。插入排序中較簡(jiǎn)單的種方法是直接插入排序，其插入位置的確定方法是將待插入的記錄與有序區(qū)中的各記錄自右向左依次比較其關(guān)鍵字值的大小。本實(shí)例要求使用直接插入排序法將數(shù)字由小到大進(jìn)行排序。

實(shí)現(xiàn)過(guò)程：
(1) 自定義一個(gè)函數(shù)，實(shí)現(xiàn)直接插入排序，在本實(shí)例中，我們自定義該函數(shù)為 insort()。
(2) main() 函數(shù)為程序的入口函數(shù)。程序代碼如下：

#include <stdio.h>
int insort(int s[], int n)    /* 自定義函數(shù) insort()*/
{
    int i,j;
    for(i=2;i<=n;i++)    //數(shù)組下標(biāo)從2開(kāi)始，s[0]做監(jiān)視哨，s[1]一個(gè)數(shù)據(jù)無(wú)可比性
    {
        s[0]=s[i];    //給監(jiān)視哨陚值
        j=i-1;    //確定要比較元素的最右邊位黃
        while(s[0]<s[j])
        {
            s[j+1]=s[j];    //數(shù)據(jù)右移
            j--;    //產(chǎn)移向左邊一個(gè)未比較的數(shù)
        }
        s[j+1]=s[0];    //在確定的位置插入s[i]
    }
    return 0;
}
 
int main()
{
    int a[11],i;    //定義數(shù)組及變量為基木整甩
    printf("請(qǐng)輸入10個(gè)數(shù)據(jù)：\n");
    for (i =1;i<=10;i++)
        scanf("%d",&a[i]);    //接收從鍵盤(pán)輸入的10個(gè)數(shù)據(jù)到數(shù)組a中
    printf("原始順序：\n");
    for(i=1;i<11;i++)
        printf("%5d",a[i]);    //將未排序前的順序輸出
    insort(a,10);    //調(diào)用自定義函數(shù) insort()
    printf("\n 插入數(shù)據(jù)排序后順序：\n");
    for(i=1;i<11;i++)
        printf("%5d",a[i]); //將排序后的數(shù)組輸出
    printf("\n");
    return 0;
}
運(yùn)行結(jié)果：
請(qǐng)輸入10個(gè)數(shù)據(jù)：
25 12 36 45 2 9 39 22 98 37
原始順序：
25 12 36 45 2 9 39 22 98 37
插入數(shù)據(jù)排序后順序：
2 9 12 22 25 36 37 39 45 98

技術(shù)要點(diǎn)：
本實(shí)例算法過(guò)程如表 1 所示。

原始順序：25 12 36 45 2 9 39 27 98 37

表1 直接插入排序過(guò)程
趟數(shù)    監(jiān)視哨    排序結(jié)果
1    25    （12，）25，36，45，2，9，39，22，98，37
2    12    （12，25，）36，45，2，9，39，22，98，37
3    36    （12，25，36，）45，2，9，39，22，98，37
4    45    （12，25，36，45，）2，9，39，22，98，37
5    2    （2，12，25，36，45，）9，39，22，98，37
6    9    （2，9，12，25，36，45，）39，22，98，37
7    39    （2，9，12，25，36，39，45，）22，98，37
8    22    （2，9，12，22，25，36，39，45，）98，37
9    98    （2，9，12，22，25，36，39，45，98，）37
10    37    （2，9，12，22，25，36，37，39，45，98，）
指點(diǎn)迷津：
本算法中使用了監(jiān)視哨，主要是為了避免數(shù)據(jù)在后移時(shí)丟失。