1.直接插入排序
1）時間復雜度：T（n）=O（n^2）;
2）空間復雜度：S(n)=O(1);
3）簡介：直接插入排序是一種最基本的插入排序方法，直接插入排序（Straight Insertion Sorting）的基本思想是把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程 中每次從無序表中取出第一個元素，將它插入到有序表中的適當位置，使之成為新的有序表，重復n-1次可完成排序過程。把a[i]插入到a[0]，a[1]，...,a[i-1]之中的具體實施過程為:先把a[i]賦值給變量t,然後將t依次與a[i-1],a[i- 2],...進行比較,將比t大的元素右移一個位置,直到發現某個j(0<=j<=i-1),使得a[j]<=t或j為(-1),把t 賦值給a[j+1].
4）直接插入排序實現：
eg：待排序的序列為{48，62，35，77，55，14，35，98}；
A）首先將待排序得數存入數組a[]中，且a[0]不賦值（a[0]是一個監哨，其作用一是臨時保存待插入的記錄，二是防止越界），首先將第一個數字（也就是a[1]看作已排好順序的單元素子集合）；
{48}，62，35，77，55，14，35，98
B）其次將a[2]賦值給a[0],然後a[2]與a[1]比較，每次比較如果a[2]小於a[1]數值交換否則此次比較終止，交換後，a[1]與a[0]比較（我們可以看到無論a[1]原本的a[2]，a[0]等於原本的a[2]，所以無論如何都不會與a[0]進行交換，這就是a[0]所起到的監哨與記錄的作用）本例中a[2]=62>(a[1]=48),所以不進行交換；
{48，62}，35，77，55，14，35，98;
同理：
C）{35，48，62}，77，55，14，35，98;
D）{35，48，62，77}，55，14，35，98;
E）{35，48，55，62，77}，14，35，98;
F）{14，35，48，55，62，77}，35，98;
G）{14，35，35，48，55，62，77}，98;
H）{14，35，35，48，55，62，77，98};
4）源代碼：
typedef int KeyType;
typedef struct{
Keytype key;
OtherType other_data;
}RecordType;
void InsSort(RecordType r[],int length)
{
for(i=2;i<=length;
{
r[0]=r[i];j=i-1;
while(r[0].key<r[i].key)
{
r[j+1]=r[j];j=j-1;
}
r[j+1]=r[0];
}
}
