结构体数组单关键字排序

结构体数组单关键字排序可以通过以下步骤来实现：
1. 定义一个结构体，包含需要排序的字段
2. 定义一个结构体数组，并初始化
3. 通过冒泡排序、快速排序等算法，对结构体数组按照需要排序的字段进行排序
4. 输出排序后的结果

以下是一个示例代码，用于对结构体数组按照score字段进行排序：

#include <iostream>
#include <algorithm>
using namespace std;

struct student {
    string name;
    int score;
};

bool cmp(student a, student b) {
    return a.score > b.score;
}

int main() {
    student stu = {{"Tom", 80}, {"Jack", 90}, {"Mary", 85}};
    sort(stu, stu + 3, cmp);
    for (int i = 0; i < 3; i++) {
        cout << stu[i].name << " " << stu[i].score << endl;
    }
    return 0;
}

相关问题

对结构体数组按某个关键字排序,程序中已通过结构体定义了学生的学号、姓名、成绩，并给出了初始数据，函数fun的功能是：按姓名的字典顺序从小到大排序，在划线处填写相应的代码。 点击复制后，将打开C知道体验页

以下是代码实现：

#include <stdio.h>
#include <string.h>

struct student {
    char id[10];
    char name[20];
    int score;
};

void fun(struct student s[], int n) {
    int i, j;
    struct student temp;
    for(i = 0; i < n - 1; i++) {
        for(j = 0; j < n - i - 1; j++) {
            if(strcmp(s[j].name, s[j + 1].name) > 0) {
                temp = s[j];
                s[j] = s[j + 1];
                s[j + 1] = temp;
            }
        }
    }
}

int main() {
    struct student s[5] = {
        {"001", "Tom", 78},
        {"002", "Jerry", 85},
        {"003", "Alice", 92},
        {"004", "Bob", 67},
        {"005", "David", 80}
    };
    int i;
    printf("排序前：\n");
    for(i = 0; i < 5; i++) {
        printf("%s %s %d\n", s[i].id, s[i].name, s[i].score);
    }
    fun(s, 5);
    printf("排序后：\n");
    for(i = 0; i < 5; i++) {
        printf("%s %s %d\n", s[i].id, s[i].name, s[i].score);
    }
    return 0;
}

程序中使用结构体存储学生信息，其中包括学号、姓名、成绩。使用函数fun对学生信息按姓名字典顺序从小到大排序，排序算法采用冒泡排序。排序前后，分别输出学生信息。

定义一最大长度为 20 的结构体数组（可以在结构体中只定义关键字域），从键盘输入结构体数组各元素的关键字值，对该数组中的元素按关键字非递减的顺序进行排序，分别用插入排序，选择排序，冒泡排序，递归的快速排序方法完成，再用折半查找方法对已经有序的结构体数组进行操作，输入一待查记录关键字，根据查找情况输出相关信息，以上各功能模块均用函数实现。设计相应算法并分析各排序方法的效率。 该程序运行情况举例说明： 运行主界面如下图所示：提示用户输入相应选项，键入数字 1 则进行待排序数据值的输入；键入数字 2 直接插入排序；键入数字 3 进行直接选择排序；键入数字 4 则进行冒泡排序；键入数字 5 则进行递归的快速排序；键入数字 6 则进行折半查找；键入数字 7 显示元素序列；键入数字 0 程序退出。

好的，我会根据您的要求进行回答。首先需要定义一个结构体类型和一个结构体数组，如下所示：

#define MAX_LENGTH 20

typedef struct {
    int key; // 关键字
} Element;

Element elements[MAX_LENGTH]; // 结构体数组

接下来，我们需要实现输入结构体数组各元素的关键字值的函数，如下所示：

void inputElements(Element elements[]) {
    printf("请输入 %d 个元素的关键字值：\n", MAX_LENGTH);
    for (int i = 0; i < MAX_LENGTH; i++) {
        scanf("%d", &elements[i].key);
    }
}

接下来，我们需要实现插入排序、选择排序、冒泡排序和递归的快速排序方法，如下所示：

void insertionSort(Element elements[]) {
    for (int i = 1; i < MAX_LENGTH; i++) {
        Element temp = elements[i];
        int j = i - 1;
        while (j >= 0 && elements[j].key > temp.key) {
            elements[j + 1] = elements[j];
            j--;
        }
        elements[j + 1] = temp;
    }
}

void selectionSort(Element elements[]) {
    for (int i = 0; i < MAX_LENGTH - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < MAX_LENGTH; j++) {
            if (elements[j].key < elements[minIndex].key) {
                minIndex = j;
            }
        }
        Element temp = elements[i];
        elements[i] = elements[minIndex];
        elements[minIndex] = temp;
    }
}

void bubbleSort(Element elements[]) {
    for (int i = 0; i < MAX_LENGTH - 1; i++) {
        for (int j = 0; j < MAX_LENGTH - i - 1; j++) {
            if (elements[j].key > elements[j + 1].key) {
                Element temp = elements[j];
                elements[j] = elements[j + 1];
                elements[j + 1] = temp;
            }
        }
    }
}

int partition(Element elements[], int low, int high) {
    Element pivot = elements[low];
    while (low < high) {
        while (low < high && elements[high].key >= pivot.key) {
            high--;
        }
        elements[low] = elements[high];
        while (low < high && elements[low].key <= pivot.key) {
            low++;
        }
        elements[high] = elements[low];
    }
    elements[low] = pivot;
    return low;
}

void quickSort(Element elements[], int low, int high) {
    if (low < high) {
        int pivotIndex = partition(elements, low, high);
        quickSort(elements, low, pivotIndex - 1);
        quickSort(elements, pivotIndex + 1, high);
    }
}

最后，我们需要实现折半查找方法，如下所示：

int binarySearch(Element elements[], int key, int low, int high) {
    if (low <= high) {
        int mid = (low + high) / 2;
        if (key == elements[mid].key) {
            return mid;
        } else if (key < elements[mid].key) {
            return binarySearch(elements, key, low, mid - 1);
        } else {
            return binarySearch(elements, key, mid + 1, high);
        }
    }
    return -1;
}

最后，我们需要实现主函数，如下所示：

int main() {
    int choice;
    do {
        printf("请选择操作：\n");
        printf("1. 输入 %d 个元素的关键字值\n", MAX_LENGTH);
        printf("2. 直接插入排序\n");
        printf("3. 直接选择排序\n");
        printf("4. 冒泡排序\n");
        printf("5. 递归的快速排序\n");
        printf("6. 折半查找\n");
        printf("7. 显示元素序列\n");
        printf("0. 退出程序\n");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                inputElements(elements);
                break;
            case 2:
                insertionSort(elements);
                printf("排序完成！\n");
                break;
            case 3:
                selectionSort(elements);
                printf("排序完成！\n");
                break;
            case 4:
                bubbleSort(elements);
                printf("排序完成！\n");
                break;
            case 5:
                quickSort(elements, 0, MAX_LENGTH - 1);
                printf("排序完成！\n");
                break;
            case 6:
                printf("请输入待查记录关键字：\n");
                int key;
                scanf("%d", &key);
                int index = binarySearch(elements, key, 0, MAX_LENGTH - 1);
                if (index != -1) {
                    printf("查找成功，元素下标为：%d\n", index);
                } else {
                    printf("查找失败，元素不存在！\n");
                }
                break;
            case 7:
                printf("元素序列如下：\n");
                for (int i = 0; i < MAX_LENGTH; i++) {
                    printf("%d ", elements[i].key);
                }
                printf("\n");
                break;
            case 0:
                printf("程序已退出！\n");
                break;
            default:
                printf("输入有误，请重新输入！\n");
                break;
        }
    } while (choice != 0);
    return 0;
}

分析各排序方法的效率：

- 插入排序：最好情况下，每个元素都只需要比较一次，时间复杂度为 O(n)；最坏情况下，每个元素都需要比较 i 次，时间复杂度为 O(n^2)；平均情况下，时间复杂度为 O(n^2)。
- 选择排序：无论什么情况下，都需要进行 n(n-1)/2 次比较和 n-1 次交换，时间复杂度为 O(n^2)。
- 冒泡排序：最好情况下，已经有序，只需要进行一次比较，时间复杂度为 O(n)；最坏情况下，每个元素都需要比较 n-i-1 次，时间复杂度为 O(n^2)；平均情况下，时间复杂度为 O(n^2)。
- 快速排序：最好情况下，每次划分的两个子序列的长度相等，时间复杂度为 O(nlogn)；最坏情况下，每次划分的两个子序列的长度分别为 n-1 和 1，时间复杂度为 O(n^2)；平均情况下，时间复杂度为 O(nlogn)。
- 折半查找：时间复杂度为 O(logn)。