[数组排序] 0912. 排序数组

1. 题目链接

912. 排序数组 - 力扣（LeetCode）

---

2. 题目大意

描述：给定一个整数数组 nums。

要求：将该数组升序排列。

说明：

• 1≤nums.length≤5∗104。
• −5∗104≤nums[i]≤5∗104。

---

3. 示例

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

---

4. 解题思路

假设数组的元素个数为 n 个，则快速排序的算法步骤如下：

1. 哨兵划分：选取一个基准数，将数组中比基准数大的元素移动到基准数右侧，比他小的元素移动到基准数左侧。
   1. 从当前数组中找到一个基准数 pivot（这里以当前数组第 1 个元素作为基准数，即 pivot=nums[low]）。
   2. 使用指针 i 指向数组开始位置，指针 j 指向数组末尾位置。
   3. 从右向左移动指针 j，找到第 1 个小于基准值的元素。
   4. 从左向右移动指针 i，找到第 1 个大于基准数的元素。
   5. 交换指针 i、指针 j 指向的两个元素位置。
   6. 重复第 3∼5 步，直到指针 ii和指针 j 相遇时停止，最后将基准数放到两个子数组交界的位置上。
2. 递归分解：完成哨兵划分之后，对划分好的左右子数组分别进行递归排序。
   1. 按照基准数的位置将数组拆分为左右两个子数组。
   2. 对每个子数组重复「哨兵划分」和「递归分解」，直到各个子数组只有 1 个元素，排序结束。

---

5. 参考代码

public class Solution {private Random random = new Random();// 三向快速排序：针对有大量重复元素的情况优化private void threeWayQuickSort(int[] nums, int low, int high) {if (low >= high) return;// 随机选取基准数并与第一个元素交换int pivotIndex = random.nextInt(high - low + 1) + low;swap(nums, low, pivotIndex);int pivot = nums[low];int lt = low;     // 维护小于基准数的区域int gt = high;    // 维护大于基准数的区域int i = low + 1;  // 遍历数组while (i <= gt) {if (nums[i] < pivot) {swap(nums, i++, lt++);} else if (nums[i] > pivot) {swap(nums, i, gt--);} else {i++;}}// 递归排序小于基准数的区域和大于基准数的区域threeWayQuickSort(nums, low, lt - 1);threeWayQuickSort(nums, gt + 1, high);}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}public int[] sortArray(int[] nums) {threeWayQuickSort(nums, 0, nums.length - 1);return nums;}
}

---