cb50a_c++_STL_算法_局部排序partial_sort

/*cb50a_c++_STL_算法_局部排序partial_sort

partial_sort(b,se,e)排序一部分,begin,source end,end
cout << "部分排序，开头的5个数排序" << endl;
partial_sort(ideq.begin(), ideq.begin() + 5, ideq.end());

需要注意的是，不能保持未排序元素的原始顺序。在执行 partial_sort() 后后面元素的顺序是不确定的，这取决于具体的实现。

partial_sort(b,se,e,p), begin,source end,end,paramete
partial_sort(ideq.begin(), ideq.begin() + 5, ideq.end(),greater<int>());//从大到小


partial_sort_copy(sb,se,db,de) 边排序边copy，sb(source begin),se(source end),db(destination begin)
partial_sort_copy(sb,se,db,de,p)

排序算法：
sort() 排序
stable_sort()稳定排序
https://www.cnblogs.com/txwtech/p/12366186.html

partial_sort()
partial_sort_copy(sb,se,db,de),
nth_element()

partition()分区
stable_partition()稳定分区
https://www.cnblogs.com/txwtech/p/12365880.html


make_heap()
push_heap()
pop_heap()
sort_heap()


greater<int>()是一个泛型

3,4,5,6,7,2,3,4,5,6,1,2,3,4,5

//

原理参考：
partial_sort 原理概述
那么 partial_sort 的原理是什么呢？是堆排序！

partial_sort的原理：

对原始容器内区间为[first, middle)的元素执行 make_heap() 操作构造一个大顶堆，
然后遍历剩余区间[middle, last)中的元素，剩余区间的每个元素均与大顶堆的堆顶元素进行比较（大顶堆的堆顶元素为最大元素，该元素为第一个元素，很容易获得），若堆顶元素较小，则交换堆顶元素和遍历得到的元素值（pop_heap ），并重新调整该大顶堆以维持该堆为大顶堆（adjust_heap）。
遍历结束后，[first, middle)区间内的元素便是排名在前的m个元素，再对该堆做一次堆排序 sort_heap() 便可得到最后的结果。

STL之partial_sort算法源码讲解
https://blog.csdn.net/ggq89/article/details/88817085
*/
#include <iostream>
#include <algorithm>
#include <deque>
#include <functional>

using namespace std;

template <typename TT9>
void print9(TT9 &ideq)
{
    for (TT9::iterator iter = ideq.begin(); iter != ideq.end(); ++iter)
        cout << *iter << ' ';
    cout << endl;

}

int main()
{
    deque<int> ideq;
    for (int i = 3; i <= 7; ++i)
        ideq.push_back(i);
    for (int i = 2; i <= 6; ++i)
        ideq.push_back(i);
    for (int i = 1; i <= 5; ++i)
        ideq.push_back(i);
    print9(ideq);

    cout << "部分排序，开头的5个数排序" << endl;
    partial_sort(ideq.begin(), ideq.begin() + 5, ideq.end());//默认从小到大，less<int>()
    print9(ideq);

    partial_sort(ideq.begin(), ideq.begin() + 5, ideq.end(),greater<int>());//从大到小

    print9(ideq);

    return 0;
}

/*

*/

#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <functional>
#include <iterator>

using namespace std;

template <class TT99>
void print99(TT99 ideq)
{
    for (TT99::iterator iter = ideq.begin(); iter != ideq.end(); ++iter)
        cout << *iter << ' ';
    cout << endl;
}

int main()
{
    deque<int> ideq;
    vector<int> ivec6(6);
    vector<int> ivec30(30);

    for (int i = 3; i <= 7; ++i)
        ideq.push_back(i);
    for (int i = 2; i <= 6; ++i)
        ideq.push_back(i);
    for (int i = 1; i <= 5; ++i)
        ideq.push_back(i);
    print99(ideq);

    partial_sort_copy(ideq.begin(), ideq.end(), ivec6.begin(), ivec6.end());

    //print99(ivec6);
    cout << "copy到cout里面" << endl;
    copy(ivec6.begin(), ivec6.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    //用一个迭代器接受partial_sort_copy返回的结果，迭代器的位置
    vector<int>::iterator pos;
    pos=partial_sort_copy(ideq.begin(), ideq.end(), ivec30.begin(), ivec30.end());
    cout << "直接调用自定义的函数，显示全部" << endl;
    print99(ivec30);
    cout << "只显示copy的部分，" << endl;

    for (vector<int>::iterator iter = ivec30.begin(); iter != pos; ++iter)
        cout << *iter << ' ';
    cout << endl;

    return 0;
}