插入排序

时间复杂度：

O(n^2) ~ O(n)

原理（降序）：

对于一个已经排好序的序列，当插入一条新值时，此时仅需要找到该值适当的位置插入即可。

步骤（降序）：

1、对于一个无序的序列，取其第一个值单独作为一个有序的序列。
2、以第二个值为起始，依次往前对比前两个值是否符合排序规则，不满足则交换这两个值，满足则可以退出当前循环。
3、依次循环遍历至最后一个值。

https://github.com/czasg/strualgo/blob/main/algo/sort/insertion.go

package sort

import "github.com/czasg/strualgo/basis"

func InsertionSortASC[Number basis.Number](nums []Number) []Number {
    newNums := make([]Number, len(nums))
    for index, num := range nums {
        newNums[index] = num
    }
    if len(newNums) < 2 {
        return newNums
    }
    for i := 1; i < len(newNums); i++ {
        index := i
        for index > 0 {
            if newNums[index-1] > newNums[index] {
                newNums[index-1], newNums[index] = newNums[index], newNums[index-1]
            } else {
                break
            }
            index--
        }
    }
    return newNums
}