基本思想：每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的序列的合适位置上，直到元素全部插入完毕。 直接插入排序：
void InsertSort(int *arr, int size) { int i = 0; int tmp = 0; int end = 0; for (i = 0; i < size; i++) { tmp = arr[i]; end = i; while (end>0 && arr[end-1]>tmp) { arr[end] = arr[end - 1]; end--; } arr[end] = tmp; } }空间复杂度：O(1) 时间复杂度：O(n*n) 稳定性：稳定 使用场景：对于一组有序的序列，想插入一个数据。
插入排序的优化：使用二分查找找到合适的插入位置（折半插入排序）
void InsertSort_OP(int *arr, int size) { int tmp = 0; int i = 0; int left = 0; int right = 0; for (i = 0; i < size; i++) { left = 0; right = i-1; tmp = arr[i]; while (left <= right) { int mid = left + ((right - left) >> 1); if (tmp > arr[mid]) left = mid + 1; if (tmp < arr[mid]) right = mid - 1; } int j = i; while (j>left && arr[j-1]>tmp) { arr[j] = arr[j - 1]; j--; } arr[left] = tmp; } }我们与直接插入的方法比较，可以看出，直接插入法，没插入一个元素，都要依次与有序元素序列每一个元素比较，最差的情况要比较N次，所以要排序N个元素，时间复杂度为O(n*n).而折半插入排序，每次先用折半查找到有序序列中的合适的位置，需要比较log以2为底的n次。找到合适位置后再移动有序序列中元素。 时间复杂度：最差的情况O(n*n) 最好的情况O(lgn) 空间复杂度：O(1) 稳定性：稳定 在大规模数据中，折半查找比直接插入排序要快。
希尔排序：将待排序的序列分成若干个子序列（由某一分量相隔的元素组成），分别对若干个子序列进行直接插入排序，之后依次缩小分量直到整个序列基本有序，再对整个序列进行直接插入排序，基于插入排序在基本有序的序列中效率极高，因此可以提高直接插入排序的效率。
void ShellSort(int* array, int size) { int i = 0; int j = 0; int tmp = 0; int gap = size >> 1; while (gap >= 1) { for (int k = 0; k < (size/2); k++) { for (i = k; i < size; i += gap) { j = i; tmp = array[i]; while (j > 0 && tmp < array[j - gap] && (j-gap>=0)) { array[j] = array[j - gap]; j -= gap; } array[j] = tmp; } } gap /= 2; } }时间复杂度：O(n*lgn) (lgn为 log以2为底的n) 空间复杂度：O(1) 稳定性：不稳定
