排序——插入排序法

插入排序法

插入排序法是将數組中的元素注意與以為排序好的資料進行比較，先将前兩個元素先派好，再将第三個元素插入到适當的位置。也就是這三個元素仍然是排序好的，接着将第四個元素加入，重複此步驟，直到排序完成為止。可以看作是在一串有序的記錄R1,R2,…,Ri中，插入新紀錄R，使得i+1個記錄排序妥當。

下面我們仍然用數列(55,23,87,62,16)從小到大的排序過程是說明插入排序法的演算流程。

演算

步驟一：55

步驟二：55<——23

步驟三：23，55，87

步驟四：23，55，87<——62

步驟五：23，55，62，87<——16

完成排序：16，23，55，62，87

###程式執行個體

#include<stdio.h>
#define SIZE 8

void inser(int *)
void showdata(int *)
void inputarr(int *，int)

int main(void)
{
    int data[SIZE]
    inputarr(data,SIZE)
    printf("before sort: ");
    showdata(data);
    inser(data);
    printf("after sort: ");
    system("pause");
    return 0;
}

void inputarr(int data[],int size)
{
    int i;
    for(i-0;i<size;i++)
    {
        printf("please input %d: ",i+1);
        scanf("%d",&data[i]);
    }
}

void showdata(int data[])
{
    int i;
    for (i=0;i<SIZE;i++)
        printf("%3d";&data[1]);
     printf("\n");
}

void inser(int  data[])
{
    int i;
    int j;
    int tmp;
    for (i=1;i<SIZE;i++)
    {
        tmp = data[i]
        j = i-1
        while (j>=0 && tmp<data[j])
        {
            data[j+1] = data[j];
            j--;
        }
        data[i+j] = tmp;
        printf("第%d次掃描： ",i);
        showdata(data)
    }
}