[排序算法] 四种排序算法的理论基础 + Python 代码：气泡排序、插入排序、选择排序、快速排序 - 插入排序（稳定排序）

最坏时间复杂度：O(n^2)
最好时间复杂度：O(n)
平均时间复杂度：O(n^2)
空间复杂度:O(1)

1. 插入排序思路（不额外增加空间，依次遍历，相邻元素两两交换）
插入排序可以理解为无序数组和有序数组两个部分，这里的插入就是指：将无序数组中的元素插入到有序数组的合适位置，假如一个数组[5,2,3,1]，把5当成初始的有序数组，剩余元素[2,3,1]为无序数组，我们的目的就是遍历无序数组，再从后往前扫描有序数组，如果无序数组中的元素比有序数组中的元素小，就说明需要把这个元素插入到有序数组中。
2比5小，交换2和5的位置；
3比5小，交换3和5的位置，但是3比2大，所以不交换3和2的位置…依次类推

2. 代码实现

 def insertSort(self,array):
        for i in range(1,len(array)): # 无序数组
            index=i-1
            while index -1<=0: # 无序数组中第一个元素和有序数组中所有元素进行比较交换，直到无序数组的元素大于有序数组里面的，结束交换
                if array[index+1]<array[index]:
                    temp=array[index]
                    array[index]=array[index+1]
                    array[index+1]=temp
                    index-=1
                else:
                    break
                    
        return array