6-4 利用“选择排序算法“对结构体数组进行排序 分数 5 作者 叶斌 单位 成都信息工程大学 本题：补充函数 sortByChoose（）的剩余部分，其要求是利用选择排序算法根据学生成绩（score)实现对结构体数组元素降序排序。 函数接口定义： void sortByChoose(struct Student *pData,int n)； 裁判测试程序样例： #include<stdio.h> #include<stdlib.h> #define N 10 struct Student { int num; int score; }; void sortByChoose(struct Student *pData,int n); int main(void) { struct Student data[10],*p; int i; for(p=data,i=0;i<N;i++) { scanf("%d %d",&p->num,&p->score); p++; } sortByChoose(data,N); for (p=data,i=0;i<N;i++) { printf("%2d-%-5d", p->num, p->score); p++; } return 0; } void sortByChoose(struct Student *pData,int n) { struct Student *p1,*p2,*p; int num, score,i,j; for(p1=pData;p1<pData+n-1;p1++) { /* 请在这里填写答案 */ } } 输入样例： 29 90 15 80 87 55 65 84 35 80 33 55 44 79 99 80 89 80 41 55 输出样例： 29-90 65-84 15-80 35-80 99-80 89-80 44-79 87-55 33-55 41-55

题目描述

本题：补充函数 sortByChoose（）的剩余部分，其要求是利用选择排序算法根据学生成绩（score)实现对结构体数组元素降序排序。

函数接口定义：

void sortByChoose(struct Student *pData,int n)；

样例

输入样例：
29 90
15 80
87 55
65 84
35 80
33 55
44 79
99 80
89 80
41 55

输出样例：
29-90 65-84 15-80 35-80 99-80 89-80 44-79 87-55 33-55 41-55

算法

(选择排序) $O(n^2)$

对结构体数组进行选择排序，根据学生成绩（score)实现对元素降序排序。

时间复杂度

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$

C++ 代码

#include <stdio.h>

#define N 10

struct Student {
    int num;
    int score;
};

void sortByChoose(struct Student *pData, int n);

int main(void) {
    struct Student data[10], *p;
    int i;

    for (p = data, i = 0; i < N; i++) {
        scanf("%d %d", &p->num, &p->score);
        p++;
    }

    sortByChoose(data, N);

    for (p = data, i = 0; i < N; i++) {
        printf("%2d-%-5d", p->num, p->score);
        p++;
    }

    return 0;
}

void sortByChoose(struct Student *pData, int n) {
    struct Student *p1, *p2, *p;
    int num, score, i, j;

    for (p1 = pData; p1 < pData + n - 1; p1++) {
        p = p1;
        for (p2 = p1 + 1; p2 < pData + n; p2++) {
            if (p2->score > p->score) {
                p = p2;
            }
        }

        if (p != p1) {
            num = p1->num;
            score = p1->score;
            p1->num = p->num;
            p1->score = p->score;
            p->num = num;
            p->score = score;
        }
    }
}