递归选择排序 Python

Question

接下来的问题里有一个需要做的递归选择排序。

def selsort(l):
    """
    sorts l in-place.
    PRE: l is a list.
    POST: l is a sorted list with the same elements; no return value.
    """                    

l1 = list("sloppy joe's hamburger place")
vl1 = l1

print l1    # should be: """['s', 'l', 'o', 'p', 'p', 'y', ' ', 'j', 'o', 'e', "'", 's', ' ', 'h', 'a', 'm', 'b', 'u', 'r', 'g', 'e', 'r', ' ', 'p', 'l', 'a', 'c', 'e']"""

ret = selsort(l1)

print l1    # should be """[' ', ' ', ' ', "'", 'a', 'a', 'b', 'c', 'e', 'e', 'e', 'g', 'h', 'j', 'l', 'l', 'm', 'o', 'o', 'p', 'p', 'p', 'r', 'r', 's', 's', 'u', 'y']"""
print vl1   # should be """[' ', ' ', ' ', "'", 'a', 'a', 'b', 'c', 'e', 'e', 'e', 'g', 'h', 'j', 'l', 'l', 'm', 'o', 'o', 'p', 'p', 'p', 'r', 'r', 's', 's', 'u', 'y']"""

print ret   # should be "None"

我知道可以通过使用关键字来实现这个，比如用 l.sort(key=str.lower)。但是问题要求我提取最大元素，而不是最小元素，然后把它加到一个递归排序好的子列表里。

如果有人能帮我，我会非常感激。

Answer 1

排序的方法应该能满足你的需求。如果你想要反向排序，只需使用 list.reverse() 就可以了。

如果你的任务是自己实现一个排序的方法，那也是可以做到的。

你可以试试下面这样的代码：

def sort(l):
    li=l[:]                                        #to make new copy
    newlist = []                                   #sorted list will be stored here
    while len(li) != 0:                            #while there is stuff to be sorted
        bestindex = -1                             #the index of the highest element
        bestchar = -1                              #the ord value of the highest character
        bestcharrep = -1                           #a string representation of the best character
        i = 0
        for v in li:
            if ord(v) < bestchar or bestchar == -1:#check if string is lower than old best
                bestindex = i                      #Update best records
                bestchar = ord(v)
                bestcharrep = v
            i += 1
        del li[bestindex]                          #delete retrieved element from list
        newlist.append(bestcharrep)                #add element to new list
    return newlist                                 #return the sorted list

Answer 2

那么，你明白这个问题了吗？

我们来看看你被要求做的事情：

提取最大元素，而不是最小元素，然后把它加到一个递归排序的子列表上。

所以，我们要做以下几件事：

1) 提取最大元素。你明白“提取”在这里是什么意思吗？你知道怎么找到最大元素吗？

2) 递归地对子列表进行排序。这里的“子列表”是指在提取最大元素后剩下的所有元素。你知道递归是怎么回事吗？就是再次调用你的排序函数，用子列表来进行排序，依靠它来完成排序。毕竟，你的函数就是用来排序列表的，所以这样应该没问题吧？ :)

3) 用.append()把最大元素加到排序后的子列表结果上。这应该不需要解释吧。

当然，我们需要一个递归的基础情况。什么时候会有基础情况呢？就是当我们不能完全按照步骤进行时。那是什么情况下会发生呢？嗯，为什么会发生呢？答案是：如果没有元素，我们就无法提取最大元素，因为那时候根本没有最大元素可提取。

所以，在函数开始时，我们要检查传入的列表是否为空。如果是空列表，我们就返回一个空列表，因为排序一个空列表的结果就是空列表。（你明白为什么吗？）否则，我们就继续进行其他步骤。