Python 不分片合并排序

Question

我曾尝试在不使用切片的情况下编写快速排序实现，但我运行在运行时中途遇到问题 - 想知道是否有人可以告诉我哪里出错了

我添加了一些打印语句（已注释掉），因此您可以看到每个阶段前后发生的情况：

def mergesort(arr, l, r):

    #print('start: ', arr[l:r])

    if len(arr[l:r]) <=1:
        return arr[l:r]

    mid = l + (r-l) // 2
    left    = mergesort(arr, l, mid)
    right   = mergesort(arr, mid, r)

    l_idx = l
    r_idx = mid
    final = []

    while l_idx < mid and r_idx < r:
        if arr[l_idx] <= arr[r_idx]:
            final.append(arr[l_idx])
            l_idx+=1
        else:
            final.append(arr[r_idx]) 
            r_idx+=1


    for val in arr[l_idx:mid]:
        final.append(val)

    for val in arr[r_idx:r]:
        final.append(val)

    #print('final: ', final[l:r])
    #print()
    #print()
    return final 



    print(merge([0, 9, 3, 7, 4, 2, 6, 1], 0, 8))

我得到的值表明，左侧效果很好，但右侧效果不佳。这很好奇，因为它似乎适用于左侧的右侧...

标准输出是：

start:  [0, 9, 3, 7, 4, 2, 6, 1]
start:  [0, 9, 3, 7]
start:  [0, 9]
start:  [0]
start:  [9]
final:  [0, 9]


start:  [3, 7]
start:  [3]
start:  [7]
final:  []


final:  [0, 3, 7, 9]


start:  [4, 2, 6, 1]
start:  [4, 2]
start:  [4]
start:  [2]
final:  []


start:  [6, 1]
start:  [6]
start:  [1]
final:  []


final:  []


final:  [0, 4, 2, 6, 1, 9, 3, 7]

Answer 1

主要问题是您从不使用从递归调用返回的 left 和 right 列表，但您需要这些，因为 arr 没有更改任何一个被那些电话咬了。当您更正此问题时，您还应该知道此结果列表将从索引 0 开始，与您通过递归调用传递的 l 的值无关。所以这意味着实际的合并循环需要从索引 0 开始，而不是 l.

这是递归调用后您应该立即拥有的代码：

# concatenate the left and right results into arr
arr = left + right

# realign the indexes with the new arr
mid -= l 
r -= l
l_idx = 0
r_idx = mid

有了这个变化 it will work。

注意：你说你想在不切片的情况下执行此操作，但请注意你仍然切片：每当你使用 : 符号时，如 arr[l:r]，你切片。

Python 不分片合并排序

Python Merge sort without slicing

sorting

algorithm

mergesort

python-3.x