思路：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，插入后，有序表继续有序。

    初始化：取待排序中的第一个元素为为有序表，除了第一个元素的所有元素组成无序表。

    直接插入排序是由两层嵌套循环组成。外层循环标识并决定待插入到有序数列的元素。内存循环为待插数值确定其合适位置，是插入后有序序列仍为有序序列。

    外层循环从第2个数值开始。

    内层循环中，待插入数值和它左面第1个数值比较，若左面第1个数值比它大，则左面第1个数值放到其后面的位置中（即带插入数值的位置，所以用temp保存一下待插值），然后和左面第2个比较，否则将待插入值放到它左面第1个数值的右面。依次类推。

#include 
     
      #include 
      
       void swap(int arr[] ,int i, int j){int temp;temp = arr[i];arr[i] = arr[j];arr[j] = temp;}void InsertSort(int arr[], int n){int i;for(i=1;i
       
        =0 && arr[j]>temp){arr[j+1] = arr[j];j--;}arr[j+1] = temp;}}void print(int arr[], int n){int i;for(i=0; i
       
      
     

复杂度:O(n²)

稳定排序