python - 使用递归快速排序附加到列表？

Question

我在让这个快速排序函数返回实际列表而不是一项一项地返回项目时遇到了一些困难。排序逻辑工作正常，但它没有返回数组。有没有办法添加一个持久列表，将项目附加到每个循环？

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])

快速旁注是，我在这里使用 print，但实际上我想以某种方式使用 return。

Answer 1

解决方案是在函数的每个分支中实际返回一个结果列表。如果没有什么可排序的，它可能是空列表。否则，它是所有小于主元元素的元素的排序列表，加上主元元素，以及所有大于或等于(或不小于)主元元素的元素的排序列表。

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)