算法研究之—插入排序

插入排序原理:插入排序的工作方式像许多人排序一手扑克牌.开始时,我们的左手为空并且桌子上的牌面向下.然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置.为了找到一张牌的正确位置,我们从右向左将它与已在手中的每张牌进行比较,拿在左手中的牌总是排序好的. 

INSERTION-SORT 伪代码:

代码实现:

插入排序的时间复杂度为 o(n^2)。

参考:算法导论(原书第3版)