固定主元算法查找第k小C++

固定主元法是一种用于解决排序问题的算法，特别适用于求解数组中第k小元素的问题，也被称为“快速选择”或“随机化快速排序”。这种方法是基于快速排序的思想，但是为了避免最坏情况下的时间复杂度O(n^2)，它引入了随机化的元素作为“主元”（pivot）。
在C++中，我们可以按照以下步骤实现固定主元法找到第k小的元素：

随机选取主元：从待排序的数组中随机选择一个元素作为主元。

分区操作：将数组分为两部分，一部分包含所有小于主元的元素，另一部分包含所有大于或等于主元的元素。这个过程类似于快速排序的划分阶段。

判断位置：如果主元的位置索引正好是k-1，那么我们就找到了第k小的元素；如果主元的位置索引小于k-1，我们在右侧继续寻找；如果大于k-1，则在左侧查找。

递归或循环：根据上述判断结果，递归地在相应部分数组上重复以上步骤，直到找到第k小的元素。

这是一个简单的伪代码示例：
int partition(vector<int>&amp; nums, int low, int high) {
// 随机选取主元
int pivotIndex = rand() % (high - low + 1) + low;
swap(nums[low], nums[pivotIndex]);

// 将其他元素移动到正确的位置
int i = low + 1;
for (int j = low + 1; j < high; ++j) {
if (nums[j] <= nums[low]) {
swap(nums[i], nums[j]);
i++;
}
}
swap(nums[low], nums[i - 1]);
return i - 1;
}

// 找到第k小元素
int findKthSmallest(vector<int>&amp; nums, int k, int left, int right) {
if (left == right) {
return nums[left];
}

int pivotIndex = partition(nums, left, right);
if (pivotIndex == k - 1) {
return nums[pivotIndex];
} else if (pivotIndex < k - 1) {
return findKthSmallest(nums, k, pivotIndex + 1, right);
} else {
return findKthSmallest(nums, k, left, pivotIndex - 1);
}
}
登录后复制