排序算法01 - 插入排序 （C语言）

原理

将a[0]作为哨兵，然后从a[2]开始遍历数组，如果发现前者比后者大，则将后者存入哨兵，再从后向前调整数组元素的位置，最后将哨兵插入即可。

图示

代码

#include<stdio.h>
const int N=10010;
int a[N];n;
void insert_sort(int a[])
{
    int j;
    for(int i=2;i<=n;i++)
    {
        if(a[i]<a[i-1]) {
            a[0] = a[i];
            for (j = i - 1; a[j] > a[0]; j--)
                a[j + 1] = a[j];
            a[j+1] = a[0];
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    insert_sort(a);
    for(int i=1;i<=n;i++)
        printf("%d ",a[i]);
    return 0;
}