排序学习思路：先实现单趟逻辑，在实现整体逻辑；先解决普遍情况，再解决特殊情况。

什么是插入排序

回忆下自己玩扑克牌的时候是怎么把手上的牌理顺的吧！其实那就是插入排序，从左边往右边，把一张张抽出来在左边插入到它适合的位置。

插入排序的特点是：完成插入动作的牌之间的是有序的，如下面动图中，开始插入7时，它前面插入过的3，5，9是有序的；开始插入2时，它前面插入过的3，5，9，7之间是有序的。

插入排序图解

排序前

排序过程

排序后

代码实现

#include <stdio.h>void InsertSort(InSoDataType* a, int n)
{//n个元素的数组，下标范围[0, n-1]for (int p = 0; p < n; ++p){//[0, end]有序，把a[end + 1]插入到前面序列int end = p;InSoDataType tmp = a[end];while (end > 0){if (tmp < a[end - 1]){a[end] = a[end - 1];--end;}else break;}a[end] = tmp;}
}void PrintfArr(int* a, int n)
{for (int i = 0; i < n; ++i)printf(" %d ", a[i]);printf("\n");
}int main()
{int arr[] = { 3, 5, 9, 7, 2, 1 };int arrsize = sizeof(arr) / sizeof(arr[0]);InsertSort(arr, arrsize);PrintfArr(arr, arrsize);return 0;
}