直接插入排序

直接插入排序是一种简单的排序方法，具体做法是：在插入第i个关键码时，k1,k2,...,ki-1已经排好序，这时将关键码ki依次与关键码ki-1,ki-2,...,进行比较，找到ki应该插入的位置时停下来，将插入位置及其后的关键码依次向后移动，然后插入ki。

下面函数insertSort用直接插入排序对整数序列进行升序排序，在main函数中调用insertSort并输出排序结果。

void insertSort(int data[],int n)   //用直接插入法将data[0]~data[n-1]中的n个整数进行升序排序
{ int i,j;
 int tmp;
 for(i=1;i<n;i++){
   if(data[i]<data[i-1]){         //将data[i]插入有序子序列data[0]~data[i-1]
      tmp=data[i];                //备份待插入的元素
      data[i]=data[i-1];
      for(j=i-2;j>=0&&data[j]>tmp;j--)       //查找插入位置并将元素后移
         data[j+1]=data[j];
      data[j+1]=tmp;              //插入正确位置
   }  //if
 }  //for
}  //insertSort
int main()
{   int *bp,*ep;
    int n,arr[]={17,392,68,36,291,776,843,255};
    n=sizeof(arr)/sizeof(int);
    insertSort(arr,n);
    bp=arr;
    ep=arr+n;
    for(;bp<ep;bp++)        //按升序输出数组元素
       printf("%d\t",*bp);
    return 0;
}