使用归并排序对未排序的单词数组进行排序

Question

我试图使用归并排序和分治法，通过获取用户提供的随机单词来实现。我将用户输入的单词分成两个数组：

import math

inputted_sentence = input("Enter your sentence here: \n")
separated_inputs = [word.lower() for word in inputted_sentence.split()]
inputs_length = int(len(separated_inputs))


#separate the arrays
array_one = (separated_inputs[0:math.floor(int(inputs_length/2))])
array_two = (separated_inputs[math.floor(int(inputs_length/2)):inputs_length])


#grab length of the array
length_array_one = len(array_one)
length_array_two = len(array_two)

接下来，我会对它们进行排序（按字母顺序）

#first array being sorted and stored

for a in range(length_array_one-1):
    for b in range(length_array_one-a-1):
        if array_one[b] > array_one[b+1]:
            array_one[b], array_one[b+1] = array_one[b+1], array_one[b]

sorted_array_one = []

for words in array_one:
    sorted_array_one.append(words)


#second array being sorted and stored

for a in range(length_array_two-1):
    for b in range(length_array_two-a-1):
        if array_two[b] > array_two[b+1]:
            array_two[b], array_two[b+1] = array_two[b+1], array_two[b]

sorted_array_two = []

for words in array_two:
    sorted_array_two.append(words)

这张图片展示了两个数组：https://istack.dev59.com/9ZrHb.webp 现在我需要比较blue和apple，发现它更小，然后比较blue和cat，发现它更大，并且在最终的数组中占据index[2]。

接下来，rabbit与cat进行比较，它更小，再与dog比较，它更小，所以占据dog之后的数组位置。

编辑：我的第一个版本（下面）能够做到这一点，但它没有利用已排序的数组，而是重新对单词进行排序。

unsorted_final = sorted_array_one + sorted_array_two
 
 
length_unsorted_final = len(unsorted_final)
 
sorted_array_final = []
 
#Final array sorted and stored
 
for a in range(length_unsorted_final-1):
    for b in range(length_unsorted_final-a-1):
        if unsorted_final[b] > unsorted_final[b+1]:
            unsorted_final[b], unsorted_final[b+1] = unsorted_final[b+1], unsorted_final[b]
 
 
for words in unsorted_final:
    sorted_array_final.append(words)
 
print(sorted_array_final)

- PineappleExpress

---

我不确定我理解了这个...如果您已经能够单独对这两个数组进行排序，那么您所需要做的就是运行最后的合并步骤来将它们组合起来。这基本上就是归并排序的工作原理。 - Z4-tier

是的，我的第一个版本可以做到这一点：https://pastebin.com/vnh2brzw 但这是不允许的。 - PineappleExpress

已添加，感谢您的评论！ - PineappleExpress

Answer 1

归并排序使用了一个称为“合并（merge）”的辅助算法，它的工作原理是将两个已排序的数组 M 和 N 合并成一个新的、也是有序的数组 S。这是通过利用一个简单的不变量来实现的：给定这两个已排序的输入数组，它们的并集中最小的元素始终要么是 m = M[0]，要么是 n = N[0]，即使在重复删除 m 或 n 中更小的元素之后，这个不变量仍然成立。如果 m <= n，则我们可以执行 S.append(M.pop(0))，从 M UNION N 中删除 m 并将其添加到 S 的末尾，这样不变量仍然成立。我们可以一直这样做，直到两个输入列表都为空，此时 S = M UNION N 且 S 是有序的。

在Python中，您可以这样实现它：

def merge(left, right):
    result = []
    while left or right:
        if left and right:
            if left[0] <= right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        elif left:
            result.extend(left)
            break
        else:
            result.extend(right)
            break
    return result

请注意，这并不完全是归并排序。实际上，这只是归并步骤。要将其转化为完整的归并排序，您需要实现分治部分。最直接的方法是将单个输入列表反复分成两半，在每半上调用 merge_sort，然后合并它们：

def mergesort(A, depth=0):
    if (count := len(A)) > 1:
        left = mergesort(A[:count // 2], depth + 1)
        right = mergesort(A[count // 2:], depth + 1)
        print("{D}A: {A}\n{D}left: {L}\n{D}right: {R}".format(A=A, L=left, R=right, D="  " * depth))
        result = merge(left, right)
        print("{D}result: {S}".format(S=result, D="  " * depth))
        return result
    return A

（添加打印语句和depth参数仅用于演示目的。虽然这不是最有效的实现方式，但我认为这是最有表现力的方法。）

希望你看到了这个例子是如何工作的：因为merge需要2个排序好的列表，所以我们需要确保提供它们。我们通过将输入拆分成越来越小的列表来实现这一点，直到它们只包含一个元素，这个元素是显然已经排好序的。然后我们继续构建越来越长的已排序元素列表，直到整个输入完成。我认为这里的要点是：归并排序就是分而治之。或者更准确地说，归并排序是“分”部分，“合并”过程是“治”部分。

- Z4-tier