python - 由于变量的存储方式,合并排序实现很困难
问题描述
我有一些 C++ 和 Python 经验,但我肯定一直在努力解决这个问题。我得到了合并排序的概念,但我不明白 Python 如何存储这些值。我专注于分类只是[11, 26, 9]
为了将这个怪物分成更小的部分。
更具体地说,在下面的输出中,这行之后会发生什么: 1 1 2 (ijk) before 2nd while 循环?Python 执行哪个循环以到达附加输出的最后一行?我的主要困惑是关于 [11] 最终在 9 到 26 之间。哪个循环确实导致了这种情况?
OUTPUT:
[11, 26, 9] left;
[15, 17, 77] right;
[11, 26, 9, 15, 17, 77] myList after dividing by 2;
[11] left;
[26, 9] right;
[11, 26, 9] myList after dividing by 2;
[26] left;
[9] right;
[26, 9] myList after dividing by 2;
[26] left;
[9] right;
[26, 9] myList at zero;
1 length of right;
1 length of left;
0 0 0 (i j k) before if loop;
[9, 9] myList at else;
[26] left before 2nd while loop;
[9] right before 2nd while loop;
0 1 1 (i j k) before 2nd while loop;
[9, 26] myList 2nd while loop i;
[11] left;
[9, 26] right;
[11, 26, 9] myList at zero;
2 length of right;
1 length of left;
0 0 0 (i j k) before if loop;
[9, 26, 9] myList at else;
[11] left;
[9, 26] right;
[9, 26, 9] myList at zero;
2 length of right;
1 length of left;
0 1 1 (i j k) before if loop;
[9, 26, 9] myList at if;
[11] left before 2nd while loop;
[9, 26] right before 2nd while loop;
1 1 2 (i j k) before 2nd while loop;//WHAT HAPPENS HERE NEXT WITH [11]?
[11] left after 2nd while loop j;
[9, 26] right after 2nd while loop j;
[9, 11, 26] myList 2nd while loop j;
import scipy.io as sio, math as m, numpy as np, sympy as sym, scipy as sp
def mergeSort(myList):
if len(myList) > 1:
mid = len(myList) // 2
left = myList[:mid]
print(left, "left")
right = myList[mid:]
print(right, "right")
print(myList, "myList after dividing by 2")
mergeSort(left)
mergeSort(right)
i, j, k = 0, 0, 0
while i < len(left) and j < len(right):
print(left, "left")
print(right,"right")
print(myList, "myList at zero")
print(len(right), "length of right")
print(len(left), "length of left")
print(i, j, k, "(i j k) before if loop")
# ---------------------------------------------------------------------
if left[i] < right[j]:
print(myList, "myList at if")
myList[k] = left[i]
i += 1
else:
myList[k] = right[j]
print(myList, "myList at else")
j += 1
k += 1
# -------------------------------------------------------------------------
print(left, "left before 2nd while loop")
print(right, "right before 2nd while loop")
print(i, j, k, " (i j k) before 2nd while loop")
# ------------------------------------------------------------------------
while i < len(left):
myList[k] = left[i]
i += 1
k += 1
print(myList, "myList 2nd while loop i")
while j < len(right):
myList[k] = right[j]
j += 1
k += 1
print(left, "left after 2nd while loop j")
print(right, "right after 2nd while loop j")
print(myList, "myList 2nd while loop j")
myList = [11,26,9,15,17,77]
mergeSort(myList)
print(myList)
解决方案
我不确定我是否完全理解你的问题,所以如果我的回答不能满足你的问题,请纠正我。
当您调用 mergeSort() 时,长度为 3,因此输入分为左 [11] 和右 [26, 9]。此拆分不会以任何方式影响输入 myList [11, 26, 9]。
在mergesort内部调用之后left仍然是[11],但是right变成了[9, 26]。
然后第一个 while 循环用 9 覆盖 myList 中的第一个值。在第二次迭代中,它用 11 覆盖 myList 的第二个值。left 和 right 都不受此影响,因此它们仍然保持 left [11] 和 right [9, 26]。(i, j, k) 现在是 (1, 1, 2),所以第一个 while 循环结束。
第二个while循环被跳过,所以那里没有变化。
在第三个循环中,myList 的剩余第三个值被右侧第二个位置的值 26 覆盖。
这结束了 mySort(...) 的原始调用,并且在此调用之外可以使用修改后的列表。
这是否满足您的问题?
PS:我知道这不是您的目标,但由于 python 不是一种性能良好的语言,请尝试使用内置函数或库,因为它们中的大多数都是用 C/C++ 编译的,因此比自行实现的版本快得多: )
推荐阅读
- amazon-web-services - DynamoDB 查询/扫描仅返回项目的子集
- python - 将行与特定字符串匹配以提取值 Python Regex
- swift - 如何删除所有对象并停止对领域数据库的所有写入?
- r - R中列值的条件排序/重新排序
- opengl - 带有 python 和 pygame 的 OpenGL 模型
- pandas - Pandas - 根据值过滤行
- apache - 防止 apache2 / http2 作为 Docker 容器的守护进程运行?
- javascript - 需要帮助使用 js 将 rel 添加到 img 标签
- anypoint-studio - 如果值满足特定条件,如何仅包含键
- javascript - 可以传递给 Puppeteer page.goto(url) 函数的 URL 字符串中的最大字符数是多少