插入排序

插入排序是一种简单的排序算法，其基本思想是将第一个记录看成是一个有序子序列，再依次从第二个记录起逐个插入到这个有序的子序列中。一般来说，在第i步上，将R(i)插入到R(i)~R(i-1)构成的有序子序列。

插入排序算法由嵌套的两个for循环组成，外层for循环n-1次，内层for循环比较复杂，循环次数依赖于第i个元素前关键字值比elem[i].key大的元素个数。

在最坏的情况下，每个循环都必须移动到数组的最前面，即原数组元素是逆序。这时第一趟循环1次，第二趟循环2次，依次类推，总比较的次数为 n(n-1)/2=O(n²)。

在最好的情况下，数组元素已经按关键字递增排序，这时每个内层循环到的元素都不需要移动，总的比较次数为n-1，所以此时的时间复杂度为O(n)。

如果待排序元素是随机的，也就是排序的元素可能出现的概率是相同的，这时可取最坏情况和最好情况的平均值，平均时间复杂度为O(n²)

下面例子

1 def insert(L):
2     for i in range(1, len(L) - 1):
3         for j in range(i, 0, -1):
4             if L[j] < L[j-1]:
5                 L[j], L[j-1] = L[j-1], L[j]  # 当前的值比前一个小，则交换两个数的位置
6             else:
7                 break  # 当前的值比前一个大，表明顺序正确，直接退出当前循环

插入排序

原文：https://www.cnblogs.com/pyexile/p/10958118.html