插入排序

插入排序原理：
将待排序的集合分为两个子集，一个是已排序子集，一个是未排序子集。插入排序的过程就是从未排序子集中逐个取出元素插入到已排序子集中。
集合可以是数组，也可以是链表。
插入排序的时间复杂度是O(n*n)。

插入排序算法实现：

/*
 * insertion sort
 * It splits the array into two arrays, one is in order, the other is not.
 * The sort process will get the element from the unsorted array one by one,
 * then insert it into the sorted array.
 */
void insertion_sort(int a[], int size)
{
    int i, j;
    int tmp;

    /* i starts from 1, not 0, because a[0] is in order */
    for (i=1; i<size; i++){
        tmp = a[i]; /* a[i] is the element got from unsorted array */

        j = i - 1; /* a[0] to a[i-1] is the sorted array */
        while (j>=0 && a[j]>tmp){ /* while is more straightforward than for loop */
            a[j+1] = a[j]; /* move the elment in sorted array */
            j--;
        }
        /*
        for (j=i-1; j>=0; j--){
           if (a[j] > tmp){
              a[j+1] = a[j];
           } else {
              break;
           }
        }
        */
        a[j+1] = tmp; /* j+1 is the place to insert element */
    }
}