关于C++ STL sort()函数的拓展应用

September 25, 2019 · 算法 · 945次阅读
原题来自洛谷P1068,由于本题涉及了sort函数排序的更多应用,因此写下这篇文章供之后参考。

1.对vector数组的排序应用及关于自定义优先级的排序设定

由于sort函数是线性数据排序,因此并不支持如map这类使用红黑树这样非线性结构数据的排序。解决办法是自定义pair数据类型的vector数组,再将map中Key-Value映射到vector中,最后利用vector结合sort函数进行排序。另外,本题中要求若数据二(分数)相等则将数据一(学号)升序排序,否则按照数据一降序排序。这样的要求使得sort默认排序方式不满足要求,具体做法是自定义一个含有排序规则判断的函数,再将函数名作为sort函数参数传入。本方法也适用于多个优先级规则的自定义,但具体效果仍待进一步尝试。

代码如下:

    //这里仅贴入主要代码供参考
    typedef pair<int, int> p;
    vector<p> v;
    bool c_b_y(const p &p1, const p &p2) {
    if(p1.second==p2.second)return p1.first < p2.first;//分数相等比学号
    else return p1.second > p2.second;//学号相等比分数
    }
    int main() {
        sort(v.begin(), v.end(), c_b_y);//使用自定义优先级的排序方法进行排序
        //........
    }

2.关于区间排序的具体应用

刚开始拿到题目时,首先想到的是对数据的某一部分单独排序以达到对数据一(学号)单独排序的目的。尽管最后舍弃了这种做法,但通过尝试发现.....嗯....区间排序确实可以做到,但可能发生奇怪的bug。基础做法如下:

    int a[10]={3, 1, 4, 1, 5, 9, 2, 6, 7, 0};
    sort(a+2,a+5);//这样就做到了对1 4 1三个数字的单独排序,而不改变其他数字的原有顺序

该方法在使用vector时存在部分排序成功部分未排序的情况。

none

最后编辑于4年前

添加新评论