python - 合并排序单词列表

Question

我已经使用 codereview 上的帖子实现了归并排序算法。它在整数列表上运行良好，但我认为需要一个更实用的应用程序。所以我下载了一个包含随机英文单词的文本文件并尝试对它们进行排序。

但是它什么也没做。

def merge_sort(seq):
    if len(seq) == 1:
        return seq
    else:
        # recursive step. Break the list into chunks of 1
        mid_index = len(seq) // 2
        left  = merge_sort( seq[:mid_index] )
        right = merge_sort( seq[mid_index:] )

    left_counter, right_counter, master_counter = 0, 0, 0

    while left_counter < len(left) and right_counter < len(right):
        if left[left_counter] < right[right_counter]:
            seq[master_counter] = left[left_counter]
            left_counter += 1
        else:
            seq[master_counter] = right[right_counter]
            right_counter += 1

        master_counter += 1

    # Handle the remaining items in the remaining_list
    # Either left or right is done already, so only one of these two
    #    loops will execute

    while left_counter < len(left):  # left list isn't done yet
        seq[master_counter] = left[left_counter]
        left_counter   += 1
        master_counter += 1

    while right_counter < len(right):  # right list isn't done yet
        seq[master_counter] = right[right_counter]
        right_counter   += 1
        master_counter  += 1

    return seq

我认为问题在于它处理的是列表列表而不是单个列表。该函数也无法知道排序的基础是什么。对吗？

我想这样调用它

with open('words.txt') as f:
    list_of_words = f.read().splitlines()
    new = merge_sort(list_of_words)
    print(new == sorted(list_of_words, key=len))

Answer 1

正如您所指出的，问题是 merge_sort 无法知道排序的基础。您可以更改 merge_sort 以接受一个附加参数，该参数返回序列中每个元素的键，就像 sorted 一样。做:

def merge_sort(seq, key=lambda x: x):

然后将比较更改为调用传递的函数而不是直接比较元素:

if key(left[left_counter]) < key(right[right_counter]):
    seq[master_counter] = left[left_counter]
    left_counter += 1
else:
    seq[master_counter] = right[right_counter]
    right_counter += 1

最后将 key 传递给递归调用:

left  = merge_sort( seq[:mid_index], key )
right = merge_sort( seq[mid_index:], key )

通过这些更改，它将按您预期的那样工作:

merge_sort([4, 6, 2, 1]) # [1, 2, 4, 6]
merge_sort(['foo', 'a', 'bar', 'foobar'], key=len) # ['a', 'bar', 'foo', 'foobar']

但要注意的是，结果与 sorted 不同，因为 merge_sort 不是 stable :

merge_sort(['foo', 'a', 'bar', 'foobar'], key=len) # ['a', 'bar', 'foo', 'foobar']
sorted(['foo', 'a', 'bar', 'foobar'], key=len) # ['a', 'foo', 'bar', 'foobar']