Выбора сортировка с помощью рекурсии


Как это рекурсивной сортировки посмотрите на все здесь? Я что-то упускаю 'весть' о том, как я сделал это?

def selection_sort(li, out=None):
    if out is None:
        out = []    
        li = li[:]

    if len(li) == 0:
        return out

    small = min(li)
    li.remove(small)
    out.append(small)
    return selection_sort(li, out)


Комментарии
1 ответ

def selection_sort(li, out=None):

Мне не нравится имя "ли," я думаю, что аббревиатуры-это плохо.

    if out is None:
out = []
li = li[:]

Вместо того, чтобы использовать параметр, чтобы сделать это, я предлагаю создать отдельную внутреннюю функцию, которая называется. В противном случае, похоже, вызывающего функцию может отрубиться = что-то, когда его только предназначается, чтобы использоваться внутренне.

    if len(li) == 0:
return out

Лучше использовать , если не нра:

    small = min(li)
li.remove(small)
out.append(small)
return selection_sort(li, out)

Его немного трудно оценить этот код, потому что вы делаете две вещи, которые вы не должны, используя рекурсию, когда его не надо и реализации собственного рода рутину. Но если вы это делаете в учебных целях это нормально.

Редактировать

Итерационное решение:

def selection_sort(li):
li = li[:]
out = []

while li:
smallest = min(li)
li.remove(smallest)
out.append(smallest)

return out

Но почему это лучше, чем рекурсивное решение:


  1. Есть предел для вашего стека. Если вы пытаетесь сортировать большой список с помощью этой функции вы получите RuntimeError

  2. Вызов функции имеет дополнительные накладные расходы, что итерации в цикле нет, то итерационный вариант будет быстрее

  3. Цикл обычно легче читать потом рекурсия. Цикл while делает его легко увидеть, что делать дальше, в то время как рекурсивная версия требует некоторых размышлений о код, чтобы увидеть логику.

3
ответ дан 7 июня 2011 в 07:06 Источник Поделиться