C語言直接插入排序算法

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

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

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

技術要點：
本實例算法過程如表 1 所示。

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

表1 直接插入排序過程
趟數    監視哨    排序結果
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，）
指點迷津：
本算法中使用了監視哨，主要是為了避免數據在后移時丟失。