前言：插入排序算法是所有排序方法中最簡單的一種算法，其主要的實現思想是將數據按照一定的順序一個一個的插入到有序的表中，最終得到的序列就是已經排序好的數據。
直接插入排序是插入排序算法中的一種，采用的方法是：在添加新的記錄時，使用順序查找的方式找到其要插入的位置，然后將新記錄插入。
很多初學者所說的插入排序，實際上指的就是直接插入排序算法，插入排序算法還包括折半插入排序、2-路插入排序，表插入排序和希爾排序等。

直接插入排序的基本操作是將一個記錄插入到已經排好的有序表中。

先選定一個位置i，插入排序將i左側比位置i數值大的數值全部右移，然后將原來i對應的值插入回去。

voidInsertSort(int*p){int i,j;inttmp=0;for(i=1;i<10;i++)
{if(p[i-1]>p[i]) {tmp = p[i];//將p[i]左邊比p[i]大的全部左移，要先將其賦給一個緩存變量
for(j=i-1;p[j]>tmp;j--)
{p[j+1]=p[j];
}p[j+1]=tmp;
} }}

過程，先將p[i]的值賦給tmp，然后i左側的數值與tmp比較，比tmp大則右移一位，不比tmp大，則將tmp插入回去。

最好情況下，即要排序的序列本身是有序的，第7行的比較一共執行了n-1次，沒有移動記錄，時間復雜度為O(n)。

最壞情況下，需要比較2+3+...+n=(n+2)(n-1)/2次，移動次數為(n+4)(n-1)/2

時間復雜度為O(n2)