1. 题目解析
题目链接：912. 排序数组
这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。
2.算法原理
算法思路：
快速排序作为一种经典的排序算法，其核心思想在于通过“分而治之”的策略，将数据划分为不同的部分，并递归地对这些部分进行排序。其中，最关键的步骤是Partition（分区），即按照某个基准元素将数组划分为左右两部分，左侧元素小于基准，右侧元素大于基准。
在处理含有大量重复元素的数据集时，常规的快速排序算法效率可能会受到影响。因此，我们可以借鉴“荷兰国旗问题”的解决思路，将数组进一步细分为左、中、右三部分：左侧存放小于基准的元素，中间存放与基准相等的元素，右侧存放大于基准的元素。随后，我们只需对左侧和右侧的元素进行递归排序，而无需处理中间的大量重复元素，从而显著提高算法效率。
算法流程：
- 定义递归出口：
- 当待排序的数组区间长度小于等于1时，认为该区间已排序完成，无需继续处理。
- 随机选择基准元素：
- 为了避免最坏情况的发生（如数组已部分有序或完全有序），我们采用随机选择基准元素的方法。
- 初始化一个随机数生成器，生成一个随机数。
- 将随机数转换为数组下标，通过取模运算和加上区间左边界的方式，确保下标在待排序区间的范围内。
- 使用该下标对应的元素作为基准元素。
- 利用荷兰国旗思想划分数组：
- 初始化三个指针：left、mid、right，分别指向区间的最左端、最右端以及当前遍历的位置。
- 从left开始遍历数组，根据当前元素与基准元素的大小关系，移动left、mid、right指针，并将元素交换到正确的位置。
- 遍历结束后，数组被划分为左、中、右三部分。
- 递归处理左边区域和右边区域：
- 对左边区域（小于基准元素的部分）递归调用快速排序算法。
- 对右边区域（大于基准元素的部分）递归调用快速排序算法。
- 注意，中间与基准相等的部分无需处理，因为它们已经处于正确的位置。
3.代码编写
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
srand(time(NULL)); // 种下⼀个随机数种⼦
qsort(nums, 0, nums.size() - 1);
return nums;
}
// 快排
void qsort(vector<int>& nums, int l, int r) {
if (l >= r)
return;
// 数组分三块
int key = getRandom(nums, l, r);
int i = l, left = l - 1, right = r + 1;
while (i < right) {
if (nums[i] < key)
swap(nums[++left], nums[i++]);
else if (nums[i] == key)
i++;
else
swap(nums[--right], nums[i]);
}
// [l, left] [left + 1, right - 1] [right, r]
qsort(nums, l, left);
qsort(nums, right, r);
}
int getRandom(vector<int>& nums, int left, int right) {
int r = rand();
return nums[r % (right - left + 1) + left];
}
};The Last
嗯，就是这样啦，文章到这里就结束啦，真心感谢你花时间来读。
觉得有点收获的话，不妨给我点个赞吧！
如果发现文章有啥漏洞或错误的地方，欢迎私信我或者在评论里提醒一声~
