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

爱被打了一巴掌 2024-02-18 23:12 65阅读 0赞

今天才知道STL有这么多神兵利器~~~

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函数类似

partial\_sort（）函数，进行部分排序。

用法：

1.partial\_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);

2.partial\_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);

更多资料点这里：http://www.cplusplus.com/reference/algorithm/partial\_sort/

// partial_sort.cpp : 定义控制台应用程序的入口点。
    //
    #include "stdafx.h"
    #include<iostream>
    #include<algorithm>
    #include<vector>
    using namespace std;
    bool compare(int a, int b)
    {
    	return(a > b);//降序
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int myints[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    	vector<int>vec(myints, myints + 9);
    	partial_sort(vec.begin(), vec.begin() + 5, vec.end());//对第0～5个元素进行排序
    	for (auto i : vec)
    	{
    		cout << i << ' ';
    	}
    	system("pause");
    	return 0;
    }

运行结果：

![Center][]

========分割线=========

三、partial\_sort\_copy(),对部分元素进行排序，并复制到另一个容器里。

用法：

1.partial\_sort\_copy (InputIterator first,InputIterator last, RandomAccessIterator result\_first,RandomAccessIterator result\_last);

2.partial\_sort\_copy (InputIterator first,InputIterator last, RandomAccessIterator result\_first,RandomAccessIterator result\_last, Compare comp);

(待排序的容器首指针，尾指针，接收元素的容器的首指针，尾指针)

// partial_sort_copy.cpp : 定义控制台应用程序的入口点。
    //
    #include "stdafx.h"
    #include <iostream>     // std::cout
    #include <algorithm>    // std::partial_sort_copy
    #include <vector>       // std::vector
    using namespace std;
    bool compare(int i, int j)
    {
    	return (i>j);
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int myints[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    	vector<int> vec(5);
    	partial_sort_copy(myints, myints + 9, vec.begin(), vec.end());
    	cout << "vec contains:";
    	for (auto it : vec)
    	{
    		std::cout << ' ' << it;
    	}
    	std::cout << '\n';
    	system("pause");
    	return 0;
    }

运行结果：

![Center 1][]

=======分割线==========

四、is\_sorted(),判断一系列元素是否有序

// is_sorted.cpp : 定义控制台应用程序的入口点。
    //
    #include "stdafx.h"
    #include<iostream>
    #include<algorithm>
    #include<array>
    using namespace std;
    int _tmain(int argc, _TCHAR* argv[])
    {
    	array<int, 5> ar = { 1, 2, 3, 4, 5 };
    	cout << is_sorted(ar.begin(), ar.end());//判断一系列元素是否有序，是就返回1
    	cout << endl;
    	system("pause");
    	return 0;
    }

运行结果：

![Center 2][]

=======分割线==========

五、is\_sorted\_until(),返回有序元素后面无序的第一个元素的指针

用法：

1.is\_sorted\_until (ForwardIterator first, ForwardIterator last);

2.is\_sorted\_until (ForwardIterator first, ForwardIterator last, Compare comp); //Compare comp自定义比较规则

#include "stdafx.h"
    #include <iostream>     // std::cout
    #include <algorithm>    // std::is_sorted_until, std::prev_permutation
    #include <array>
    using namespace std;
    int _tmain(int argc, _TCHAR* argv[])
    {
    	array<int, 4> foo={2,3,-5,0};//2、3有序，-5无序
    	array<int, 4>::iterator it;
    	it =is_sorted_until(foo.begin(), foo.end());//返回指向-5的指针
    	cout << *it;
    	cout << endl;
    	system("pause");
    	return 0;
    }

运行结果：

![Center 3][]

STL中的nth\_element()方法的使用 通过调用nth\_element(start, start+n, end)  
方法可以使第n大元素处于第n位置（从0开始,其位置是下标为  
n的元素），并且比这个元素小的元素都排在这个元素之前，比这个元素大的元素都排在这个元素之后，但不能保证他们是有序的，下面是这个方法的具体使用方法.

![复制代码][copycode.gif]

1 #include <iostream>
     2 
     3 #include <algorithm>
     4 
     5 #include <functional>
     6 
     7 #include <vector>
     8 
     9 using namespace std;
    10 
    11 
    12 
    13 int main()
    14 
    15 {
    16 
    17     const int VECTOR_SIZE = 50 ;
    18 
    19 
    20 
    21     vector<int> Numbers(VECTOR_SIZE) ;
    22 
    23 
    24 
    25     vector<int>::iterator start, end, it ;
    26 
    27 
    28 
    29     // Initialize vector Numbers
    30 
    31     for(int i=0;i<50;++i){
    32 
    33              Numbers[i]=i;
    34 
    35     }
    36 
    37 /*由于赋值时是有序的，下面random_shuffle()方法将这些数据的顺序打乱*/
    38 
    39     random_shuffle(Numbers.begin(),Numbers.end());
    40 
    41     
    42 
    43 // location of first element of Numbers
    44 
    45     start = Numbers.begin() ; 
    46 
    47 
    48 
    49  // one past the location last element of Numbers
    50 
    51     end = Numbers.end() ;     
    52 
    53 
    54 
    55     cout << "Before calling nth_element/n" << endl ;
    56 
    57 
    58 
    59   // print content of Numbers
    60 
    61     cout << "Numbers { " ;
    62 
    63     for(it = start; it != end; it++)
    64 
    65         cout << *it << " " ;
    66 
    67     cout << " }/n" << endl ;
    68 
    69 
    70 
    71   /* 
    72 
    73     * partition the elements by the 8th element，
    74 
    75   *（notice that 0th is the first element）
    76 
    77   */ 
    78 
    79     nth_element(start, start+8, end) ;
    80 
    81 
    82 
    83     cout << "After calling nth_element/n" << endl ;
    84 
    85 
    86 
    87     cout << "Numbers { " ;
    88 
    89     for(it = start; it != end; it++)
    90 
    91         cout << *it << " " ;
    92 
    93     cout << " }/n" << endl ;
    94 
    95     system("pause");
    96 
    97 }

[SouthEast]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/c4e005d384014e30b6b747e13345ba19.png
[Center]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/dbef8bbf15d44dc587c5ec6ef400b467.png
[Center 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/4b7efcf6dcf141968c9697588ad2d57b.png
[Center 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/45e5fc4cd461401dbafd92356f759f5a.png
[Center 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/3ee3e21589dd4f2db7f16010dfd85e13.png
[copycode.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/71b6f0a392e1471ca953c91c2de510e6.png