插入排序

复习算法，从简单的插入排序开始……

直接看算法导论，看伪代码看解释，云里雾里，大概是静不下心来吧

算了，看C代码，还是看不懂，什么i啊j啊，这些变量到底是什么意思啊

忽然发现当时写的代码开头有注释————插入排序的原理很简单：
用扑克牌来举例，左手上是一组已经排好序的牌，右手上是一组没排序的牌；
每次从右手取出一张牌，把左手上所有比这张牌大的牌都右移一位，在最后得到的空位中插入这张牌

代码：

#include <stdio.h>
#include "array_sort.h"

/**
 * @brief Insert Sort for array.
 *
 * Get a new card from unsorted group on right hand.
 * Insert it into the sorted group in left hand,
 * Cards on left hand that greater than the new card are right shift by 1,
 * the new card goes in the empty slot after right shift.
 *
 * @note Complexity: O(n^2).
 * @param array The array need to be sort.
 * @param len Length of array.
 * @return The sorted array, Ascending.
 */
int *insert_sort (int *array, int len)
{
	/**
	 * j for the select card in array
	 * i for the boundary of the sorted group in the beginging 
	 * i + 1 for the index for the selected card after iteration.
	 * key for the value of the selected card.
	*/
	
	int i, j, key;

	for (j = 1; j < len; j++)
	{
		key = array[j];
		i = j - 1;

		while (i >= 0 && array[i] > key)
		{
			array[i + 1] = array[i];
			i--;
		}
		array[i + 1] = key;
	}

	return array;
}