class Solution {
// partition函数:
// 在进行分区操作时,需要维护两个指针i,j
// i指向小于pivot的最后一个元素;j指向当前正在处理的元素
// i的初始值l-1,这意味着当第一次迭代时,如果 nums[j] <= pivot,我们将会交换 nums[i+1] 和 nums[j],并将 i 加 1
// 这样,在第一次迭代之后,i 的值就变成了 l
// 之后,每当 nums[j] <= pivot 时,i 的值都会加 1。
int partition(vector<int>& nums, int l, int r) {
int pivot = nums[r];
int i = l - 1;
for (int j = l; j <= r - 1; ++j) {
if (nums[j] <= pivot) {
i = i + 1;
swap(nums[i], nums[j]);
}
}
swap(nums[i + 1], nums[r]); // 遍历完整个区间后,将基准位放到分界位置
return i + 1;
}
int randomized_partition(vector<int>& nums, int l, int r) {
int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
swap(nums[r], nums[i]); // 参照题解中的动画,将基准位放到最右侧
return partition(nums, l, r);
// partition函数将数值进行分区(按照大小将数据放到基准位两侧)
}
void randomized_quicksort(vector<int>& nums, int l, int r) {
if (l < r) {
int pos = randomized_partition(nums, l, r); // 随机基准位
randomized_quicksort(nums, l, pos - 1);
randomized_quicksort(nums, pos + 1, r);
}
}
public:
vector<int> sortArray(vector<int>& nums) {
srand((unsigned)time(NULL)); // 随机数发生器的初始化函数、后面使用了rand()
randomized_quicksort(nums, 0, (int)nums.size() - 1);
return nums;
}
};
快排的思想:
选取一个基准位,将比基准位小的元素放到基准位左侧,比基准位大的放到基准位右侧
leetcode题解中的方法基准位是随机选取的
版权声明:本文为Dorothy_yy原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。