快速选择算法
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
typedef pair<int,int>pii;
const int N=2e5+10;
// 用快速选择算法
int n,k;
int q;
int quick_sort(int l,int r,int k)
{
if(l==r)return q;
int x=q,i=l-1,j=i+1;
while(i<j)
{
do i++;while(q<x);
do j--;while(q>x);
if(i<j)swap(q,q);
}
int sl=j-l+1;// 左边区间有多少个数
if(k<=sl)return quick_sort(l,j,k);
return quick_sort(j+1,r,k-sl);
}
void solve()
{
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>q;
}
cout<<quick_sort(0,n-1,k)<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t=1;
while(t--)
{
solve();
}
}
为什么会没有输出呢 快速选择算法是一种用于在无序数组中寻找第k个最小元素的算法。它的思想类似于快速排序，通过将数组分成两部分，其中一部分比pivot元素小，另一部分比pivot元素大。然后根据pivot元素所在的位置，判断第k个最小元素在哪一部分，并对相应的部分进行递归处理。
以下是一个使用快速选择算法寻找第k个最小元素的示例代码：
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot = arr;// 选择最右边的元素作为pivot
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr <= pivot) {
i++;
swap(arr, arr);
}
}
swap(arr, arr);
return i + 1;
}
int quickSelect(int arr[], int low, int high, int k) {
if (low == high) {
return arr;
}
int pivotIndex = partition(arr, low, high);
int rank = pivotIndex - low + 1;
if (rank == k) {
return arr;
} else if (rank < k) {
return quickSelect(arr, pivotIndex + 1, high, k - rank);
} else {
return quickSelect(arr, low, pivotIndex - 1, k);
}
}
int main() {
int arr[] = {3, 1, 5, 2, 4};
int n = sizeof(arr) / sizeof(arr);
int k = 2;// 寻找第2个最小元素
int result = quickSelect(arr, 0, n - 1, k);
cout << "第" << k << "个最小元素是：" << result << endl;
return 0;
}
上述代码中，`quickSelect`函数用于执行快速选择算法，其中`partition`函数用于进行数组的分割操作。在`main`函数中，我们定义了一个整型数组`arr`，并使用`quickSelect`函数寻找第k个最小元素。
希望对你有所帮助！如果还有其他问题，请随时向我提问。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]