无法跟踪我的合并排序算法 (Python 3)

Question

我在 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.

Answer 1

在您的注释中，您似乎过早地退出了第一个 while 循环，您在一个运行后停止，而代码实际上执行了 3 运行秒。以下是您将如何了解 wgat 实际发生的情况：

你运行通过一次，然后你有k=1、i=1和j=0、
所以你再走一遍这个循环（这次是执行else，把4赋给数组的索引1，现在k=2，i=1和j=1
所以你运行第三次通过循环，执行 if，最后 k=3、i=2 和 j=1，所以你得到在第一个 while.

Answer 2

首先，请注意您的措辞，要明确合并排序不会合并不同的数组，合并排序巧妙地将单个未排序的数组解构为子数组（在我们的例子中是左数组和右数组）并分别对它们进行排序并合并他们再次回到一个单一的阵列与最后的排序。换句话说，您向该函数传递了一个未排序的数组，而它 returns 是一个已排序的数组。如果你需要合并两个数组，你会在调用它之前这样做。

合并排序

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

Debug/Analyze代码

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

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]

这会产生一些 apx。像这样：

参考资料： https://runestone.academy/runestone/books/published/pythonds/SortSearch/TheMergeSort.html

无法跟踪我的合并排序算法 (Python 3)

Trouble tracing my Merge sort algorithm (Python 3)

python

sorting

algorithm

mergesort

python-3.x