快速排序算法（QuickSort） 题目描述：给定一个整数数组，使用快速排序算法将其按升序排列。快速排序是一种高效的排序算法，采用分治策略，平均时间复杂度为O(n log n)。 解题过程： 基本思想 快速排序的核心是"分治"：选择一个基准元素，将数组分为两部分，使得左边部分的元素都小于等于基准，右边部分的元素都大于等于基准，然后递归地对左右两部分进行排序。 分区过程（Partition） 这是快速排序最关键的一步，具体操作如下： 从数组中选择一个基准元素（通常选择第一个、最后一个或中间元素） 设置两个指针：左指针从数组起始位置开始，右指针从数组末尾开始 左指针向右移动，直到找到大于基准的元素 右指针向左移动，直到找到小于基准的元素 交换这两个元素 重复上述过程，直到左指针超过右指针 最后将基准元素放到正确的位置 递归排序 分区完成后，数组被分为三个部分： 左子数组：所有元素小于基准 基准元素：已经在正确位置 右子数组：所有元素大于基准 然后递归地对左子数组和右子数组进行快速排序。 具体示例 以数组 [ 3, 6, 8, 10, 1, 2, 1 ] 为例： 第一步：选择最后一个元素1作为基准 分区过程： 左指针在3停止（3>1），右指针在1停止（1≤1） 交换3和1：数组变为[ 1, 6, 8, 10, 1, 2, 3 ] 继续：左指针在6停止，右指针在2停止，交换6和2：[ 1, 2, 8, 10, 1, 6, 3 ] 继续：左指针在8停止，右指针在1停止，此时左指针已超过右指针 将基准1放到正确位置：[ 1, 2, 1, 10, 8, 6, 3] → [ 1, 2, 1, 3, 8, 6, 10 ] 第二步：递归排序左子数组[ 1, 2, 1]和右子数组[ 8, 6, 10 ] 时间复杂度分析 最佳情况：O(n log n) - 每次分区都能均匀划分 最差情况：O(n²) - 每次分区都极不均匀 平均情况：O(n log n) 优化措施 三数取中法：选择首、中、尾三个元素的中值作为基准 小数组使用插入排序：当子数组规模较小时，切换为插入排序 三向切分：处理包含大量重复元素的数组 快速排序在实际应用中非常高效，是很多编程语言内置排序函数的实现基础。