优秀算法系列--排序算法（二）

插入排序
它是将一个已经有序的数据序列，在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序一种新的排序方法。插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。它的过程是：把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的位置。

插入排序包括:直接插入排序，二分插入排序（又称折半插入排序），链表插入排序,希尔排序（又称缩小增量排序）。

为了方便描述，使用顺序表类型定义如下：

#define MAXSIZE 1000
typedef int KeyType;
typedef struct {
KeyType key;
InfoType otherinfo;
}RecType;

typedef struct {
RecType r[MAXSIZE+1];
int length;
}SqList;
直接插入排序：
设R[1...n]为待排序的n个记录，R[1...i-1]已按照关键字从小到大排序。

void Dinsert (SqList & q)
{
   int i,j,k;
   RecType t;
   for(i=1;i<q.length;i++)
    {
        for(t=q.r[i],j=i-1;j>=0&&t.key<q.r[j].key;j--)
          q.r[j+1]=q.r[j];
        q.r[j+1]=t;
    }
}
希尔排序：
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

希尔排序基本思想：

　　先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

　　该方法实质上是一种分组插入方法。

　　给定实例的shell排序的排序过程：

初次取线性表的一半长度为步长，以后每次减半，直到步长为1，算法如下：

void Shsort(SqList &q)
{
   int j,K,h;
   RecType y;
   for(h=q.length/2;h>0;h/=2)
      for(j=1;j<=h;j++)
       {
        y=q.r[j];
          for(k=j-h;k>=0&&y.key<q.r[k].key;k-=h)
          q.r[k+h]=q.r[k];
         q.r[k+h]=y;
       }
}
　　好了，就先说到这里了。

作者“flute的专栏”

补充：软件开发 , C语言 ,