基本思想：依次將待排序序列中的每一個記錄插入到一個已排好序的序列中，知道全部記錄都排好序衰腌。
具體過程：
(1)將整個待排序的記錄序列劃分為有序區(qū)和無序區(qū)，初始時有序區(qū)為待排序記錄序列中的第一個記錄皇型，無序區(qū)包括所有剩余待排序的記錄默垄；
(2)將無序區(qū)的第一個記錄插入到有序區(qū)的合適位置中，從而使無序區(qū)減少一個記錄憎妙，有序區(qū)增加一個記錄库正；
(3)重復(fù)執(zhí)行(2)，直到無序區(qū)中沒有記錄為止厘唾。
//直接插入排序算法
void InsertSort(int r[], int n)//0號單元用作暫存單元和監(jiān)視哨
{
int i, j;
for (i = 2; i <= n; i++)
{
r[0] = r[i]; //暫存待插關(guān)鍵碼褥符，設(shè)置哨兵
for (j = i - 1; r[0] < r[j]; j--) //尋找插入位置
r[j + 1] = r[j]; //記錄后移
r[j + 1] = r[0];
}
}
// 時間復(fù)雜度為O(n^2)
