一、原理

        每次从无序数据中取出一个，插入到有序的数据列表中合适的位置，保证插入后的列表依然后续。

       如：一堆牌，原先手上没有牌，依次从牌堆上取一张到手上，第一张牌到手上时，手上只有一张牌，即为有序，取第二张和第一张比较，插入合适的位置，保证手上的牌依然后续，依次类推。

二、时间和空间复杂度

      最坏的情况是数据是倒序的，时间复杂度为： T(n)=O(1+2+....+n-1)=O((n^2)/2 - n/2)=O(n^2)

      最好的情况是数据已经是有序的，时间复杂度为：O(n)

      空间复杂度：O(1)

三、排序过程图

四、代码实现

void insert_sort(int arr[], int arr_size){     int index_tra; //用于外层循环，遍历整个数组     int index_sort; //用于内层循环，找到合适的位置     int tmp; //                     index_tra = 1;     while (index_tra < arr_size) {         index_sort = index_tra - 1;         tmp = arr[index_tra];         while (index_sort >= 0 && arr[index_sort] > tmp) {              arr[index_sort + 1] = arr[index_sort];              index_sort--;           }          arr[index_sort + 1] = tmp; //找到合适的位置，插入          index_tra++;     }     }