python - 排序算法命名法

Question

下面的排序算法叫什么名字？

 for i in range(1, len(a)):
    for j in range (0,i):
        if(a[j] > a[i]):
            a[i], a[j] = a[j], a[i]

Answer 1

这是插入排序的一种变体:在外循环的每次迭代之前，对列表的前缀进行排序，然后外循环的每次迭代都将以下元素插入到其正确位置，将已排序的前缀增加 1。通常插入排序会在内循环中向下迭代；这个变体从底部开始，因此一旦放置了新元素就不能提前退出内部循环。插入排序通常具有最佳情况 O(n)，但此变体是最佳情况 O(n^2)。