将N个整数按从小到大排序的冒泡排序法是这样工作的：从头到尾比较相邻两个元素，如果前面的元素大于其紧随的后面元素，则交换它们。通过一遍扫描，则最后一个元素必定是最大的元素。然后用同样的方法对前N−1个元素进行第二遍扫描。依此类推，最后只需处理两个元素，就完成了对N个数的排序。

本题要求对任意给定的K（<N），输出扫描完第K遍后的中间结果数列。

输入格式：

输入在第1行中给出N和K（1≤K<N≤100），在第2行中给出N个待排序的整数，数字间以空格分隔。

输出格式：

在一行中输出冒泡排序法扫描完第K遍后的中间结果数列，数字间以空格分隔，但末尾不得有多余空格。

输入样例：

1
2
6 2
2 3 5 1 6 4

输出样例：

1
2 1 3 4 5 6

思路

以下假设是进行升序排序：

冒泡排序：依次比较两相邻元素，如果后面的大于前面的，则交换，进行(n-1)轮，第k轮会确定第k大的数的最终位置

冒泡排序复杂度O(n2)，效率低，也是理解其余复杂排序方法的基础

知识点：冒泡排序

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> ve;
    for(int i = 0; i < n; i++) {
        int id;
        cin >> id;
        ve.push_back(id);
    }
    for(int i = 0; i < k; i++) { //进行k轮
        bool flag = false;
        for(int j = 1; j < n - i; j++) {
            if(ve[j] < ve[j - 1]) { //将大的数顶到最高，顶出水面
                swap(ve[j], ve[j - 1]);
                flag = true;
            }
        }
        if(!flag) { //如果该轮没有进行交换，说明已经有序（小优化）
            break;
        }
    }
    for(int i = 1; i <= n; i++) {
        cout << ve[i - 1];
        cout << (i == n ? '\n' : ' ');
    }
    return 0;
}