插入排序算法是所有排序方法中最簡單的一種算法迅办，其主要的實(shí)現(xiàn)思想是將數(shù)據(jù)按照一定的順序一個一個的插入到有序的表中，最終得到的序列就是已經(jīng)排序好的數(shù)據(jù)章蚣。
直接插入排序是插入排序算法中的一種站欺，采用的方法是：在添加新的記錄時，使用順序查找的方式找到其要插入的位置纤垂，然后將新記錄插入矾策。
很多初學(xué)者所說的插入排序，實(shí)際上指的就是直接插入排序算法峭沦，插入排序算法還包括折半插入排序贾虽、2-路插入排序，表插入排序和希爾排序等吼鱼，后序文章都會一一講到蓬豁。
例如采用直接插入排序算法將無序表{3,1,7,5,2,4,9,6}進(jìn)行升序排序的過程為：
首先考慮記錄 3 ，由于插入排序剛開始菇肃，有序表中沒有任何記錄地粪，所以 3 可以直接添加到有序表中，則有序表和無序表可以如圖1 所示：
?
向有序表中插入記錄 1 時琐谤，同有序表中記錄 3 進(jìn)行比較蟆技，1<3，所以插入到記錄 3 的側(cè)斗忌，如圖 2 所示：
?
向有序表插入記錄 7 時质礼，同有序表中記錄 3 進(jìn)行比較，3<7织阳，所以插入到記錄 3 的右側(cè)眶蕉，如圖 3 所示：
?
向有序表中插入記錄 5 時，同有序表中記錄 7 進(jìn)行比較陈哑，5<7妻坝，同時 5>3伸眶，所以插入到 3 和 7 中間，如圖 4 所示：
?
向有序表插入記錄 2 時刽宪，同有序表中記錄 7進(jìn)行比較厘贼，2<7，再同 5圣拄，3嘴秸，1分別進(jìn)行比較，最終確定 2 位于 1 和 3 中間庇谆，如圖 5 所示：
?
照此規(guī)律岳掐，依次將無序表中的記錄 4，9 和 6插入到有序表中饭耳，如圖 6 所示：
?
直接插入排序的具體代碼實(shí)現(xiàn)為：
#include <stdio.h>
//自定義的輸出函數(shù)
void print(int a[], int n ,int i){
printf("%d:",i);
for(int j=0; j<8; j++){
printf("%d",a[j]);
}
printf("
");
}
//直接插入排序函數(shù)
void InsertSort(int a[], int n)
{
for(int i= 1; i<n; i++){
if(a[i] < a[i-1]){//若第 i 個元素大于 i-1 元素則直接插入串述；反之，需要找到適當(dāng)?shù)牟迦胛恢煤笤诓迦搿?/p>
int j= i-1;
int x = a[i];
while(j>-1 && x < a[j]){ //采用順序查找方式找到插入的位置寞肖，在查找的同時纲酗，將數(shù)組中的元素進(jìn)行后移操作，給插入元素騰出空間
a[j+1] = a[j];
j--;
}
a[j+1] = x; //插入到正確位置
}
print(a,n,i);//打印每次排序后的結(jié)果
}
}
int main(){
int a[8] = {3,1,7,5,2,4,9,6};
InsertSort(a,8);
return 0;
}
運(yùn)行結(jié)果為：
1:13752496
2:13752496
3:13572496
4:12357496
5:12345796
6:12345796
7:12345679
直接插入排序算法本身比較簡潔新蟆，容易實(shí)現(xiàn)觅赊，該算法的時間復(fù)雜度為O(n2)。插入排序的其它 4 種排序方法琼稻，點(diǎn)擊獲取吮螺，喜歡的可以關(guān)注，點(diǎn)贊帕翻，轉(zhuǎn)發(fā)喲鸠补。
