实现快速排序 题目描述 实现快速排序算法对一个整数数组进行升序排序。快速排序是一种分治算法，其核心思想是选择一个基准元素，将数组划分为两个子数组，使得左子数组的所有元素小于等于基准，右子数组的所有元素大于基准，然后递归地对子数组排序。 解题过程 选择基准 ：从数组中选择一个元素作为基准。常见策略包括选择第一个元素、最后一个元素或随机元素。这里我们选择数组中间的元素作为基准。 分区操作 ：重新排列数组，使得所有小于基准的元素移到其左侧，大于基准的元素移到右侧。分区后，基准元素处于其最终位置。 递归排序 ：对基准左侧和右侧的子数组递归地应用快速排序。 终止条件 ：当子数组的长度为0或1时，无需排序，直接返回。 详细步骤 步骤1：定义函数 创建函数 quick_sort(arr, low, high) ，其中 arr 是待排序数组， low 和 high 是当前子数组的起始和结束索引。 步骤2：分区函数 设计辅助函数 partition(arr, low, high) ： 选择基准元素 pivot （例如 arr[(low + high) // 2] ）。 使用双指针法：左指针 i 从 low 开始向右移动，右指针 j 从 high 开始向左移动。 移动 i 直到找到大于 pivot 的元素，移动 j 直到找到小于 pivot 的元素。 交换这两个元素，重复直到 i 和 j 相遇。 最终返回 j 作为分界点（此时 arr[j] 及左侧元素均 ≤ pivot ）。 步骤3：递归调用 在 quick_sort 中： 若 low < high ，调用 partition 获取分界点 pivot_index 。 递归排序左子数组： quick_sort(arr, low, pivot_index) 。 递归排序右子数组： quick_sort(arr, pivot_index + 1, high) 。 步骤4：示例演示 对数组 [3, 6, 8, 10, 1, 2, 1] ： 首次分区选择基准 pivot=10 （中间值），分区后变为 [3, 6, 8, 1, 1, 2, 10] 。 递归处理左子数组 [3, 6, 8, 1, 1, 2] ，右子数组 [] （已为空）。 持续递归直到所有子数组有序。 关键点 分区操作确保每轮排序后基准元素位置固定。 平均时间复杂度为 O(n log n)，最坏情况（如数组已有序）为 O(n²)，可通过随机选择基准优化。