快速排序
输入样例
5
3 1 2 4 5
输出样例
1 2 3 4 5
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
if (l == r)
return;
int x = q[(l + r) / 2], i = l - 1, j = r + 1;
while (i < j)
{
while (q[++i] < x);//移动i直到q[i]大于等于x
while (q[--j] > x);//移动j直到q[j]小于等于x
if (i < j)
swap(q[i], q[j]);//两者交换
}
quick_sort(q, l, j);//递归处理左端
quick_sort(q, j + 1, r);//递归处理右端
}
int main()
{
cin >> n ;
for (int i = 0; i < n; i++)
scanf("%d", &q[i]);
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i++)
printf("%d ", q[i]);
return 0;
}
选取第k个数
输入样例
5 3
2 4 1 5 3
输出样例
3
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n,k;
int q[N];
int quick_sort(int l,int r,int k)
{
if (l == r)
return q[l];
int x = q[(l + r) / 2], i = l - 1, j = r + 1;
while (i < j)
{
while (q[++i] < x);//移动i直到q[i]大于等于x
while (q[--j] > x);//移动j直到q[j]小于等于x
if (i < j)
swap(q[i], q[j]);//两者交换
}
int s = j - l + 1;//左端长度
if (k <= s)
quick_sort(l, j, k);//递归处理左端
else
quick_sort(j + 1, r, k-s);//递归处理右端
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++)
scanf("%d", &q[i]);
cout << quick_sort(0, n - 1, k) << endl;
return 0;
}