算法导论2-4 O(nlgn)时间复杂度求逆序对

def mergesort(nums,le,ri):

    if le>ri-2:

        return 0

    mi=le+(ri-le)//2

    a=mergesort(nums,le,mi)

    b=mergesort(nums,mi,ri)

    c=merge(nums,le,mi,ri)

    return a+b+c

def merge(nums,le,mi,ri):

    i,j=le,mi

    data=[]

    count=0

    while i<mi and j<ri:

        if nums[i]<nums[j]:

            data.append(nums[i])

            i+=1

        else:

            print(nums[i],nums[j])

            data.append(nums[j])

            j+=1

            count+=mi-i

    while i<mi:

        data.append(nums[i])

        i+=1

    while j<ri:

        data.append(nums[j])

        j+=1

    nums[le:ri]=data

    return count

x=mergesort(a,0,len(a))

print(a)

print(x)

解释：就是在merge里加一个计数器，若A[I]>A[J]则A[J]和A[I]到A[MID-1]的所有元素都构成逆序对，即count+=（mid-1）-i+1=mid-i

巴特西

算法导论2-4 O(nlgn)时间复杂度求逆序对

最新文章

热门文章