合并排序 Python 2.7 倍

Question

函数 merge() 工作正常但 merge_sort 不是，使用 merge_sort() 后 ls 和 rs 的值没有改变。请帮助找出问题所在，我已经坚持了几个小时。

def merge_sort(arr):


  def merge(sub_arr,p,q):

    L = []
    R = []

    for i in range(p):
        L.append(sub_arr[i])
        #print L

    for i in range(q-p):
        R.append(sub_arr[p+i])
        #print R

    L.append('n')
    R.append('n')

    j=k=0

    for i in range(q):

        if L[j] < R[k] :

            sub_arr[i] = L[j]
            j += 1

        else:

            sub_arr[i] = R[k]
            k += 1


  if len(arr) > 1 :

    ls = arr[:len(arr)/2]
    rs = arr[len(arr)/2:]


    merge_sort(ls)
    #print ls
    merge_sort(rs)
    #print rs



    arr = ls + rs

    #print arr

    merge (arr,len(arr)/2,len(arr))
    #print arr




x = map(int,raw_input('Enter sequence:').strip().split())

merge_sort(x)

print x

Answer 1

问题在于行

arr = ls + rs

您不再对传递给 merge_sort 的列表调用合并，而是对副本调用它。所以原始列表没有被修改。要更正此问题，您可以在末尾使用 merge_sort 函数 return arr，然后分配 ls = merge_sort(ls)（与 rs 类似）。完成后，您的代码应该可以工作了。

正确的版本在这里..

def merge_sort(arr):
  def merge(sub_arr,p,q):
    L = []
    R = []
    for i in range(p):
        L.append(sub_arr[i])
    for i in range(q-p):
        R.append(sub_arr[p+i])
    L.append('n')
    R.append('n')
    j=k=0
    for i in range(q):
        if L[j] < R[k] :
            sub_arr[i] = L[j]
            j += 1
        else:
            sub_arr[i] = R[k]
            k += 1
  if len(arr) > 1 :
    ls = arr[:len(arr)/2]
    rs = arr[len(arr)/2:]
    ls = merge_sort(ls)
    rs = merge_sort(rs)    
    arr = ls + rs
    merge (arr,len(arr)/2,len(arr))
  return arr

这给出了预期的结果

>>> x = map(int,raw_input('Enter sequence:').strip().split())
Enter sequence:4 5 2 1 3 4 6
>>> y = merge_sort(x)
>>> print x
[4, 5, 2, 1, 3, 4, 6]
>>> print y
[1, 2, 3, 4, 4, 5, 6]

合并排序 Python 2.7 倍

Merge Sort Python 2.7x

python

mergesort