时间戳

首页 > 解决方案 > 无法跟踪我的合并排序算法（Python 3）

python - 无法跟踪我的合并排序算法（Python 3）

问题描述

我在 Python 3 中编写了一个简短的合并排序算法。我很难理解它是如何实现正确结果的，因为当我尝试跟踪它的逻辑步骤时，我最终会得到一个乱序列表。注释代码如下所示。

我具体指的是代码的合并部分。三个“while”循环。

让我用一个例子来说明什么让我感到困惑。我在注释中解释了细节。

提前感谢您的时间和帮助。

假设我们要合并两个数组。

left = [2,6]
right = [4,8]

def merge_sort(array):

    if len(array) > 1:

        middle = len(array)//2

        left = array[:middle]
        right = array[middle:]

        merge_sort(left)
        merge_sort(right)

        i = j = k = 0

        while i < len(left) and j < len(right):

            # i.e. if 2 < 4
            if left[i] < right[j]: 

                # The first index of the array is assigned the value 2
                array[k] = left[i]  

                # i = 1 now
                i += 1

            # The 'else' statement is not executed, because the 'if' statement was.
            else:

                array[k] = right[j]
                j += 1

            # k = 1 now
            k += 1 

        # The 'while' loop below assigns '6' as the value for index 1 of the array and terminates.
        # k = 2 now
        while i < len(left):
       
            array[k] = left[i]
            i += 1
            k += 1

        # The last 'while' loop assigns '4' and '8' to indexes 2 and 3 of the array, respectively.
        while j < len(right):

            array[k] = right[j]
            j += 1
            k += 1

        # The algorithm terminates and from what I can see I should end up with the array of [2,6,4,8].
        # I do not, however. It is sorted in ascending order and I cannot see where I'm making a mistake.

标签： pythonpython-3.xalgorithmsortingmergesort

解决方案

首先，小心你的措辞，要明确合并排序不是合并不同的数组，合并排序巧妙地将一个未排序的数组解构为子数组（在我们的例子中是左和右）并将它们单独排序并将它们合并回一个再次进行最终排序的数组。换句话说，你传递给这个函数一个未排序的数组，它返回一个排序的数组。如果你需要合并两个数组，你会在调用它之前这样做。

合并排序

“合并排序是一种递归算法，它不断地将列表分成两半。如果列表为空或有一项，则按定义排序（基本情况）。如果列表有多个项，我们将列表拆分并递归地在两半上调用合并排序。一旦两半排序后，就会执行称为合并的基本操作。合并是获取两个较小的排序列表并将它们组合成一个单独的排序新列表的过程。 "

调试/分析代码

为了帮助理解它的工作原理（和调试），至少注入打印注释以最好地更详细地显示正在发生的事情。我采用了您编写的内容并添加了打印注释，并向函数传递了一个字符串，以帮助确定它正在排序的数组（左或右）。您可以看到拆分排序和合并，因为它通过将数组拆分为大小为一并在此过程中合并排序的子数组等来完成排序...

def merge_sort(array,type):
    print('merge_sort =>' + type)
    if len(array) < 2:
        print('Array < 2 nothing changed')
        return array
    middle = len(array) // 2
    left = array[:middle]
    right = array[middle:]
    print('splitting : ' + str(array))
    merge_sort(left,'left')
    merge_sort(right,'right')
    i = j = k = 0
    print('sorting.. Left/Right:' + str(left) + str(right))
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            print(' - left[i] < right[j] ('+ str(left[i]) + ' < ' + str(right[j]) + ') set array[' + str(k) + '] = ' + str(left[i]) + '')
            array[k] = left[i]
            i += 1
        else:
            print(' - else left[i] >= right[j] ('+ str(left[i]) + ' >= ' + str(right[j]) + ') set array[' + str(k) + '] = ' + str(right[j]) + '')
            array[k] = right[j]
            j += 1
        k += 1
    while i < len(left):
        print(' - WHILE i < len(left), ('+str(i) +' < '+str(len(left))+'), set array[' + str(k) + '] = ' + str(left[i]) + '')
        array[k] = left[i]
        i += 1
        k += 1
    while j < len(right):
        print(' - while j < len(right) ('+str(j) +' < ' + str(len(right)) + '), set array[' + str(k) + '] = ' + str(right[j]) + '')
        array[k] = right[j]
        j += 1
        k += 1
    print("returning.." + str(array))
    return array

arr = [2,6,4,8]
result = merge_sort(arr,'full')
print(result)

它提供以下输出：

merge_sort =>full
splitting : [2, 6, 4, 8]
merge_sort =>left
splitting : [2, 6]
merge_sort =>left
Array < 2 nothing changed
merge_sort =>right
Array < 2 nothing changed
sorting.. Left/Right:[2][6]
 - left[i] < right[j] (2 < 6) set array[0] = 2
 - while j < len(right) (0 < 1), set array[1] = 6
returning..[2, 6]
merge_sort =>right
splitting : [4, 8]
merge_sort =>left
Array < 2 nothing changed
merge_sort =>right
Array < 2 nothing changed
sorting.. Left/Right:[4][8]
 - left[i] < right[j] (4 < 8) set array[0] = 4
 - while j < len(right) (0 < 1), set array[1] = 8
returning..[4, 8]
sorting.. Left/Right:[2, 6][4, 8]
 - left[i] < right[j] (2 < 4) set array[0] = 2
 - else left[i] >= right[j] (6 >= 4) set array[1] = 4
 - left[i] < right[j] (6 < 8) set array[2] = 6
 - while j < len(right) (1 < 2), set array[3] = 8
returning..[2, 4, 6, 8]

这会产生一些东西。像这样： 在此处输入图像描述

参考资料： 如何在 python 中合并数组？ https://runestone.academy/runestone/books/published/pythonds/SortSearch/TheMergeSort.html

推荐阅读