众所周知，ln是一个dalao，lty是一个five，现在lty问ln，你能将n个数字进行选择法排序使其从小到大有序吗？ln觉得这个问题很简单，然后就反问lty，你能在这个的基础上，输出进行k轮选择法排序的结果吗？lty是个弱鸡，当然不会，于是向你请教这个问题，你能替lty解决这个问题吗？ 给你n个数字，输出将这n个数字经过k轮选择法排序后的结果。

选择法排序：遍历整个数组，第一轮遍历第1位到第n位，找到最小的与第1位交换，第二轮遍历第2位到第n位，找到最小的与第2位交换，以此类推。（每轮只交换一次）

输入格式：

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

输出格式：

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

输入样例：

1
2
6 2
2 3 5 1 6 4

输出样例：

1
1 2 5 3 6 4

思路

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

选择排序：依次从数组中选出最小、第2小、第3小。。。的数，放到数组的第1、第2、第3。。。个位置。选择(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
#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++) {
        int index = i; //最小数的索引
        int val = ve[i]; //最小数，先假设第一个最小，然后从第2个开始遍历
        for(int j = i + 1 ; j < n; j++) {//寻找第(i+1)小的数
            if(ve[j] < val) {
                index = j;
                val = ve[j];
            }
        }
        swap(ve[i], ve[index]);//将最小数放到前面
    }
    for(int i = 1; i <= n; i++) {
        cout << ve[i - 1];
        cout << (i == n ? '\n' : ' ');
    }
    return 0;
}