直接插入排序

插入类排序的基本思想：在一个已排好序的子集的基础上，每一步将下一个待排序的记录有序的插入到已排好序的子集中。

讲的通俗一点，每次我们选取一个待排序记录r(或一个元素)，向前插入，因为我们假设前面是已排好序的，那么我们只需要找到r之前的所有记录中第一个小于r的记录，停下，在这个记录后插入r。(因为是排好序的，所以第一个小于r的记录前面的记录都小于r)，这样就完成了一次插入排序。我们先对前两个记录排序，此时第二个记录为待排序记录r;再选第三个记录为待排序记录....继续....知道最后一个记录也被选为待排序记录，结束。

记住一句话：插入排序始终向前找到第一个小于自己的数，然后插入，待排记录后移，继续...

有两个版本，一个是ACM书上的，另一个我写的。其实都差不多了~

ACM版

/* Algorithm: Insert Sort
 * ACM edition
 * sort M number
 */
#include <stdio.h>

#define M 10

void insort(int A[],int n)
{
    int    i=2,j;

    for(i=2;i<n;i++)
    {
        A[0]=A[i];
        j=i-1;
        while(A[0]<A[j])
        {
            A[j+1]=A[j];/* move back A[j] */
            j--;
        }/* Find the 1st number which is little than A[i]
                then,insert A[0] */
        A[j+1]=A[0];
    }
}

int main(int argc,char **argv)
{
    int r[M+1];
    int i;

    printf("Input %d number:\n",M);
    for(i=1;i<=M;i++)
    {
        scanf("%d",&r[i]);
    }

    for(i=1;i<=M;i++){    
        printf("%d ",r[i]);
    }
    printf("\n");
    
    insort(r,M+1);
    for(i=1;i<=M;i++){    
        printf("%d ",r[i]);
    }
    printf("\n");
    return 0;
}

My edition

/* Algorithm: Inert Sort
 * My edition
 * sort M number
 */
#include <stdio.h>

#define M 10

void insort(int A[],int n)
{
    int    i,j;
    int r;

    for(i=1;i<n;i++)
    {
        r=A[i];
        for(j=i-1;j>=-1;j--)
        { /* Find the 1st number which is little than A[i]
                then,insert r(A[i]) and break */
            if(A[j]<=r || j==-1){
                A[j+1]=r;
                break;
            }    
            else if(A[j]>r)
                A[j+1]=A[j]; /* move back A[j] */
        }
    }
}

int main(int argc,char **argv)
{
    int r[M];
    int i;

    printf("Input %d number:\n",M);
    for(i=0;i<M;i++)
    {
        scanf("%d",&r[i]);
    }

    for(i=0;i<M;i++){    
        printf("%d ",r[i]);
    }
    printf("\n");
    
    insort(r,M);
    for(i=0;i<M;i++){    
        printf("%d ",r[i]);
    }
    printf("\n");
    return 0;
}