统计逆序【python】

给定一个序列：[a1,a2,a3,a4,……,an]，若i<j且ai>aj，则构成逆序

分治思想：

分解：将原序列分成左右两部分left和right

递归：对每一部分调用inversion来计算各部分的逆序数

合并：结果为count_left(left)+count_right(right)+count_left_right(left,right)

其中count_left和count_right分别为调用inversion函数求解出来的逆序数，而count_left_right为调用merge（left,right）函数得到的结果

下面详细来说merge函数：

merge函数

用来处理跨界的逆序数。最简单的方法就是分别将left的n/2个元素和right的n/2个元素进行比较，时间复杂度为O(n^2)

优化思考：如果左右两边都是有序的,

              1）若left[i]<right[j]，则left[i]比right[j]右边的元素都小，不构成逆序对

              2）若left[i]>right[j]，则left[i]右边的元素都比right[j]大，构成的逆序对数为len(left)-i

但是排序会影响原列表中各元素的的位置，所以必须先计数，再排序，为了方便，把排序后的放到新列表中

最后的解法时间复杂度为O(nlogn)

def inversion(A):
    lent=len(A)
    if lent<2:
        return 0,A
    mid=lent//2
    left=A[:mid]
    right=A[mid:]
    count_left,left=inversion(left)
    count_right,right=inversion(right)
    count_left_right,mergeA=merge(left,right)
    return count_left+count_right+count_left_right,mergeA

def merge(left,right):
    alist=[]
    lenl=len(left)
    lenr=len(right)
    i,j,inver=0,0,0
    while i<lenl and j<lenr:
        if left[i]<=right[j]:   #left[i]于right[j]及right[i]的元素都不构成逆序对
            alist.append(left[i])
            i+=1
        else:
            inver+=lenl-i   #先计数，再排序
            alist.append(right[j])
            j+=1
    while i<lenl:
        alist.append(left[i])
        i+=1
    while j<lenr:
        alist.append(right[j])
        j+=1
    return inver,alist


if __name__ == "__main__":
    list=[5,7,3,3,8,6]
    print(list)
    print(inversion(list))

最后

以上就是虚心奇迹为你收集整理的统计逆序【python】的全部内容，希望文章能够帮你解决统计逆序【python】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。