实现直接插入排序（数据结构与算法 - 排序）

记号说明：a[k:r]是指序列a[k] a[k+1] a[k+2] … a[r]。
为了讨论简单，假设待排序的每个记录是一个整数，这个整数就是排序码。
直接插入排序：先将第一个记录看作是一个有序的记录序列，然后从第二个记录开始，依次将未排序的记录插入到这个有序的记录序列中去，直到整个文件中的全部记录排序完毕。
举例说明：
假设待排序的序列是：46,58,15,45,90,18，下面的描述中[ ]中的序列是有序序列，[ ]后面的记录是待排序的。排序过程是：i从1到n-1执行“将a[i]插入到a[0…i-1]得到从小到大的排列a[0…i]”。
示例过程如下：
初始a[0:0]是一个有序序列：[46] 58 15 45 90 18；
将a[1]插入a[0:0]得到a[0:1]：[46 58] 15 45 90 18；
将a[2]插入a[0:1]得到a[0:2]: [15 46 58] 45 90 18；
将a[3]插入a[0:2]得到a[0:3]: [15 45 46 58] 90 18；
将a[4]插入a[0:3]得到a[0:4]：[15 45 46 58 90] 18；
将a[5]插入a[0:4]得到a[0:5]：[15 18 45 46 58 90]；
将a[i]插入到a[0:i-1]得到a[0:i]的方法是：
首先将a[i]放入临时变量temp：temp = a[i]；然后a[i-1],a[i-2],…依次与temp比较，若大于temp，则往后移动一个位置；最后一个腾出的位置放置temp的值。

#include<stdio.h>
#include<stdlib.h>
#include"directInsSort.h"
void DirecInsSort(int* a, int n)
// direct insert sorting
{
    int i, k,temp;
    for (i=1; i<n; i++)   
 {
  for(int j=0;j<n-i;j++)
  {
   if(a[j]>a[j+1])
   {
    temp=a[j];
    a[j]=a[j+1];
    a[j+1]=temp;
   }
  }
    }
}
void SortPrint(int* a, int n)
{
    int i;
    printf("sort result:");
    for (i=0; i<n; i++)
    {
     printf("%d ", a[i]);
 }
    //printf("\n");
}
int main()
{
    int n;
    scanf("%d", &n);
    int i;
    int * a=(int*)malloc(sizeof(int)*n);
    for (i=0; i<n; i++) scanf("%d", &a[i]);
    DirecInsSort(a,n);
    SortPrint(a,n);
    //system("PAUSE");
    //free(a);
}