首页 > 编程语言 >PTA 21级数据结构与算法实验8—排序

PTA 21级数据结构与算法实验8—排序

时间：2022-11-28 21:26:37浏览次数：63  
标签：std 数据结构 21 int 插入排序 PTA ++ using 排序

目录

7-1 统计工龄

代码 :

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N], d[110];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    for (int i = 0; i < n; i++) d[a[i]] ++;

    for (int i = 0; i <= 50; i++) {
        if (d[i]) printf("%d:%d\n", i, d[i]);
    }
    
    return 0;
}

7-2 寻找大富翁

代码 :

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int a[N];

// 快排
void qsort(int l, int r){
    if (l >= r) return;
    
    int i = l - 1, j = r + 1;
    int x = a[l + r >> 1];
    while (i < j){
        do i++; while (a[i] > x);
        do j--; while (a[j] < x);
        if (i < j) swap(a[i], a[j]);
    }
    
    qsort(l, j);
    qsort(j + 1, r);
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    qsort(1, n);
    
    // m 有可能小于 n, 取个最小值
    for (int i = 1; i <= min(m, n); i++) {
        if (i == 1) printf("%d", a[i]);
        else printf(" %d", a[i]);
    }
    return 0;
}

7-3 点赞狂魔

题意 :

​ 给 N 个用户, 每个用户有个 Name 和 K 个特性编号 Fi ; 找出每个人点赞不同编号的数量, 并输出数量最大的前三名; 如果有并列, 就输出标签出现次数平均值最小的那个, 若不足3人，则用-补齐缺失

代码:

#include <bits/stdc++.h>
using namespace std;

struct Node {
    char name[10];
    int cnt, k; // cnt 存不同标签数量, k 存所有标签数量
} p[110];

set<int> s;	// set 去重

// 排序规则
bool cmp(Node a, Node b) {
    if (a.cnt != b.cnt) return a.cnt > b.cnt;
    return a.k < b.k;
}

int main() {
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> p[i].name >> p[i].k;
        s.clear();
        int x;
        for (int j = 0; j < p[i].k; j++) {
            scanf("%d", &x);
            s.insert(x);
        }
        p[i].cnt = s.size();
    }
    
    // 根据题目规则排序
    sort(p + 1, p + n + 1, cmp);
    
    if (n == 0) printf("- - -\n");
    else if (n == 1) printf("%s - -\n", p[1].name);
    else if (n == 2) printf("%s %s -\n", p[1].name, p[2].name);
    else printf("%s %s %s\n", p[1].name, p[2].name, p[3].name);
    
    return 0;
}

7-4 插入排序还是归并排序

题意:

​ 给出两个长度为 N 的序列, 第一行代表初始状态, 第二行代表插入排序 (归并排序) 的中间序列; 判断是用的插入排序还是归并排序, 并输出用该排序算法再迭代一轮的结果序列

思路 :

​ 对于插入排序, 因为每次都是从序列头中拿出一个, 插入到排好的序列中, 所以对于一个长度为 n 的序列, 如果是插入排序, 前 k 个数应该是排好序的, 而后 n - k 个数中 a[i] == b[i], 这样就能找到 k, 并排序前 k + 1 的长度

​ 对于归并排序, 因为它每次都是取半递归排序, 所以要找到最小的已经排好序的子段长度 len, 然后再按照 2 * len 的子段长度归并排序

代码参考博客地址: 博客园 kingwzun

代码 :

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int a[N], b[N];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
	
    // 先判断是不是插入排序
    int flag = 0;
    int k = 0;
    for (int i = 1; i < n; i++) {
        if (flag == 0 && b[i] < b[i - 1]) k = i, flag = 1;	// 看前面排好序的递增序列
        // 如果 k 到 n 间 a[i], b[i] 不全相等, 说明不是插入排序
        if (flag == 1 && b[i] != a[i]) {
            flag = 2;
            break;
        }
    }

    if (flag == 1) {
        cout << "Insertion Sort" << endl;

        sort(a, a + k + 1);

        for (int i = 0; i < n; i++) {
            if (i) cout << " " << a[i];
            else cout << a[i];
        }
    } else {
        cout << "Merge Sort" << endl;
		
        // 找到最小的排好序的子段
        int len = 0x3f3f3f3f;
        int cnt = 1;
        for (int i = 0; i < n - 1; i ++) {
            if (b[i] < b[i + 1]) cnt++;
            else len = min(len, cnt), cnt = 1;
        }

        len *= 2;
        for (int i = 0; i < n; i += len)
            sort(a + i, a + min(i + len, n));	// 这里和 n 取min值, 防止越界
            
        for (int i = 0; i < n; i++) {
            if (i) cout << " " << a[i];
            else cout << a[i];
        }
    }

    return 0;
}

7-5 插入排序还是堆排序

题意:

​ 同 7-4, 判断是插入排序还是堆排序, 并输出用该排序算法再迭代一轮的结果序列

思路

​ 插入排序同 7-4, 或者因为数据很小, 可以每次都排序判断

​ 对于堆排序, 题目是从长度为 n 开始, 每次对前 k 个序列取大根堆, 并将长度为 k 的序列里的第一个和最后一个交换, 直到 k == 0; 完整的一步迭代是 : 形成前 k 个数的大根堆, 并 swap(a[1], a[k]), 并且形成前 k - 1 个数的大根堆

代码参考博客地址 : CSDN 摺耳喵

代码 1 :

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int a[N], b[N], tmp[N];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    memcpy(tmp, a, sizeof (tmp));

    bool flag = 0;
    // 这里 i 一定要从 2 开始, 不然会被卡
    for (int i = 2; i <= n; i++) {
        sort(a, a + i);
        if (flag) {
            cout << "Insertion Sort" << endl;
            for (int j = 0; j < n; j++) {
                if (j) cout << " " << a[j];
                else cout << a[j];
            }
            break;
        }
        if (equal(a, a + n, b)) flag = 1;
    }

    if (!flag) {
        memcpy(a, tmp, sizeof (a));

        for (int i = n; i >= 1; i--) {
            make_heap(a, a + i);
            if (flag) {
                cout << "Heap Sort" << endl;
                for (int j = 0; j < n; j++) {
                    if (j) cout << " " << a[j];
                    else cout << a[j];
                }
                break;
            }
            if (equal(a, a + n, b)) flag = 1;
            swap(a[0], a[i - 1]);
        }
    }
    return 0;
}

代码 2 : 手写堆排序实现

// 注意 : 这里数组的下标是从 1 开始的

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int a[N], b[N], tmp[N];
int len;

// 大根堆
void down(int u) {
    int t = u;
    if (u * 2 <= len && a[t] < a[u * 2]) t = u * 2;
    if (u * 2 + 1 <= len && a[t] < a[u * 2 + 1]) t = u * 2 + 1;

    if (u != t) {
        swap(a[t], a[u]);
        down(t);
    }
}

void init() {
    for (int i = len / 2; i; i--) down(i);
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    
    memcpy(tmp, a, sizeof (a));

    bool flag = 0;
    for (int i = 2; i <= n; i++) {
        sort(a + 1, a + i + 1);
        if (flag) {
            cout << "Insertion Sort" << endl;
            for (int j = 1; j <= n; j++) {
                if (j != 1) cout << " " << a[j];
                else cout << a[j];
            }
            break;
        }
        if (equal(a, a + n, b)) flag = 1;
    }

    if (!flag) {
        memcpy(a, tmp, sizeof (a));

        flag = 0;
        for (int i = n; i >= 1; i--) {
            len = i;
            init();
            if (flag) {
                cout << "Heap Sort" << endl;
                for (int j = 1; j <= n; j++) {
                    if (j != 1) cout << " " << a[j];
                    else cout << a[j];
                }
                break;
            }
            if (equal(a, a + n, b)) flag = 1;
            swap(a[1], a[i]);
        }
    }
    return 0;
}

7-6 逆序对

思路 : 归并排序 求 逆序对

代码 :

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int a[N], tmp[N];
long long int sum = 0;

// 归并排序
void merge_sort(int l, int r) {
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else	// 这里 a[i] > a[j] 就说明 a[i] 到 a[mid] 间的数都大于 a[j] 并形成逆序对
            tmp[k++] = a[j++], sum += mid - i + 1; 
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];

    for (int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    merge_sort(1, n);

    cout << sum << endl;
    return 0;
}

7-7 堆排序

代码 :

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int h[N], len;

// 这里是大根堆
void down(int u) {
    int t = u;
    if (u * 2 <= len && h[t] < h[u * 2]) t = u * 2;
    if (u * 2 + 1 <= len && h[t] < h[u * 2 + 1]) t = u * 2 + 1;

    if (t != u) {
        swap(h[t], h[u]);
        down(t);
    }
}

void init() {
    for (int i = len / 2; i; i--) down(i);
}

int main() {
    int n;
    while (cin >> n) {

        for (int i = 1; i <= n; i++) cin >> h[i];
        len = n;
        init();

        for (int i = n; i > 1; i--) {
            swap(h[1], h[i]);
            len = i - 1;
            down(1);
            for (int j = 1; j <= n; j++) {
                if (j == 1)
                    printf("%d", h[j]);
                else
                    printf(" %d", h[j]);
            }
            printf("\n");
        }
    }
    return 0;
}

7-8 石子合并

代码参考博客地址 :
CSDN ACdreamers
星辰阁

代码 :

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int a[N], d[N];
int dp[N][N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        d[i] = d[i - 1] + a[i];
    }

    for (int h = 1; h <= n; h++) {
        for (int i = 1; i <= n; i++) {
            int j = i + h;
            if (j > n) continue;
            dp[i][j] = 0x3f3f3f3f;
            for (int k = i; k <= j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
            }
            dp[i][j] += d[j] - d[i - 1];
        }
    }

    cout << dp[1][n] << endl;
    return 0;
}

7-9 第k小

代码参考地址 : acwing

代码1 : 快排实现

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int a[N];

int quick_sort(int l, int r, int k) {
    if (l >= r) return a[k];

    int x = a[(l + r) >> 1], i = l - 1, j = r + 1;

    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    if (k <= j) quick_sort(l, j, k);
    else quick_sort(j + 1, r, k);
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    cout << quick_sort(0, n - 1, k - 1) << endl;

    return 0;
}

代码2 : 堆排序实现

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int h[N], len;

// 小根堆
void down(int u) {
    int t = u;
    if (u * 2 <= len && h[t] > h[u * 2]) t = u * 2;
    if (u * 2 + 1 <= len && h[t] > h[u * 2 + 1]) t = u * 2 + 1;

    if (u != t) {
        swap(h[u], h[t]);
        down(t);
    }
}

void init() {
    for (int i = len / 2; i; i--) down(i);
}

int main() {
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);

    len = n;
    init();
    for (int i = 1; i < k; i++) {
        swap(h[1], h[len]);
        len--;
        down(1);
    }

    cout << h[1] << endl;

    return 0;
}

7-10 快速排序的过程

代码 : 快速排序的模板很多, 但是这道题好像只能用这个模板 ( 不是很确定 )

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;

int a[N];
int n;

void quick_sort(int l, int r) {
    if (l > r) return;
    int x = a[l], i = l, j = r;

    while (i < j) {
        while (i < j && a[j] >= x) j--;
        while (i < j && a[i] <= x) i++;
        if (i < j) swap(a[i], a[j]); 
    }
    swap(a[l], a[j]);

    for (int k = 1; k <= n; k++) {
        cout << a[k] << " ";
    }
    cout << endl;
    quick_sort(l, j - 1);
    quick_sort(j + 1, r);
}

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];
    quick_sort(1, n);

    return 0;
}

标签：std,数据结构,21,int,插入排序,PTA,++,using,排序
From： https://www.cnblogs.com/oneway10101/p/16933640.html

相关文章

  • go源码学习（一）：数据结构-数组
    数组是相同类型元素的集合，在内存中对应一块连续的内存空间。数组类型是通过存储的元素类型以及能够存储的大小两个维度来决定的，一旦声明之后大小就不可更改。初始化go语......
  • 【779】R语言数据结构
    1.向量向量从数据结构上看就是一个线性表，可以看成一个数组。c()是一个创造向量的函数。R语言中的"下标"不代表偏移量，而代表第几个，也就是说是从1开始的！seq......
  • MyEclipse6.0中使用aptana插件，添加jquery提示功能
    MyEclipse6.0中使用aptana插件，添加jquery提示功能第一：查看当前MyEclipse集成的eclipse的版本，，查看路径   D:/MyEclipse6.0/eclipse/readme/readme_eclipse.html(以我的......
  • StoneDB 开源社区月刊 | 202210期
    StoneDB开源社区第四期月刊来啦！StoneDB开源社区10月的月度会议在11月3日晚上圆满落幕。本次会议是StoneDB开源社区的第四次月度会议，讨论场面之激烈史无前例！原计划一小时......
  • 常见8大数据结构
    8种数据结构，数组、链表、栈、队列、树、堆、图、哈希表。①、数组优点：按照索引查询元素的速度很快；按照索引遍历数组也很方便。缺点：数组的大小在创建后就确定......
  • DTCC | 2021中国图数据库技术大会链接分享
    DTCC|2021中国图数据库技术大会链接分享​​DTCC|2021中国图数据库技术大会链接分享​​​​一、新一代分布式架构​​​​二、数据流通与数据交易​​​​三、业务模型......
  • 数据结构初阶--二叉树介绍（基本性质+堆实现顺序结构）
    树的基本概念和结构树的相关概念节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为2叶节点或终端节点：度为0的节点称为叶节点；如上图：D、F、G、H为叶节点非......
  • 【JS】121-重温基础：流程控制和错误处理
    本文是 重温基础 系列文章的第二篇，需要让自己静下心来，学习，养成好习惯。本章节复习的是JS中的控制流语句，让我们能实现更多的交互功能。注意一点：在ES6之前，JS是没有块作用域......
  • 【算法】228-每周一练 之 数据结构与算法（Set）
    这是第四周的练习题，五一放假结束，该收拾好状态啦。欢迎关注我的个人主页&&个人博客&&个人知识库&&微信公众号“前端自习课”本周练习内容：数据结构与算法——Set这些......
  • redisOject 和 底层数据结构对应 学习笔记
    笔记摘抄自https://pdai.tech/md/db/nosql-redis/db-redis-data-type-enc.htmlredisObject查看编码命令setk11objectencodingk1setk2helloobjectencoding......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99