Быстрая сортировка добавить в список с рекурсией? - PullRequest
Новая
       16

Быстрая сортировка добавить в список с рекурсией?

0 голосов
/ 29 мая 2018

У меня возникли небольшие трудности с тем, чтобы эта функция быстрой сортировки возвращала фактический список вместо элементов один за другим.Логика сортировки работает нормально, но не возвращает массив.Есть ли способ добавить постоянный список, в который элементы добавляются к каждому циклу? 

import random


def quick_sort_2(input_arr):

    if len(input_arr) == 1:
        print(input_arr[0])
        return input_arr[0]
    elif len(input_arr) == 0:
        return
    else:
        pivot = input_arr[0]
        i = 0
        left_arr = []
        right_arr = []
        while i < len(input_arr):
            if input_arr[i] < pivot:
                left_arr.append(input_arr[i])
                i += 1
            elif input_arr[i] > pivot:
                right_arr.append(input_arr[i])
                i += 1
            else:
                i += 1
        quick_sort_2(left_arr)
        print(pivot)
        quick_sort_2(right_arr)


quick_sort_2([3, 5, 2, 6, 1, 7, 0])

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

1 Ответ

0 голосов
/ 31 мая 2018

Решение состоит в том, чтобы фактически возвращать список результатов в каждой ветви функции.Это может быть пустой список, если сортировать нечего.В противном случае это отсортированный список всех элементов, меньших, чем элемент сводки, плюс элемент сводки, и отсортированный список всех элементов, больших или равных (или не меньших), чем элемент сводки. 

def quick_sort_2(items):
    items = iter(items)
    try:
        pivot = next(items)
    except StopIteration:
        return []
    else:
        left_items = []
        right_items = []
        for item in items:
            (left_items if item < pivot else right_items).append(item)
        return quick_sort_2(left_items) + [pivot] + quick_sort_2(right_items)
...