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，）

指點迷津：

本演算法中使用了監視哨，主要是為了避免資料在後移時丟失。