插入排序的步骤是从第二个数开始往前比较，如果前面的数字比第二个数大，则向后移一位。知道再也找不到比第二个数大的时候，将第二个数插入到该位置。第二轮则是从第三个数开始，以此类推。

    1. enum Compare {
    2.   LESS_THAN,
    3.   BIGGER_THAN,
    4.   EQUAL,
    5. }
    7. /**
    8.  * 比较两个数的大小
    9.  * @param a
    10.  * @param b
    11.  */
    12. function defaultCompare<T>(a: T, b: T): Compare {
    13.   if (a < b) {
    14.     return Compare.LESS_THAN;
    15.   } else if (a === b) {
    16.     return Compare.EQUAL;
    17.   } else {
    18.     return Compare.BIGGER_THAN;
    19.   }
    20. }
    23. function insertionSort<T>(array: T[], compareFn = defaultCompare): T[] {
    24.   for (let i = 1; i < array.length; i++) {
    25.     const tmp = array[i]
    26.     let insertPos = i
    27.     for (let j = i - 1; j >= 0; j--) {
    28.       if (compareFn(array[j], tmp) === Compare.BIGGER_THAN) {
    29.         array[j+1] = array[j]
    30.         insertPos = j
    31.       } else {
    32.         break;
    33.       }
    34.     }
    35.     if (insertPos !== i) {
    36.       array[insertPos] = tmp
    37.     }
    38.   }
    40.   return array
    41. }

    时间复杂度分析：插入排序 - 图1