STL 部分排序partial_sort和stable_sort稳定排序

ゝ一纸荒年。 2024-02-18 23:12 54阅读 0赞

partial\_sort接受一个middle迭代器，使序列中的middle-first个最小元素以递增顺序排序，置于\[first, middle)内。下面是测试代码：

#include <iostream>
    #include <vector>
    #include <algorithm>
     
    using namespace std;
     
    int main()
    {
        int a[] = {10,9,8,7,6,5,4,3,2,1,0};
        vector<int> vec(a, a+11);
        vector<int>::iterator b = vec.begin();
        vector<int>::iterator e = vec.end();
     
        partial_sort(b, b+6, e);     // 前6个最小元素排序
        while (b != e)
            cout << *(b++) << ' ';
        return 0;
    }

运行结果：

![SouthEast][]

从结果可以看出，前6个最小元素放在了前6个位置上，而剩下的元素则放于容器后面未排序。

实现partial\_sort的思想是：对原始容器内区间为\[first, middle)的元素执行make\_heap()操作构造一个最大堆，然后拿\[middle, last)中的每个元素和first进行比较，first内的元素为堆内的最大值。如果小于该最大值，则互换元素位置，并对\[first, middle)内的元素进行调整，使其保持最大堆序。比较完之后在对\[first, middle)内的元素做一次对排序sort\_heap()操作，使其按增序排列。注意，堆序和增序是不同的。

stable\_sort 稳定排序， 头文件还是algorithm，

对给定区间所有元素进行稳定排序，就是相等的元素位置不变，原来在前面的还在前面。

stable\_sort(b.begin(),b.end()) 和sort函数类似

[SouthEast]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/c997aac9d40141aaa083e0a153b3eca1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，54人围观）

还没有评论，来说两句吧...

相关阅读

相关 STL 部分排序partial_sort和stable_sort稳定排序 is_sorted 函数 partial_sort_copy函数

今天才知道STL有这么多神兵利器~~~ partial\_sort接受一个middle迭代器，使序列中的middle-first个最小元素以递增顺序排序，置于\[first,

爱被打了一巴掌/ 2024年02月18日 23:12/ 0 赞/ 66 阅读

相关 STL 部分排序partial_sort和stable_sort稳定排序

partial\_sort接受一个middle迭代器，使序列中的middle-first个最小元素以递增顺序排序，置于\[first, middle)内。下面是测试代码：

ゝ一纸荒年。/ 2024年02月18日 23:12/ 0 赞/ 55 阅读

相关稳定排序和不稳定排序

这几天笔试了好几次了，连续碰到一个关于常见排序算法稳定性判别的问题，往往还是多选，对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目，当然如果你笔试之前已经记住了数据结

拼搏现实的明天。/ 2022年07月17日 03:23/ 0 赞/ 189 阅读

相关稳定排序和不稳定排序

这几天笔试了好几次了，连续碰到一个关于常见排序算法稳定性判别的问题，往往还是多选，对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目，当然如果你笔试之前已经记住了数据

淡淡的烟草味﹌/ 2022年06月18日 09:38/ 0 赞/ 179 阅读

相关稳定排序：归并排序

归并排序：对于给定的一组长度为n的记录，利用分治和递归的思想，将记录分为一个个长度为1的子序列，最后再用递归方法将排好序的子序列合并成为越来越大的有序序列。此方法称为2-路归并

约定不等于承诺〃/ 2022年06月17日 07:44/ 0 赞/ 182 阅读

相关稳定排序：冒泡排序

实现思路：不停地使数组中的相邻的左右两个元素对比大小，大的元素往右移，因为是左右交换，所以如果他们相等，肯定不会交换。所以是稳定的。【平均时间复杂度】：O(n^2);

你的名字/ 2022年06月17日 06:51/ 0 赞/ 196 阅读

相关稳定排序：插入排序

插入排序：每次从【无序表】中取出第一个元素。把它插入的到有序列表中的合适位置。实现思路：第一趟比较前两个数，然后把第二个数按大小插入到有序表中；第二趟把

超、凢脫俗/ 2022年06月17日 06:37/ 0 赞/ 188 阅读

相关稳定排序之插入排序

插入排序（Insertion Sorting）就是每次都将一个无序的待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。比较顺序是有序部分的从右到左（从大到

清疚/ 2022年06月16日 12:56/ 0 赞/ 204 阅读

相关稳定排序和不稳定排序

转载自：http://www.cnblogs.com/codingmylife/archive/2012/10/21/2732980.html 这几天笔试了好几次了，连续碰到

野性酷女/ 2022年06月09日 05:10/ 0 赞/ 205 阅读

相关稳定排序和不稳定排序

稳定排序和不稳定排序 1.如何区分？ 2.稳定性意义的探讨 1.如何区分？稳定排序：排序前后两个相等的数相对位置不变，则算法稳定非稳定排序：排

╰+攻爆jí腚メ/ 2022年04月23日 01:28/ 0 赞/ 237 阅读