Python算法实现快速排序

快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

以下是使用Python实现快速排序的代码：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

arr = [3,6,8,10,1,2,1]
print(quick_sort(arr))

在这段代码中，我们首先检查输入的数组的长度，如果长度小于或等于1，那么这个数组已经是有序的，我们直接返回，然后我们选择一个基准值，这里我们选择数组的中间元素，接着我们将数组分为三部分，左边的部分包含所有小于基准值的元素，中间的部分包含所有等于基准值的元素，右边的部分包含所有大于基准值的元素，最后我们对左边和右边的部分递归地进行快速排序，然后将结果和中间的部分合并在一起，就得到了排序后的数组。

这段代码的时间复杂度是O(n log n)，空间复杂度是O(log n)，这是因为每次递归调用都会将问题的规模减半，所以总共需要进行log n次递归调用，而在每次递归调用中，我们需要创建一个新的数组来存储左边、中间和右边的部分，所以总的空间复杂度是O(log n)。