在Python中使用merge sortquick sort对类对象的属性进行排序。

Question

我有这个学生班

class Student:
    def __init__(self, name, id):
        self.name = name
        self.id = id

我需要对学生类中的一些对象进行排序，特别是使用 合并快速排序 来排序 id 而预期的结果是学生姓名的数组。因此，如果我有这些对象。

s1 = Student("Andy", 4)
s2 = Student("Bob", 3)
s3 = Student("Sophie", 2)
s4 = Student("Tony", 1)
s5 = Student("Jerry", 5)

而预期的结果是：

result = ["Tony", "Sophie", "Bob", "Andy", "Jerry"]

我不知道我是否需要创建一个对象数组 或者我把排序函数放在哪里。

有什么想法吗？

Answer 1

你可以使用是创建一个学生的列表。假设你将自己写合并排序函数，现在你有一个这样的函数定义。

def merge_sort(students_array)

现在这个函数应该以一种特殊的方式来实现 你可以根据id来比较元素。

要做到这一点，你有几个选择。

1. 有一个 __eq__ (函数支持 a == b), __le__ (函数支持 a <= b), __ge__ (函数支持 a >= b), __gt__ (函数支持 a > b), __lt__ (函数支持 a < b). 你可以只用"<，>，="IMO，但这些都是你要考虑的函数。学生需要实现它们，这样就可以通过比较两个学生的ID来进行比较--这可能是最pythonic的方式。

实例实现。

class Student:
    def __init__(self, name, id):
        self.name = name
        self.id = id
    def __eq__(self, other):
        return self.id == other.id

    def __gt__(self, other):
        return self.id > other.id

    def __lt__(self, other):
        return self.id < other.id

...
# getting a list of Students, not only ids
def merge_sort(students_array):
...
    # example compare in the sort function
    # this will be translated to: students_array[i].__gt__(students_array[j])
    # which will return: students_array[i] > students_array[j]
    if students_array[i] > students_array[j]:
        # do something
...

def main():

    s1 = Student("Andy", 4)
    s2 = Student("Bob", 3)
    s3 = Student("Sophie", 2)
    s4 = Student("Tony", 1)
    s5 = Student("Jerry", 5)
    students_array = [s1, s2, s3, s4, s5]
    merge_sort(students_array)

关于python dunder函数的好文档。https:/docs.python.org3libraryoperator.html

希望能帮到你

Answer 2

将其转换为对数组，然后应用合并排序，并将数组作为参数传入。

def merge(arr, l, m, r): n1 = m - l + 1 n2 = r- m

# create temp arrays 
L = [0] * (n1) 
R = [0] * (n2) 

# Copy data to temp arrays L[] and R[] 
for i in range(0 , n1): 
    L[i] = arr[l + i] 

for j in range(0 , n2): 
    R[j] = arr[m + 1 + j] 

# Merge the temp arrays back into arr[l..r] 
i = 0    # Initial index of first subarray 
j = 0    # Initial index of second subarray 
k = l    # Initial index of merged subarray 
enter code here

while i < n1 and j < n2 : 
    if L[i][1] <= R[j][1]: // here you need to compare id
        arr[k] = L[i] 
        i += 1
    else: 
        arr[k] = R[j] 
        j += 1
    k += 1
# Copy the remaining elements of L[], if there 
# are any 
while i < n1: 
    arr[k] = L[i] 
    i += 1
    k += 1
# Copy the remaining elements of R[], if there 
# are any 
while j < n2: 
    arr[k] = R[j] 
    j += 1
    k += 1

def mergeSort(arr,l,r): 
      if l < r: 
        # Same as (l+r)//2, but avoids overflow for 
        # large l and h 
        m = (l+(r-1))//2
        # Sort first and second halves 
        mergeSort(arr, l, m) 
        mergeSort(arr, m+1, r) 
        merge(arr, l, m, r) 

arr = [( "sdas",1), ( "asd3",3), ( "asd1",2)] 
n = len(arr) 
print ("Given array is") 
for i in range(n): 
    print ("%s" %arr[i][0]), 

mergeSort(arr,0,n-1) 
print ("\n\nSorted array is") 
for i in range(n): 
    print (arr[i]), 
#or you can use predefined sort function like this
def sortSecond(val): 
    return val[1] 
arr = [( "sdas",1), ( "asd3",3), ( "asd1",2)] 
# sorts the array in ascending according to 
# second element 
arr.sort(key = sortSecond) 
print(arr)