为什么我的合并排序算法不起作用？如何让它根据字符串的第一个字符进行排序？

Question

我正在尝试通过合并排序函数运行字符串列表（运动队）以按字母顺序对其进行排序。归并排序算法在技术上是可行的，但并不完全可行。它按字母顺序对 15 支球队中的三支进行排序，并剔除其余球队。我对数据结构和算法很陌生，所以我很难弄清楚。以下是我的算法：

def mergeSort(arr):
    if len(arr[0]) > 1:
        left_arr = arr[:len(arr)//2]
        right_arr = arr[len(arr)//2:]

        mergeSort(left_arr)
        mergeSort(right_arr)

        i = 0
        j = 0
        k = 0

        while i < len(left_arr) and j < len(right_arr):
            if left_arr[i] < right_arr[j]:
                arr[k] = right_arr[j]
                i += 1
            else:
                arr[k] = right_arr[j]
                j += 1
            k += 1

        while i < len(left_arr):
            arr[k] = left_arr[i]
            i += 1
            k += 1

        while j < len(right_arr):
            arr[k] = right_arr[j]
            j += 1
            k += 1

这是我的列表的示例（短得多）： [“鸭子队”、“喷气机队”、“小牛队”、“骑士队”、“流浪者队”] 它将其分类为： [‘勇敢者’、‘双胞胎’、‘双胞胎’、‘双胞胎’、‘双胞胎’、‘双胞胎’、‘双胞胎’、‘双胞胎’]

我假设该算法是根据字符串的大小或类似的东西进行排序，并且需要根据每个单独字符串的第一个索引进行排序，我只是不知道如何做到这一点。非常感谢。

PS我不想使用python的排序功能。我知道这会更容易，但我是一名本科生，想通过自己编写算法来学习材料。

Answer 1

您在合并步骤中错误地分配了 right_arr 中的元素。

def mergeSort(arr):
    if len(arr) > 1:  
        left_arr = arr[:len(arr)//2]
        right_arr = arr[len(arr)//2:]
        mergeSort(left_arr)  
        mergeSort(right_arr) 

        i = j = k = 0  

        while i < len(left_arr) and j < len(right_arr):
            if left_arr[i][0] < right_arr[j][0]: 
                arr[k] = left_arr[i]  
                i += 1
            else:
                arr[k] = right_arr[j]  
                j += 1
            k += 1

        while i < len(left_arr):
            arr[k] = left_arr[i]
            i += 1
            k += 1

        while j < len(right_arr):
            arr[k] = right_arr[j]
            j += 1
            k += 1

# Example
teams = ['Ducks', 'Jets', 'Mavericks', 'Knights', 'Rangers']
mergeSort(teams)
print(teams)