【Python练习】044. 编写一个函数，实现快速排序算法

044. 编写一个函数，实现快速排序算法

快速排序是一种高效的排序算法，使用分治法（Divide and Conquer）策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。

示例代码

def quick_sort(arr):"""快速排序函数。参数:arr (list): 输入数组。"""if len(arr) <= 1:return arr  # 如果数组长度小于等于1，直接返回数组else: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("原始数组：", arr)
sorted_arr = quick_sort(arr)
print("排序后的数组：", sorted_arr)

运行结果

运行上述代码后，输出如下：

原始数组： [3, 6, 8, 10, 1, 2, 1]
排序后的数组： [1, 1, 2, 3, 6, 8, 10]

代码解释

基本情况：

• 如果数组长度小于等于 1，直接返回数组，因为长度为 1 的数组已经是有序的。

选择基准：

• 选择数组中间的元素作为基准（pivot）。也可以选择第一个元素、最后一个元素或随机元素作为基准。

划分数组：

• 使用列表推导式将数组分为三部分：

• left：小于基准的元素。

• middle：等于基准的元素。

• right：大于基准的元素。

递归排序：

• 递归地对 left 和 right 子序列进行快速排序。

• 最后将排序后的 left 子序列、middle 和排序后的 right 子序列合并。

扩展：原地快速排序

上述实现使用了额外的空间来存储 left、middle 和 right 子序列。为了节省空间，可以实现原地快速排序。以下是原地快速排序的实现代码：

def quick_sort_inplace(arr, low, high):