快速排序的详细过程
快速排序是一种高效的排序算法，它的基本思想是分治法，快速排序由两部分组成：划分（partition）和递归排序（recursive sorting）。
一、划分（Partitioning）划分是快速排序中最关键的一步，在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。
以下是一个简单的 Python 代码实现：
def partition(arr, low, high):
# 选择最右边的元素作为基准值
pivot = arr[high]
# 初始化 i 为 low-1，指向未排序部分的第一个元素
i = low - 1
for j in range(low, high):
# 如果当前元素小于或等于 pivot
if arr[j] <= pivot:
# 增加 i 的值
i += 1
# 交换 arr[i] 和 arr[j]
arr[i], arr[j] = arr[j], arr[i]
# 交换 arr[i+1] 和 arr[high]（或者 pivot）
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1
二、递归排序（Recursive Sorting）在递归排序中，我们使用划分操作将数组划分为两个子数组，然后对这两个子数组分别进行快速排序，递归的过程可以一直持续到子数组长度为 0 或 1，此时可以认为子数组已经排序完成。
def quick_sort(arr, low, high):
if low < high:
# 划分操作，得到基准值的位置 pivot_index
pivot_index = partition(arr, low, high)
# 对基准值左边和右边的子数组进行递归排序
quick_sort(arr, low, pivot_index-1)
quick_sort(arr, pivot_index+1, high)
通过以上两个步骤，我们可以实现快速排序，快速排序的时间复杂度在最坏情况下为 O(n^2)，但在平均情况下为 O(n log n)，其中 n 是数组的长度，快速排序是一种原地排序算法，它的空间复杂度为 O(log n)。
