m0_54391351 2021-03-15 10:31 采纳率: 50%
浏览 28
已采纳

python实现二归并排序时,为什么只是交换了and两边条件的位置,一个能出结果,一个就报错?

def merge(s1,s2,s):
    i = j = 0
    while i+j<len(s):
        if j==len(s2) or (i<len(s1) and s1[i]<s2[j]):
            s[i+j] = s1[i]
            i += 1
        else:
            s[i+j] = s2[j]
            j += 1

def merge_sort(s):
    n = len(s)
    if n < 2:
        return
    mid = n // 2
    s1 = s[0:mid]
    s2 = s[mid:n]
    merge_sort(s1)
    merge_sort(s2)
    merge(s1,s2,s)


s = [24,17,40,28,13,14,22,32,40,21,48,4,47,8,37,18,88,56,79,35,0,66,156]
merge_sort(s)
print(s)

这个代码是能正常运行的,结果是:

[0, 4, 8, 13, 14, 17, 18, 21, 22, 24, 28, 32, 35, 37, 40, 40, 47, 48, 56, 66, 79, 88, 156]

但是我只是改变了if 语句中 and两边语句 的位置,结果就报错了

 if j==len(s2) or (s1[i]<s2[j] and i<len(s1)):
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-9-5ac2ee75fd0c> in <module>()
     22 
     23 s = [24,17,40,28,13,14,22,32,40,21,48,4,47,8,37,18,88,56,79,35,0,66,156]
---> 24 merge_sort(s)
     25 print(s)

<ipython-input-9-5ac2ee75fd0c> in merge_sort(s)
     16     s1 = s[0:mid]
     17     s2 = s[mid:n]
---> 18     merge_sort(s1)
     19     merge_sort(s2)
     20     merge(s1,s2,s)

<ipython-input-9-5ac2ee75fd0c> in merge_sort(s)
     16     s1 = s[0:mid]
     17     s2 = s[mid:n]
---> 18     merge_sort(s1)
     19     merge_sort(s2)
     20     merge(s1,s2,s)

<ipython-input-9-5ac2ee75fd0c> in merge_sort(s)
     18     merge_sort(s1)
     19     merge_sort(s2)
---> 20     merge(s1,s2,s)
     21 
     22 

<ipython-input-9-5ac2ee75fd0c> in merge(s1, s2, s)
      2     i = j = 0
      3     while i+j<len(s):
----> 4         if j==len(s2) or (s1[i]<s2[j] and i<len(s1)):
      5             s[i+j] = s1[i]
      6             i += 1

IndexError: list index out of range
  • 写回答

1条回答 默认 最新

  • cclxpp123 2021-03-15 12:37
    关注

    越界后, and的短路特性使得第二个条件没被执行. 另外我觉得没必要写这么复杂的条件, 可以在最后把剩下的放进去, 代码比较对称, 逻辑比较清晰:

    def merge(s1, s2, s):
        i = j = 0
        while i < len(s1) and j < len(s2):
            if s1[i] < s2[j]:
                s[i+j] = s1[i]
                i += 1
            elif s1[i] >= s2[j]:
                s[i+j] = s2[j]
                j += 1
        while i < len(s1):
            s[i+j] = s1[i]
            i += 1
        while j < len(s2):
            s[i+j] = s2[j]
            j += 1

    或者直接舍弃指标i和j, 用列表的pop移动.

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?