冒泡全TLE，求帮

P1923 【深基9.例4】求第 k 小的数

Li_wc0802 @ 2023-11-04 20:21:51

#include <iostream>
using namespace std;
int n, k, a[5000001];
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = n; i > 0; i--) {
        for (int j = n; j > 0; j--) {
            if (a[j] < a[j - 1])
                swap(a[j - 1], a[j]);
        }
    }
    cout << a[k + 1];
    return 0;
}

求调QWQ

by strlen_s_ @ 2023-11-04 20:22:56

@Li_wc

这题并不是要你用冒泡排序啊。这个数据范围不T 就怪了。

by 2021zjhs005 @ 2023-11-04 20:27:21

（我没有想到全部时间超限）。如果不用分治算法，可以用 $nth\underline{-}element$ 来写（中间有个下划线）。具体代码如下： ```cpp #include<bits/stdc++.h> using namespace std; int k,n,a[5000005]; int main() { cin>>n>>k; for(int i=0;i<n;i++) scanf("%d",&a[i]);//输入。 nth_element(a,a+k,a+n); //nth_element(数组名，数组名+求第几小的数（从 0 开始），数组名+总个数); //表示将数组的前 $k$ 个数从小到大排列好。 cout<<a[k]; return 0; } ```

by 2021zjhs005 @ 2023-11-04 20:28:57

差不多是这个意思。

@Li_wc

by Ace_FutureDream @ 2023-11-04 20:46:01

@Li_wc 不T就怪了，建议学习下sort

by MichaelQiu @ 2023-11-04 20:54:37

@Li_wc 建议楼主学一下 <algorithm>下的sort()函数，这玩意儿效率很高，会自动选择快排等等，格式如下（cmp在不需要调整的情况下可省略）：

void sort(RandomIt first, RandomIt last, Compare comp);

同时建议楼主稍微了解一下数组的地址，比如数组int arr[114]，arr即是该数组地址（指向第0个元素）

by danlao @ 2023-11-04 21:02:35

n<=5000000

冒泡时间复杂度：O(n²)

选择时间复杂度：O(n²)

插入时间复杂度：O(n²)

快速时间复杂度：O(n ㏒ n)

想想用哪个

by Igunareo @ 2023-12-21 21:38:11

@Li_wc

也想得出来拿冒泡做5000000的

好歹用选择啊（好一点，也就好一点）

sort更好(TLE别找我)

正解分治（照站长标程打）

就你用的cin读入都会超

想学排序建议换两题