Python函数：快速排序一个列表

快速排序是一种常用的排序算法，它的思想是通过一趟排序将待排序的列表分割成两部分，其中一部分的所有元素都比另一部分的元素小，然后再按照此方法对这两部分分别进行快速排序，以达到整个序列有序的目的。下面是一个使用Python实现快速排序的函数。

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        # 选取基准值
        pivot = arr[0]
        # 将小于基准值的元素放在一个列表中
        lesser = [x for x in arr[1:] if x <= pivot]
        # 将大于基准值的元素放在一个列表中
        greater = [x for x in arr[1:] if x > pivot]
        # 递归地对小于基准值的列表和大于基准值的列表进行快速排序
        return quicksort(lesser) + [pivot] + quicksort(greater)

# 使用示例
arr = [2, 1, 5, 3, 4]
sorted_arr = quicksort(arr)
print(sorted_arr)

以上代码中，定义了一个名为quicksort的函数，它接受一个列表参数arr，然后通过递归地调用自身对列表进行分割和排序。在每一次递归调用中，函数会选择列表的第一个元素作为基准值（pivot），然后分别将小于等于基准值的元素和大于基准值的元素分到两个列表中。最后，函数将递归地对这两个列表进行排序，并将排序好的小于基准值的列表、基准值和排序好的大于基准值的列表拼接起来返回。

通过调用quicksort函数，并打印返回结果，我们可以得到一个已排序的列表[1, 2, 3, 4, 5]。

快速排序的时间复杂度为O(nlogn)，其中n是列表的长度。快速排序是一种原址排序算法，意味着它不需要额外的存储空间来存储中间结果，所以它的空间复杂度为O(logn)。