_Hal @ 2023-07-21 12:18:09
#include <iostream>
#include <string>
const int N = 50000010;
int k;
int arr[N];
void swap(int& a, int&b)
{
int temp = a;
a = b;
b = temp;
}
int qu_sort(int arr[], int l, int r, int k)
{
if (l == r)
{
return arr[l];
}
int i = l - 1, j = r + 1, x = arr[l + r >> 1];
while (i < j)
{
do
{
i++;
} while (arr[i] < x);
do
{
j--;
} while (arr[j] > x);
if (i < j)
{
swap(arr[i], arr[j]);
}
}
int len = r - l + 1;
if (k < len)
{
qu_sort(arr, l, j, k);
}
else
{
qu_sort(arr, j + 1, r, k - len);
}
}
int main()
{
int i, n;
scanf("%d %d\n", &n, &k);
for (i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
std::cout << qu_sort(arr, 0, n - 1, k + 1);
system("pause");
return 0;
}
by __Tonycyt__ @ 2023-07-21 12:30:00
@ln2____ system("pause")
你想干嘛
by _Hal @ 2023-07-21 12:40:55
@Tonycyt 啊。。。不是cpp代码都有这个吗我记得。。。删掉也过不了哇。。
by __Tonycyt__ @ 2023-07-21 12:59:56
@ln2____ 我觉得就是有点没必要,你用的是快排,全红吗?
by Terrible @ 2023-07-21 13:01:44
@ln2____
①int len = r - l + 1;
里面改成 j-l+1
②后面两个 qu_sort
加上 return
:return qu_sort(arr, l, j, k);
和 return qu_sort(arr, j + 1, r, k - len);
别刷小聪明,这个能在 G++ 不开优化的时候输出正确结果。但是你这是违法行为,走跟我去自首。用 Clang++ 编译或者在开 O2 的环境里铁定寄。
by Terrible @ 2023-07-21 13:03:53
③ if (k <= len)
加个等号。
by __Tonycyt__ @ 2023-07-21 13:04:19
最小的数是第0小你为啥qu_sort(arr,0,n-1,k+1)
我很疑惑
by __Tonycyt__ @ 2023-07-21 13:06:06
还有你好像少了return
by Terrible @ 2023-07-21 13:06:11
@Tonycyt 细细读题。
输出这些数字的第
k 小的数。最小的数是第0 小.
将
by _Hal @ 2023-07-21 13:06:12
@Tonycyt 我用的是快速选择排序,O(n)的那个。。
by _Hal @ 2023-07-21 13:07:01
@Terrible 谢兄弟谢谢啦!我去看看