程序开发实训 【专题六】 排序

包含题目

1、数组排序
2、数组排序（统计次数）
3、删除重复字符排序字符串
4、数组异或
5、学生成绩排序（结构体数组排序）

注意

1.以下代码仅供参考，不代表最优解。
2.代码的运行结果与编译环境有关，以下代码均通本地测试，如果代码存在无法编译或输出异常，请检查运行环境。
3.如果发现问题或者您有更优的解，欢迎加群交流。

1、数组排序

【问题描述】从标准输入中输入一组整数，按从小到大顺序排序输出。

【输入形式】首先输入整数的个数，再输入第一组整数，以空格分隔。

【输出形式】按从小到大顺序排序输出整数，输出整数间以一个空格分隔，最后不含回车符。

【样例输入】

8
5 1 4 3 8 7 9 6

【样例输出】

1 3 4 5 6 7 8 9

/*
数组排序
安润鲁 2020-05-18 18:08:30
*/
#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
}

void getData(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cin >> arr[i];
}

void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        if (i == n - 1)
            cout << arr[i];
        else
            cout << arr[i] << " ";
}

int main()
{
    int n;
    cin >> n;
    int arr[n];
    getData(arr, n);
    bubbleSort(arr, n);
    display(arr, n);
    return 0;
}

2、数组排序（统计次数）

【问题描述】

从标准输入中输入一组整数，依据从小到大的顺序采用冒泡排序算法，统计在冒泡排序过程种数据交换的次数。

【输入形式】首先输入整数的个数，再输入第一组整数，以空格分隔。

【输出形式】在冒泡排序过程种数据交换的次数。

【样例输入】

8 5 1 4 3 8 7 9 6

【样例输出】

8

/*
数组排序统计次数
安润鲁 2020-05-18 18:10:55
*/
#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n)
{
    int count = 0;
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (arr[j] > arr[j + 1])
            {
                count++;
                swap(arr[j], arr[j + 1]);
            }
    cout << count;
}

void getData(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cin >> arr[i];
}

int main()
{
    int n;
    cin >> n;
    int arr[n];
    getData(arr, n);
    bubbleSort(arr, n);
    return 0;
}

3、删除重复字符排序字符串

【问题描述】

编写一个程序，从键盘接收一个字符串，然后按照字符顺序从小到大进行排序，并删除重复的字符。

【输入形式】

从键盘输入一个字符串，以回车结束输入。要求程序可以处理含有空格的字符串。

【输出形式】

程序接收此字符串，然后将其按照字符 ASCII 码值从小到大的顺序进行排序，并删除重复的字符输出。如果字符串为空，输出也应该为空。

【样例输入】badacgegfacb

【样例输出】abcdefg

【样例说明】输入 badacgegfacb，然后排序、删除重复字符得到 abcdefg

/*
删除重复字符排序字符串
安润鲁 2020-05-18 21:02:19
*/
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

void bubbleSort(char arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
            }
}

// 手写去重代码
void removeRepeat(char arr[], int n)
{
    int curr = 0;
    char newStr[n];
    for (int i = 0; i < n; i++)
        // 将不重复的元素存入新数组
        if (arr[i] != arr[i + 1])
            newStr[curr++] = arr[i];

    for (int i = 0; i < curr; i++)
        arr[i] = newStr[i];
    arr[curr] = '\0';
}

int main()
{
    char str[100];
    cin >> str;
    int n = strlen(str);
    bubbleSort(str, n);
    removeRepeat(str, n);

    /* 库函数去重代码
    int x = unique(str, str + n) - str; // 去重
    for (int i = 0; i < x; i++)
        cout << str[i];
    */
    cout << str;
    return 0;
}

4、数组异或

【问题描述】

从标准输入中输入两组整数(每行不超过 20 个整数，每组整数中元素不重复),合并两组整数，去掉在两组整数中都出现的整数，并按从小到大顺序排序输出（即两组整数集;异或;）

【输入形式】

首先输入第一组整数的个数，再输入第一组整数，以空格分隔；然后输入第二组整数的个数，再输入第二组整数，以空格分隔。

【输出形式】

按从小到大顺序排序输出合并后的整数（去掉在两组整数中都出现的整数），输出整数间以一个空格分隔，最后不含回车符。

【样例输入】

8
5 1 4 3 8 7 9 64
5 2 8 10

【样例输出】

1 2 3 4 6 7 9 10

/*
数组异或
安润鲁 2020-05-19 08:41:32
*/
#include <iostream>
using namespace std;

// 冒泡排序
void bubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
}

// 数组异或
void xorArr(int arr1[], int n1, int arr2[], int n2, int newArr[], int &curr)
{
    int flag = 1;
    curr = 0;
    for (int i = 0; i < n1; i++)
    {
        // 如果当前元素在另一个数组中存在，则设 flag=0
        flag = 1;
        for (int j = 0; j < n2; j++)
            if (arr1[i] == arr2[j])
            {
                flag = 0;
                break;
            }
        if (flag == 1)
            newArr[curr++] = arr1[i];
    }
    for (int i = 0; i < n2; i++)
    {
        flag = 1;
        for (int j = 0; j < n1; j++)
            if (arr2[i] == arr1[j])
            {
                flag = 0;
                break;
            }
        if (flag == 1)
            newArr[curr++] = arr2[i];
    }
}

// 格式化输出
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        if (i == n - 1)
            cout << arr[i];
        else
            cout << arr[i] << " ";
}

int main()
{
    int n1, n2, n;
    int nums1[20], nums2[20];
    int nums[40];

    // 输入数据
    cin >> n1;
    for (int i = 0; i < n1; i++)
        cin >> nums1[i];
    cin >> n2;
    for (int i = 0; i < n2; i++)
        cin >> nums2[i];

    // 数组异或算法
    xorArr(nums1, n1, nums2, n2, nums, n);
    // 排序
    bubbleSort(nums, n);
    // 输出
    display(nums, n);

    return 0;
}

/*
数组异或解法2
安润鲁 2020-05-19 08:41:32
*/
#include <iostream>
using namespace std;

// 冒泡排序
void bubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
}

// 数组异或
void xorArr(int arr1[], int n1, int arr2[], int n2, int newArr[], int &curr)
{
    int i = 0, j = 0;
    while (i < n1 && j < n2)
    {
        if (arr1[i] < arr2[j])
            newArr[curr++] = arr1[i++];
        else if (arr1[i] > arr2[j])
            newArr[curr++] = arr2[j++];
        else if (arr1[i] == arr2[j])
            i++, j++;
    }

    if (i < n1)
        for (; i < n1; i++)
            newArr[curr++] = arr1[i];
    if (j < n2)
        for (; j < n2; j++)
            newArr[curr++] = arr2[j];
}

// 格式化输出
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        if (i == n - 1)
            cout << arr[i];
        else
            cout << arr[i] << " ";
}

int main()
{
    int n1, n2, n;
    int nums1[20], nums2[20];
    int nums[40];

    // 输入数据
    cin >> n1;
    for (int i = 0; i < n1; i++)
        cin >> nums1[i];
    cin >> n2;
    for (int i = 0; i < n2; i++)
        cin >> nums2[i];

    // 排序数组
    bubbleSort(nums1, n1);
    bubbleSort(nums2, n2);

    // 数组异或算法
    xorArr(nums1, n1, nums2, n2, nums, n);

    // 输出
    display(nums, n);

    return 0;
}

5、学生成绩排序（结构体数组排序）

【问题描述】

对某班学生成绩排序。从键盘依次输入某班学生的姓名和成绩（一个班级人数最多不超过 50 人）并保存，然后分别按学生成绩由高到低顺序输出学生姓名和成绩，成绩相同时，则按输入次序排序。

【输入形式】

从键盘依次输入最多不超过 50 个学生的学生姓名和成绩： 第一行输入班级学生人数； 在单独行上输入空格隔开的学生姓名和成绩，其中学生成绩是整数。

【输出形式】

按学生成绩由高到低顺序输出学生姓名和成绩，每行输出一位学生的姓名和成绩，其中姓名（英文）占 15 位，成绩占 5 位，均按缺省方式对齐。成绩相同时按输入次序排序。

【输入样例】

4
aaa 50
bbb 70
ccc 65
ddd 90

【输出样例】

############ddd###90
############bbb###70
############ccc###65
############aaa###50

/*
学生成绩排序(结构体数组排序)
安润鲁 2020-05-19 09:35:12
*/
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
typedef struct stu
{
    string name;
    int score;
} stu;

// 输入数据
void getData(stu s[], int n)
{
    for (int i = 0; i < n; i++)
        cin >> s[i].name >> s[i].score;
}

// 冒泡排序
void bubbleSort(stu s[], int n)
{
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (s[j].score < s[j + 1].score)
            {
                swap(s[j], s[j + 1]);
            }
}

// 输出数据
void display(stu s[], int n)
{
    for (int i = 0; i < n; i++)
        cout << setw(15) << right << s[i].name << setw(5) << right << s[i].score << endl;
}

int main()
{
    int n;
    cin >> n;
    stu stus[n];
    getData(stus, n);
    bubbleSort(stus, n);
    display(stus, n);
    return 0;
}

评论交流

最后，如果你觉得笔记对你有帮助，不妨赞赏一杯可乐😅

QQ 交流群 217394861