选择排序输出多轮学号

胡兜兜玩算法 / 2023-08-29 / 原文

题目描述

有n名学生从左往右排成一行站成队列，学号是1至n。给出这n名学生的身高，学号是i的学生的身高是h[i]，所有学生的身高都不相同。现在进行n-1轮操作，第i轮操作由如下三个步骤构成：
第一步：从当前学生队列排在第i个位置的学生至排在最后一个位置的学生当中，选出身高最矮的学生，不妨假设是第k个位置的学生身高最矮。

第二步：当前队列第i个位置的学生和第k个位置的学生，他们交换位置。

第三步：从左往右，输出当前队列n个学生的学号。

解题思路

我们可以用一个结构体来存放每个学生的信息，一个结构体变量包括以下两部分内容：

id，也就是学号
h，身高（用于比较）

结构体定义

struct man{
	int id;
	int h;
};

剩下的就是排序了,注意：排序时比较的是arr[j].h而不是arr[j]。

AC代码

#include<bits/stdc++.h>
using namespace std;
struct man{
    int id;
    int h;
};
void mySort(man arr[], int len) {
    int min;
    for (int i = 1; i < len; i++) {
        min = i;
        for (int j = i; j <= len; j++)
            if (arr[j].h < arr[min].h)
                min = j;
        swap(arr[i], arr[min]);
        for (int j = 1; j <= len; j++)
            cout << arr[j].id << " ";  //输出arr[j].id而不是arr[j].h
        cout << "\n";
    }
}
int main() {
    int n;
    cin >> n;
    man a[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i].h;
        a[i].id = i;
    }
    mySort(a, n);
    return 0;
}