继续上文讲排序的方法 插入排序：
void insert_sort(int *a, int len) { int i,j,get; for(i = 1; i < len; i++) { get = a[i]; j = i - 1; while(j >= 0 && a[j] > get) { a[j + 1] = a[j]; j--; } a[j + 1] = get; } }插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。 插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
引申1——二分插入排序：
void t_insert(int *a, int len) { int i,j; int get; int left,mid,right; for(i = 1; i < len; i++) { get = a[i]; left = 0; right = i - 1; while(left <= right) { mid = (left + right) / 2; if(a[mid] > get) { right = mid - 1; } else { left = mid + 1; } } for(j = i - 1; j >= left; j--) { a[j + 1] = a[j]; } a[left] = get; } }二分法插入排序是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left
void shell_sort(int *a, int len) { int i,j; int get; int d = len; do { d = d / 3; for(i = d; i < len; i++) { get = a[i]; j = i - d; while(j >=0 && a[j] > get) { a[j + d] = a[j]; j -= d; } a[j + d] = get; } }while(d > 1); }希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
