串列串列的就地快速排序

我的任務是使用快速排序就地對資料進行排序。輸入是一個串列串列（name、score1、score2）。

資料應按 score1 降序排序，然后（如果相等）按 score2 升序排序，然后（如果相等）按名稱升序排序。

示例輸入：

5
antony 4 100
jack 6 1000
jerry 2 90
ricky 2 90
timy 4 80

預期輸出：

jack
timy
antony
jerry
ricky

到目前為止，我已經撰寫了快速排序演算法并使用一些自定義輸入對其進行了測驗，但我不知道如何比較串列串列中的值。或者還有其他方法可以進行這種比較嗎？

import random

def compare(l1, l2):
    if l1[1] > l2[1]:
        return True
    elif l1[1] == l2[1] and l1[2] < l2[2]:
        return True
    elif l1[2] == l2[2] and l1[1] == l2[1] and l1[0] > l1[0]:
        return True
    else:
        return False

def quicksort(A, l=0, r=None):
    if r is None:
        r = len(A) - 1
    # end = len(array) - 1
    if l >= r:
        return
    else:
        q = random.choice(A[l:r   1])
        i = l
        j = r
        while i <= j:
            while compare(q, A[i]):
                i  = 1
            while compare(A[j], q):
                j -= 1
            if i <= j:
                A[i], A[j] = A[j], A[i]
                i  = 1
                j -= 1
                quicksort(A, l, j)
                quicksort(A, i, r)
    return A

def read_input():
    k = int(input())
    values = []
    while k > 0:
        n = input().split()
        values.append(n[0])
        values.append(n[1])
        values.append(n[2])
        k -= 1
    return values

uj5u.com熱心網友回復：

您的代碼中存在以下問題：

• read_input讀取一維串列中的所有值，即它不創建三元組串列

• read_input不會將分數轉換為int資料型別，而是將它們保留為字串，這將影響它們的比較方式compare

  要解決這兩個問題，請更改回圈體read_input：

  name, score1, score2 = input().split()
  values.append([name, int(score1), int(score2)])
  k -= 1
  

• compareTrue當第一個引數應該排在第二個引數之后時回傳。當您打電話時，compare您將True其視為一條訊息，不要交換。但是您按照引數出現在輸入中的順序傳遞引數，這意味著您應該在獲得True. 所以這里的代碼是錯誤的。通過以相反的順序傳遞引數來修復。

• 的遞回呼叫quickSort是在錯誤的時間進行的。這些呼叫不應在回圈期間完成，而應在回圈之后完成。

• quicksort有一個return無串列和一個return A有串列。這并不一致。就地而言，quicksort不回傳串列更加pythonic ，所以改變那個finalreturn。呼叫者應該將它傳遞的串列作為引數，該串列將被排序。

• compare字串比較中有錯字：有l1[0] > l1[0]（兩個運算元相同），應該是l2[0] > l1[0]

這是帶有上述更正的代碼：

def compare(l1, l2):
    if l1[1] > l2[1]:
        return True
    elif l1[1] == l2[1] and l1[2] < l2[2]:
        return True
    elif l1[2] == l2[2] and l1[1] == l2[1] and l2[0] > l1[0]:
        return True
    else:
        return False

def quicksort(A, l=0, r=None):
    if r is None:
        r = len(A) - 1
    if l >= r:
        return
    else:
        q = random.choice(A[l:r   1])
        i = l
        j = r
        while i <= j:
            while compare(A[i], q):  # args swapped
                i  = 1
            while compare(q, A[j]):  # args swapped
                j -= 1
            if i <= j:
                A[i], A[j] = A[j], A[i]
                i  = 1
                j -= 1
        quicksort(A, l, j)  # Fixed indentation
        quicksort(A, i, r)
    return  # Don't return A

def read_input():
    k = int(input())
    values = []
    while k > 0:
        name, score1, score2 = input().split()
        # Append a triple, and convert the scores to int:
        values.append([name, int(score1), int(score2)])
        k -= 1
    return values

標籤：Python算法排序快速排序

上一篇：基于與其他串列的交集對串列進行部分排序

下一篇：如何按此順序對物件陣列進行排序？