直接插入排序是一种比较容易理解的排序算法，其核心思想是遍历数组，将数组中的元素逐个插入到已排序序列中。

时间复杂度：O(n^2)

稳定性：稳定

实现：

1: /* @brief insetion sort

2:  * insert the new element to the sorted subarray

3:  */

4: void

5: insertion_sort(int a[], int n)

6: {

7:     int i, j, num;

8: 

9:     for (i = 1; i < n; ++i) {

10:         num = a[i];

11:         for (j = i - 1; j >= 0 && a[j] > num; --j)

12:             a[j+1] = a[j];

13:         a[j+1] = num;

14:     }

15: }