6.插入排序-python

霍格沃兹测试学院校内交流
1

插入排序

有序度：比如说2、4、3、1、5、6这组数组的有序度是11，因为它有11个有序元素对，分别是(2,4)、(2,3)、(2,5) (2,6)、(4,5)、(4,6)、(3,5)、(3,6)、(1,5)、(1,6)、(5,6)。

逆序度：满有序度 - 有序度。

对于 6、5、4、3、2、1这组数据，它的有序度是0；对于1、2、3、4、5、6这组数据来说，它的有序度是n*(n-1)/2，这种完全有序的数组的有序度叫做满有序度。

移动次数 == 逆序度：n*(n-1)/2

class InsertionSort:
    def sort(self, data):
        for i in range(1, len(data)):
            value = data[i]
            j = i - 1
            while j >= 0 and data[j] > value:
                data[j + 1] = data[j]
                j -= 1
            data[j + 1] = value




if __name__ == '__main__':
    insertion_sort = InsertionSort()
    data = [5, 2, 1, 4, 10, 3, 6, 7]
    insertion_sort.sort(data)
    assert data == [1, 2, 3, 4, 5, 6, 7, 10]

空间复杂度：O(1)
时间复杂度：
最好：O(n)
最坏：O(n2)
平均：O(n*((1+2+3+…+n)/n)) = O(n2)

稳定：