合并排序不使用切片列表

Question

我被我的算法困住了，我不知道为什么输出不是预期的。我想设计一个合并排序算法，而不需要对列表进行切片。我的想法是使用开始索引和结束索引来模拟对列表的切片。我能得到一些关于窃听器的帮助吗？ 谢谢！你知道吗

def mergeSort(alist, start, end):
    print("Splitting ",alist[start:end])
    length = end - start
    if length >1:
        mid = length//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(alist, start, start + mid)
        mergeSort(alist, start + mid, end)


        i=0
        j=0
        k=0
        while i < mid and j < mid:
            if alist[start + i] <= alist[start + mid + j]:
                alist[k]=alist[start + i]
                i=i+1
            else:
                alist[k]=alist[start + mid + j]
                j=j+1
            k=k+1

        while i < mid:
            alist[k]=alist[start + i]
            i=i+1
            k=k+1

        while j < mid:
            alist[k]=alist[start + mid + j]
            j=j+1
            k=k+1
    print("Merging ",alist[start:end])

当我尝试时：

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist,0, len(alist))

我得到了

[44, 55, 77, 31, 77, 31, 44, 55, 20]

Answer 1

一些问题：

1. 首先，引用alist[k]没有意义。如果它是alist[start + k]，那就更有意义了，因为您确实不想在窗口start:end之外更改任何内容。

2. 但是，仍然会覆盖alist中仍然需要的值。以第一个while循环的第一次迭代为例（i和j都是零）。假设alist[start + i] > alist[start + mid + j]，那么else块开始工作。你可以这样做：

   alist[start + k] = alist[start + mid + j]
   

   现在意识到alist[start + k]和alist[start + i]引用相同的值，所以这个赋值破坏了while循环下一次迭代所需的值。它永远失去了。你知道吗

   你真的需要额外的存储来管理这个列表。你知道吗

   一种方法是使用临时列表来收集合并的值。您将不再需要k索引，因为您只需要将值附加到这个新列表中。一旦它被填充，您就可以将它的值注入回alist。

3. 最后，while条件假设要合并的两半具有相同的大小，但事实并非如此。end - start可以是奇数，然后后半部分还有一个元素。因此，在这种情况下，执行while i < mid and j < end将错过最后一次迭代。你知道吗

   对于这个问题，我建议不要对相对大小或相对偏移量使用变量，比如当前的mid，而只使用绝对偏移量。

以下是处理上述问题的相关代码：

    mid = (start + end) // 2 # use absolute offsets only
    mergeSort(alist, start, mid)
    mergeSort(alist, mid, end)
    i = start # use absolute offsets only
    j = mid # use absolute offsets only
    merged = [] # temporary list
    while i < mid and j < end: # now condition is correct
        if alist[i] <= alist[j]:
            merged.append(alist[i]) # use append
            i = i + 1
        else:
            merged.append(alist[j])
            j = j + 1

    # add the remainder from the left side
    merged.extend(alist[i:mid])
    # inject back into main list
    alist[start:start+len(merged)] = merged