直接插入排序
直接插入排序(Straight Insertion Sort)是一種最簡單的排序方法，其基本操作是将一條記錄插入到已排好的有序表中，進而得到一個新的、記錄數量增1的有序表。
直接插入排序的方法：先将序列中第一個記錄看成有序的子序列，然後從第二個記錄起逐個進行插入，直至整個序列變成按關鍵字遞減的有序序列為止
直接插入排序中需要設定一個臨時變量temp，temp在直接插入排序中尤為重要，充當了一個哨兵的角色。
下面我們用這樣一個例子去詳細的說明直接插入排序的過程：
現在我們有一串無序序列“49，38，65，97，76，13，27，49”也就是一串數組，設為數組a
我們要用直接插入排序的方法将其變為有序的序列
1.先将這八個數字标号：
2.此時我們将a[0]看為為有序序列，從a[1]開始逐個插入，是以将a[1]的值賦給哨兵temp，a[1]的值就為空了
3.将哨兵temp與有序序列的最後一位比較；如若temp的值>=有序序列最後一個的值/temp比較完了有序序列中所有的數（也就是temp的值最小，則temp值賦給數組中的空位；如若temp的值<有序序列最後一個的值，則有序序列的最後一個向前移動填補前面的的空位，留下自己原來的位置作為空位，然後temp的值在與有序序列的倒數第二位比較，直至temp>有序序列的某一位的值，比較結束，temp填補空位
此例中：temp<a[0] ,則a[0]向前移動填補a[1]的空位，此時a[0]為空位，temp比較完了有序序列中所有的數，則temp值賦給空位
4.此時序列的前兩個數已經有序，則取第三位a[2]作為哨兵temp，留下空位a[2]
仿照3的比較過程用temp與有序序列最後一個數比較，也就是temp與a[1]比較，此時temp>a[1]，則temp填入空位a[2].
5
5.現在輪到a[3]了，a[0]-a[2]已經是有序序列了，是以取a[3]為哨兵，留下空位a[3]
仿照3的比較過程用temp與有序序列最後一個數比較，也就是temp與a[2]比較，此時temp>a[2]，則temp填入空位a[3].
6.此時a[0]-a[3]已經有序，輪到了a[4],是以取a[4]為哨兵，留下空位a[4]
仿照3的比較過程用temp與有序序列最後一個數比較，也就是temp與a[3]比較,此時temp<a[3],則将a[3]後移填補空位a[4],留下空位
a[3]
temp繼續比較，此時應該與有序序列中倒數第二個數比較也就是a[2],此時temp>a[2],是以temp填入空位a[3]
7.此時a[0]-a[4]已經成為有序序列，剩餘的三個數a[5],a[6],a[7]交給讀者自己思考，相信你一定可以還原出來整個過程的
接下來是是代碼部分（c語言）
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#defineMAXSIZE 8
typedef int KeyType; //定義關鍵字類型
typedef int InfoType; //其他資料項類型
typedefstruct //記錄類型
{
KeyType key; //關鍵字項
InfoType data; //其他資料項的類型InfoType
} RecType;
//排序的記錄類型定義
for(j = i; j > 0 &&R[j-1].key > temp.key; j–)
{
//把有序區中的關鍵字依次往後移動
R[j] = R[j-1];
}
//如果無序區中的第一個關鍵字比有序區中的關鍵字大，那麼無序區中的第一個關鍵字的位置插入到有序區中該關鍵字後面的位置
R[j].key = temp.key;
}
}
int main(void)
{
RecType R[MAXSIZE] = {0};
int arr[] = {49,38,65,97,76,13,27,49};
int i;
printf("--------排序前--------\n");
for(i = 0; i < MAXSIZE; i++)
{
R[i].key = arr[i];
printf(“R[%d].key = %d\n” , i, R[i].key);
}
//插入排序
InsertSort(R, MAXSIZE);
printf("--------排序後--------\n");
for(i = 0; i < MAXSIZE; i++)
{
printf(“R[%d].key = %d\n” , i, R[i].key);
}
return 0;
}
大家也能看出來直接插入排序中每次循環都要經過比較，移動
是以比較次數的時間複雜度為o（n * n）
移動次數的時間複雜度為o（n * n）
是以直接插入排序的時間複雜度為o（n * n）