插入排序
它是將一個已經有序的數據序列，在這個已經排好的數據序列中插入一個數，但要求插入後此數據序列仍然有序一種新的排序方法。插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據，算法適用於少量數據的排序。它的過程是：把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最後一個元素除外，而第二部分就只包含這一個元素。在第一部分排序後，再把這個最後元素插入到此刻已是有序的第一部分裡的位置。
插入排序包括:直接插入排序，二分插入排序（又稱折半插入排序），鏈表插入排序,希爾排序（又稱縮小增量排序）。
為了方便描述，使用順序表類型定義如下：
#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的專欄”
