排序数组 题目描述 给你一个整数数组 nums ，请你将该数组升序排列。你必须设计一个时间复杂度为 O(n log n) 的排序算法，且不额外使用大量的辅助空间（即尽量原地排序）。例如，输入 nums = [5,2,3,1] ，输出应为 [1,2,3,5] 。 解题过程 题目要求 O(n log n) 的时间复杂度，这提示我们可以使用分治策略的排序算法，例如快速排序或归并排序。由于要求尽量原地排序，我们选择快速排序的变种，通过递归分治实现。以下是详细步骤： 选择基准值（Pivot） 从当前待排序的子数组中选取一个元素作为基准值。通常可选择中间位置的元素，以减少最坏情况发生的概率。例如，对子数组 nums[left...right] ，取 mid = left + (right - left) // 2 ，将 nums[mid] 作为基准值。 分区操作（Partition） 将数组重新排列，使得所有小于基准值的元素放在其左侧，大于基准值的元素放在右侧。具体步骤： 初始化两个指针 i = left ， j = right 。 将基准值与末尾元素交换，暂时将其放在末尾（便于后续比较）。 指针 i 从左向右扫描，直到找到大于等于基准值的元素；指针 j 从右向左扫描，直到找到小于等于基准值的元素。 若 i < j ，交换 nums[i] 和 nums[j] ，继续扫描。 当 i >= j 时，将基准值从末尾换回位置 i ，此时基准值左侧的元素均小于它，右侧均大于它。 递归排序子数组 对基准值左侧的子数组（ nums[left...i-1] ）和右侧的子数组（ nums[i+1...right] ）递归执行上述过程，直到子数组长度为 1 或 0（即已排序）。 示例演示 以 nums = [5,2,3,1] 为例： 初始选基准值： mid = 0 + (3-0)//2 = 1 ，基准值 pivot = nums[1] = 2 。 分区：交换 pivot 与末尾元素 1 ，数组变为 [5,1,3,2] 。 扫描： i 指向 5 （≥2）， j 指向 1 （≤2），交换后为 [1,5,3,2] 。 继续扫描： i 指向 5 ， j 指向 1 ，此时 i > j ，交换基准值 2 与 nums[i] ，得 [1,2,3,5] 。 递归左侧 [1] （已排序）和右侧 [3,5] ，对右侧再次分区后得到有序数组。 复杂度分析 平均时间复杂度：O(n log n)，最坏情况（如数组已有序）为 O(n²)，但随机选基准可避免。 空间复杂度：递归栈深度平均为 O(log n)，符合原地排序要求。 通过以上步骤，即可高效完成排序。