自动化测试-面试经典排序算法之插入排序

排序算法名称 时间复杂度 基于比较
冒泡,插入,选择 O(n2)
快排,归并 O(nlogn)
桶,计数,基数 O(n)

从三个维度衡量一个算法好坏:

稳定性

对对象排序,要考虑稳定性,比如对角标进行从小到大排序:B2,B1,B3,A2,有两种结果:

  1. B1,B2,A2,B3
  2. B1,A2,B2,B3

结果 1 是稳定的,排序前 B2 在 A2 前,排序后,B2 也在 A2 前。反之,结果 2 是不稳定的。

插入排序

有序度:比如说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

# 插入排序
def  insertion_sort ( a : List [ int ]):
    length  =  len ( a )
    if  length  <=  1 :
        return

    for  i  in  range ( 1 , length ):
        value  =  a [ i ]
        j  =  i  -  1
        while  j  >=  0  and  a [ j ] >  value :
            a [ j  +  1 ] =  a [ j ]
            j  -=  1
        a [ j  +  1 ] =  value

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

稳定:

课后表单:

1 Like