插入排序Python版

94 3月之前 Python 算法

答案

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5
def insertion_sort(lst):
    for i in range(1, len(lst)):
        pos = i
        current = lst[pos]

        while pos > 0 and lst[pos - 1] > current:
            lst[pos] = lst[pos - 1]
            pos = pos - 1

        lst[pos] = current

     return lst

时间复杂度:

  • 最坏:O(n2)
  • 平均:O(n2)
  • 最好:O(n)