python插入排序的性能问题

1、空间复杂度是O(1)，是原地排序算法。

除了在运行时需要临时变量来存储交换的数据和下标之外，不需要额外的存储空间。

2、稳定性，对于值相同的元素，选择将出现较晚的元素插入较早出现的元素中。

这样可以保证原来的前后顺序不变，是一种稳定的排序算法。

3、时间复杂度，最好的时间复杂度是O(n)。

如果数据有序，则无需移动任何数据。在查找插入位置时，我们可以在从头到尾的有序区间内查找插入位置，每次只需比较插入位置一次，即可确定插入位置。如果数据是逆序的，每次相当于在数据的首位插入新数据，所以需要移动大量数据，最坏的时间复杂度是O(n^2)。通常的时间复杂度，因为在数据中插入元素的平均时间复杂度是O(n)，所以对于插入排序来说，每一次插入操作相当于在数组中插入一条数据，循环n次插入操作，所以平均时间复杂度为 O(n^2)。

本文教程操作环境：windows7系统、Python 3.9.1，DELL G3电脑。