归并排序中的递归和 While 循环

Question

所以我尽我最大的努力想象这个合并排序过程将如何进行，但我坚持使用递归和三重 While 循环，以及这些递归如何影响数组的当前划分 [1, 9,7,10,11] 上半场和 [8,3,2,5,6,4] 下半场。我可以理解代码的前半部分，但是在尝试遵循这些 while 循环的流程时我迷路了。非常感谢您的回答！！！

def merge_sort(数组):

if len(array) > 1:
    start_mid = array[:len(array)//2]
    mid_end = array[len(array)//2:]

    #recusion process
    merge_sort(start_mid)
    merge_sort(mid_end)


    left_ind = 0
    right_ind = 0
    merged_ind = 0
    while left_ind < len(start_mid) and right_ind < len(mid_end):
        if start_mid[left_ind] < mid_end[right_ind]:
            array[merged_ind] = start_mid[left_ind]
            left_ind += 1
        else:
            array[merged_ind] = mid_end[right_ind]
            right_ind += 1
        merged_ind += 1
    while left_ind < len(start_mid):
        array[merged_ind] = start_mid[left_ind]
        left_ind += 1
        merged_ind += 1
    while right_ind < len(mid_end):
        array[merged_ind] = mid_end[right_ind]
        right_ind += 1
        merged_ind += 1

array_test = [1,9,7,10,11,8,3,2,5,6,4]

merge_sort(array_test)

打印(array_test)

Answer 1

我会说在白板或其他东西上写下递归的每次迭代，因为您的代码非常简单。如果你把它画出来，你会看到代码正在拆分数组，直到它不能再拆分，然后运行循环这些循环来改变两半的顺序，但又回到下一个最大的一半。

一种描述方式是每个循环负责特定的 feature/situation 并且递归调用会将列表的当前版本保存到运行较小部分的相同功能在您的列表中。

第一个循环将处理您当前的数组状态，并根据哪一个先进行对两半进行排序，直到其中一个完成。第二个循环处理左边还有更多元素要经过的情况。

（即 [4,5], [1,2,3] ）

第三个循环处理右侧还有更多元素要通过的情况

（即 [1,2], [3,4,5] ）

编辑：

如果我问的关于数组横向排列的顺序是正确的，那么它是：

[1,9,7,10,11] , [8,3,2,5,6,4] ->[1,9,] , [7,10,11] -> [1 ] , [9] (和排序) -> [7] , [10,11] -> (跳过排序 7) -> [10] , [11] (和排序) -> (排序 [7] , [10 ,11]) -> (排序 [1,9,] , [7,10,11]) -> 等等

基本上它会将这对数组中的第一个数组切成两半，并且只将第一个数组切成两半，直到你能够将它的长度减少到 1。完成后，第一个数组length 1 回来了，你现在终于可以开始查看一对中的第二个数组了。一旦你完成了那对和 return 从那个递归调用你就会完成上面层的“第一个”数组，而现在开始那对的第二个数组。

一旦你对第二个数组进行递归调用，你将重复对第一个数组进行优先排序的过程

归并排序中的递归和 While 循环

Recursions and While loops in Merge Sort

python

sorting

recursion

mergesort

while-loop