直接插入排序

    直接插入排序为稳定排序，基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。时间复杂度为O（n*n），辅助空间为O（1）。

    基本思想：假设在排序过程中，记录序列R[1..n]，将记录R[i]插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。R[i]的插入过程就是完成排序中的一趟，随着有序序列的不断扩大，最终使全部有序，完成排列。

    算法分析：要将R[i]插入到前面的有序序列中，只要将该记录的关键字与第i-1个记录开始的记录关键字进行比较，当它比前面的数小时，前面的记录顺序后移，否则将该记录存入该单元。在此，还要注意将R[i]临时存储到R[0]中暂存。

 

     哨兵（监视哨）的作用：

1.作为临时变量存放R[i]的副本。

2.在查找循环中用来监视下标变量j是否越界。

 

    算法效率：

时间复杂度最好的情况是已经排好序，比较次数为n-1，移动次数为0；

最坏的情况是反序时进行插入排序，平均的移动次数和比较次数都是O(n*n)。

空间复杂度为O(1)。

 

    排序特点：

1.是一种稳定的排序方法。

2.适用于接近排好序的情况。

3.适用于n较小的情况。

4.直至最后一趟排序过程才能确定一个元素的最终位置。

 

     程序：

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>
#define MAXSIZE 10
typedef struct
{
 int length;
 int arr[MAXSIZE+2];
}list;

void insert(list* p)
{
 int i,j;
 for (i = 2; i <= p->length; i += 1)//第一个暂存，第二个数字是待比较的数字，从第三个开始比较起
  {
   p->arr[0] = p->arr[i];//数组的第一个数字用来暂存每次用来比较的arr[i]

     for (j = i-1; (p->arr[0] < p->arr[j]) && j!=0; j --)
     {
     p->arr[j+1] = p->arr[j];
     }
   p->arr[j+1] = p->arr[0];

  }
}
int main()
{
 int i;
 list *plist;
 plist = (list*)malloc(sizeof(list));//分配空间
 plist->length = MAXSIZE;
 plist->arr[MAXSIZE+2] = 0;//将最后一个数字置为0

 srand((unsigned int)time(NULL));//随机种子生成

 for (i = 1; i < MAXSIZE+1; i += 1)//数组的第一个数字用来暂存每次用来比较的arr[i]
  {
  plist->arr[i] = (rand() % 100);//生成10个100以内的随机数
  printf("array before:%d\n", plist->arr[i]);
  }

 insert(plist);

 printf("\n");

 for (i = 1; i < MAXSIZE+1; i += 1)
  {
  printf("array after:%d\n", plist->arr[i]);
  }
 return 0;
}

    从空间来看，它只需要一个记录的辅助空间R[0]；从时间来看，n个记录要进行n-1趟插入过程，每一趟都要进行与关键字的比较和记录的移动，但是比较的次数是不固定的。最好的情况是记录已经是排列有序的，则每一趟都只需要比较一次，就可以找到插入记录的位置，不需移动记录，复杂度为O（n）；最坏情况是记录逆序存放，则每一趟都要与前面的关键字进行比较并移动记录，复杂度为O（n*n）。所以平均性能的复杂度为O（n*n）。

    因此，直接插入排序算法非常适合记录基本有序且记录数不是很多的情形。