algorithm - k = k + 1 是什么意思？对于用解决方案对实际问题进行分类有什么建议吗？

Question

我了解归并排序实现的大部分内容。但是我对第二个和第三个 while 循环下的 k = k + 1 有点困惑。我认为无论我们是否执行 k = k + 1，k 都会再次更新为 0。但是在我评论 k = k + 1 之后结果会有所不同。有人可以向我解释一下吗？

有什么建议可以让我在线查找一些实际的排序问题(以及解决方案)？

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

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1## what is the meaning of k += 1?
            # if we don't have k += 1 then the result will be
            #Merging  [0, 1, 2, 17, 26, 54, 55, 2, 0, 93, 2, 0]
            #[0, 1, 2, 17, 26, 54, 55, 2, 0, 93, 2, 0]

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

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

Answer 1

• i 代表当前位置在左半边
• j代表当前位置在右半边
• k 表示当前在“合并”数组中的位置

第一个 while 继续，直到其中一个索引(i 和 j)超过相应数组的长度。

第二个 while 和第三个 while 行为相同 - 将两半中的剩余项目复制到“合并”中。其中一半已经空了。

k 的增量在所有 3 个中都具有相同的含义，而您从其中一半中取出一个元素并将其放入并移动到下一个索引。

我不确定现在流行什么，但在 LeetCode 上有一堆标有“sort”的问题 - 其中许多也应该有解决方案。

---

以下是有关返回值(此处不相关)和按引用或值传递(相关)的一些信息:

• https://www.quora.com/Are-arguments-passed-by-value-or-by-reference-in-Python

• Python procedure return values

如果您对该主题感到困惑，我会查看更多资源。