直接插入排序是将第一个数当作有序区，其后的数据进行排序，依次插入有序区。
void InsertSort(int*arr, int n) { for (int i = 0; i < n - 1; ++i) { int end = i; int tmp = arr[end + 1]; while (end>=0) { if (arr[end]>tmp) { arr[end + 1] = arr[end]; --end; } else { break; } arr[end + 1] = tmp; } } }直接插入排序的时间复杂度：O(N^2)[最好情况：O(N) 最坏情况：O(N^2)] 空间复杂度：O(1) 直接插入排序是一种稳定的排序算法。
插入排序效率最高的情况： 如果当要排序的序列大致上接近于有序的时候，插入排序的效率最高，基本上接近O(N)。因为当数据基本上接近于有序的时候，元素向有序区插入的时候比较的次数会很少，同样有序区元素向后移动的次数也是很少的。
插入排序效率最低的情况： 如果当要排序的序列大致上接近于逆序的时候，插入排序的效率最低，基本上接近与O(N^2)。因为这时候每向有序区插入一个元素的时候，假设最极端的情况下要比较和移动的次数就是有序区的长度。这时候插入排序的效率就会很低。
希尔排序是对直接插入排序的优化， gap的值越大，小的数会尽快往前排序，但是也是越不接近有序的。
void ShellSort(int *arr, size_t n) { int gap = n; while (gap > 1) { for (size_t i = 0; i < n - gap; ++i) { gap = gap / 3 + 1; int end = i; int tmp = arr[end + gap]; while (end >= 0) { if (arr[end] > tmp) { arr[end + gap] = arr[end]; end -= gap; } else { break; } arr[end + gap] = tmp; } } } }当一组数据接近有序的时候，优先选择插入排序，一组数据接近逆序的时候，优先选择希尔排序。 插入情况最好的情况就是希尔排序最坏的情况，因为这时候希尔排序的预排序起不到作用。插入排序最坏的情况则是希尔排序最高的情况，因为这时候预排序的效果是非常明显的。
希尔排序的时间复杂度：O(N^1.3)[最好情况：O(N) 最坏情况：O(N^2)] 空间复杂度：O(1) 希尔排序是一种不稳定的排序算法。
