for(j=i;j>0 && a[j-1]>key;j--)
3.插入元素 a[j] = key;

#include<stdio.h>
#define MAX 8
int main(void)
{
    int a[MAX]={8,7,6,5,4,3,2,1};
    int i;
    void insert(int*a,int n);//函数声明

    insert(a,MAX);
    printf("after:\n");
    for(i=0;i<8;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
}

void insert(int *a,int n)
{
    int i,j,key;
    for(i=1;i<n;i++)//控制需要插入的元素
    {
        key=a[i]; //key为要插入的元素
        for(j=i;j>0 && a[j-1]>key;j--) //查找要插入的位置,循环结束,则找到插入位置
        {
            a[j] = a[j-1]; //移动元素的位置.供要插入元素使用
        }
        a[j] = key; //插入需要插入的元素

    }
}

由于嵌套循环的每一个都花费 N次迭代,因此插入排序 为 O(N的2次方);
在另一方面.如果数据是已经排序好的.则运行时间只要O(N),因为内层的for检测总是判定不成立的
所以需要知道插入排序的平均运行时间. 即为 O(N的2次方);

转载请注明出处: http://blog.sina.com.cn/u/1835498344
                http://weibo.com/1835498344