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

霍格沃兹测试开发学社 霍格沃兹公开课
1
排序算法名称 时间复杂度 基于比较
冒泡，插入，选择 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 个赞