递归冒泡排序Python与R相比不起作用

Question

我是Python的新手。相同的代码在R上工作得很好，但我不明白为什么它在Python中不能工作.

Python：

#swap pair
def swap_pair(xpair):
    if xpair[0] > xpair[1]:
        xpair.reverse()
    else:
        xpair
    return xpair

#swap_pass
def swap_pass(xlist):
    for i in range(0,len(xlist)-1):
        xlist[i:i+2] = swap_pair(xlist[i:i+2])
    return xlist

def bubble_sort(data):
    newdata = swap_pass(data)
    if data == newdata:
        return(newdata)
    else:
        return bubble_sort(newdata)

test = [100,6,5,3,2,1]
bubble_sort(test)

出局: 6，5，3，2，1,100

下面是R中的相同代码，它们工作得很好：

swap_if_larger = function(pair) {
  if( pair[1] > pair[2] )
    return(rev(pair)) else
      return(pair)
}

swap_pass = function(vec) { 
  for(i in seq(1, length(vec)-1)) { 
    vec[i:(i+1)] = swap_if_larger(vec[i:(i+1)]) 
  }
  return(vec)
}

bubble_sort = function(vec) {
  new_vec = swap_pass(vec)
  if( isTRUE(all.equal(new_vec, vec)) ) { 
    return(new_vec) 
  } else {
    return(bubble_sort(new_vec))
  }
}

test = c(100,6,5,3,2,1)
bubble_sort(test)

Bubble_sort(测试) 1 1 2 3 5 6 100

你能帮我吗？

Answer 1

您的swap_pass正在适当地改变data并返回它。所以在bubble_sort中，data和new_data都是对同一个list的引用。如果要避免这种情况，请在调用时复制，因此实际上有两个不同的list：

def bubble_sort(data):
    newdata = swap_pass(data[:])  # Empty slice copies data before passing to swap_pass
    if data == newdata:
        return(newdata)
    else:
        return bubble_sort(newdata)

或者，让swap_pass为您做副本，这样调用者就不需要考虑它(这通常是Pythonic的方法；Python函数要么变异参数，什么都不返回，要么返回一个新值并保持参数不变，他们不会变异和返回)：

def swap_pass(xlist):
    xlist = xlist[:]  # Add shallow copy before doing work
    for i in range(0,len(xlist)-1):
        xlist[i:i+2] = swap_pair(xlist[i:i+2])
    return xlist