【逆序數】哎呀為什么會有人想用QuickSort求逆序數嘛！-有解無憂

（這篇文章底端的圖為什么這么大……不管了）

[--大家好我們第一個團本CD就通了PT而且打掉了H老一呢，看不懂這行的請當它不存在--]

事情，大概是這樣的—— （沒錯這又是一篇我被作業演算法血虐的心路歷程大水文）

哦對了，得先解釋一下，逆序數這東西呢，可以理解為冒泡排序的程序中，bubble一次算一次逆序，全部排序完畢之后bubble了多少次，那就是逆序數是多少，

官方一點的解釋呢就是：

“對于n個不同的元素，先規定各元素之間有一個標準次序（例如n個不同的自然數，可規定從小到大為標準次序），于是在這n個元素的任一排列中，當某兩個元素的先后次序與標準次序不同時，就說有1個逆序，一個排列中所有逆序總數叫做這個排列的逆序數，”

哎呀求逆序數，開心，愜意，歸并走起，刷刷刷——

class SortAndCount_Merge():
    def __init__(self):
        self.inList = []
        
    def mergeAndCount(self, L, R):
        RC, i, j = 0, 0, 0
        ret = []
        for k in range(len(L) + len(R)):
            if i == len(L) or j == len(R):
                ret += L[i:] + R[j:]
                break
            elif L[i] > R[j]:
                ret.append(R[j])
                RC += len(L) - i
                # The Same as:
                # RC += (len(L) + len(R))/2 - i
                j += 1
            else :
                ret.append(L[i])
                i += 1
        return (RC, ret)

    def sortAndCount(self, A):
        if len(A) < 2: return (0, A)
        mid = len(A) / 2 
        L,R = A[:mid],A[mid:]
        RC_L, L = self.sortAndCount(L)
        RC_R, R = self.sortAndCount(R)
        # There can be a better method without recursive
        # Mark for advanced
        cnt, ret = self.mergeAndCount(L, R)
        cnt += RC_L + RC_R
        return (cnt, ret)

然后，悲傷如我，發現了題意是要求使用【快速排序】來求…… 唔，咱們用冒泡排序+插入排序+樹狀陣列各求一次行不，快排這么傷腦子的事情能不能就不做了？QvQ

不能，

哦……

class SortAndCount_QSort():
    def __init__(self, inList):
        self.A = inList
        self.cnt = 0
    
    def swap(self, pos1, pos2):
        l,r = min(pos1, pos2), max(pos1, pos2)
        self.cnt += (r - l)
        
        tmp = self.A[l]
        self.A[l] = self.A[r]
        self.A[r] = tmp

    def sortAndCount(self, lef, rig):
        if lef >= rig: return 
        pivot = lef
		for pos in xrange(lef+1, rig+1):
            if self.A[pos] < self.A[lef]:
                pivot += 1
                self.swap(pivot, pos)
        self.swap(lef, pivot)
        self.sortAndCount(lef, pivot-1)
        self.sortAndCount(pivot+1, rig)
        return (self.cnt, self.A)

于是心思縝密的我去對照了一下兩個演算法的答案……

然后把這段注釋掉了QvQ

""" There will be extra counts without modified-method. 
for pos in xrange(lef+1, rig+1):
	if self.A[pos] < self.A[lef]:
		pivot += 1
		self.swap(pivot, pos)
self.swap(lef, pivot)
""" #( counts QSORT:2502239417 > MERGE:2500572073 )

頭疼，能不能分成以pivot為界線，分成 “左邊的到了左邊”，“左邊的到了右邊”，“右邊的到了左邊”和“右邊的到了右邊”來考慮呢，然后我就寫了這么個可怕的東西——

然后……鄙人就是不服，可以的——

class SortAndCount_QSort():
    def __init__(self, inList):
        self.A = inList
        self.cnt = 0
    
    def swap(self, pos1, pos2):
        l,r = min(pos1, pos2), max(pos1, pos2)
        # self.cnt += (r - l)
        
        tmp = self.A[l]
        self.A[l] = self.A[r]
        self.A[r] = tmp
    
    def addPartCnt(self, pivot, dir, sig):  
        ins, insp, crs, crsp = 0, [], 0, [] # inside/cross part
        for idx in xrange( pivot + sig, dir + sig, sig ):
            if self.A[ins] < self.A[pivot]:
                insp.append(self.A[idx])
                ins += 1
            else:
                crsp.append(self.A[idx])
                crs += 1
                self.cnt += ins + 1 
        return insp, crsp, crs
        
    """ Simplified to addPartCnt() '''
    def addLefCnt(self, lef):
        lposl, L2L, lposr, L2R = 0, [], 0, []
        for idx in xrange(pivot-1, lef-1, -1):
            if self.A[lposl] < self.A[pivot]:
                L2L.append(self.A[idx])
                lposl += 1
            else:
                L2R.append(self.A[idx])
                lposr += 1
                self.cnt += lposl + 1 
        return L2L, L2R, lposr
    
    def addRigCnt(self, rig):
        rposr, R2R, rposl, R2L = 0, [], 0, []
        for idx in xrange(pivot+1, rig+1, +1):
            if self.A[rposr] > self.A[pivot]:
                R2R.append(self.A[idx])
                rposr += 1
            else:
                R2L.append(self.A[idx])
                rposl += 1
                self.cnt += rposr + 1 
        return R2R, R2L, rposl
    """
    
    def mergeAndCount(self, pivot, lef, rig):
        if not lef <= pivot <= rig: return
        ll, lr = [], []
        crsL2R, crsR2L = 0, 0
        if lef < pivot : ll, lr, crsL2R = self.addPartCnt(pivot, lef, -1) # addLefCnt()
        if rig > pivot : rr, rl, crsR2L = self.addPartCnt(pivot, rig, +1) # addRigCnt()
        ll.reverse()
        lr.reverse()
        self.cnt += crsL2R * crsR2L
        ret = ll + rl + [self.A[pivot]] + lr + rr
        if lef != 0: ret = self.A[:lef] + ret
        if rig != self.A.__len__()-1: ret = ret + self.A[rig+1:]
        self.A = ret
        
    def sortAndCount(self, lef, rig):
        if lef >= rig: return 
        pivot = lef
        self.mergeAndCount(pivot, lef, rig)
        self.sortAndCount(lef, pivot-1)
        self.sortAndCount(pivot+1, rig)
        return (self.cnt, self.A)

看吶我還發現了那兩段是一樣的，還合并成了一個函式是不是很聰明，是不是可以加分！

剛好 @ZoeCUR 來問我這道題，我三五句話給她講懂之后，她瞬間表示了解，演算法GET，三分鐘后，“這個還是簡單，不就幾行的事情么？” WHAT？！

經夫人一番指點果然豁然開朗……

然后我發現了……原來這就是一個……線性的……寫出來只要16行的……代碼……

對不起是我的錯，我想多了，對不起人民對不起國家：（沒錯前面都是廢話都是廢代碼親愛的讀者你發現了嗎？）

好的其實就是個線性的這么簡單的東西QwQ—— （聽說作業被抄襲也要算0分，這段先隱藏一下等作業提交截止了再發不好意思~）

class SortAndCount_QSort():
    def __init__(self):
        self.cnt = 0
    
    def swap(self, pos1, pos2):
        l,r = min(pos1, pos2), max(pos1, pos2)
        # self.cnt += (r - l)
        
        tmp = self.A[l]
        self.A[l] = self.A[r]
        self.A[r] = tmp
   
    def sortAndCount(self, inList):
        c, L, R = 0, [], []
        if inList.__len__() <= 1 : return c, inList

        for idx in xrange(1, inList.__len__()) :
            if(inList[idx] < inList[0]):
                c += idx - 1 - L.__len__()
                L.append(inList[idx])
            else: R.append(inList[idx])
        c += L.__len__()
        lcnt, L = self.sortAndCount(L)
        rcnt, R = self.sortAndCount(R)
        return lcnt + c + rcnt, L + [inList[0]] + R
        
        """ There will be extra counts without modified-method. 
        for pos in xrange(lef+1, rig+1):
            if self.A[pos] < self.A[lef]:
                pivot += 1
                self.swap(pivot, pos)
        self.swap(lef, pivot)
        """ #( counts QSORT:2502239417 > MERGE:2500572073 )

輸出結果：

E:\UCAS\計算機演算法設計與分析\Homework\091M4041H - Assignment1_DandC>python A08.py

[ANSWER]  Merge Version : 1.21399998665 sec.
the number of inversions in Q8.txt is:  2500572073
Check Completed: List Sorted.

[ANSWER]  Qsort Version : 0.953000068665 sec.
the number of inversions in Q8.txt is:  2500572073
Check Completed: List Sorted.

唔，為了伸手黨們，感覺該有的還是得有……像什么Main函式啊，讀入輸出啥的也貼一下好啦~

def readFile(filename):
    with open(filename,'r') as f:
        inList = [int(x) for x in f.readlines()]
        return inList

def check(A):
    a, b = A, xrange(1,100001)
    for pos in b:
        if a[pos-1] != pos:
            return "Unmatch at", pos
    return "Check Completed: List Sorted."
    
def printAnswer(mode, t, filename, cnt, ret):
    print "\n[ANSWER] ", mode, "Version :", t, "sec."
    print "the number of inversions in", filename, "is: ", cnt
    print check(ret) #,"\nList:\n",ret
        
if __name__ == "__main__":
    filename = "Q8.txt"
    inList   = readFile(filename)
    capacity = len(inList)
    
    t, SacM  = time.time(), SortAndCount_Merge()
    cnt, ret = SacM.sortAndCount(inList)
    printAnswer("Merge", time.time() - t, filename, cnt, ret)
    
    t, SacQ  = time.time(), SortAndCount_QSort()
    cnt, ret = SacQ.sortAndCount(inList)
    printAnswer("Qsort", time.time() - t, filename, cnt, ret)

事情，大概是這樣的——

官方一點的解釋呢就是：

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/224382.html

標籤：其他

上一篇：2020秋招面試經驗匯總，已入職位元組跳動，附上我的面經和復習資料！

下一篇：【Unity】Post-process后處理之Color Grading