没想到！STL中sort有如此多亲戚邻居

用户9831583

发布于 2022-06-16 15:17:34

2010

发布于 2022-06-16 15:17:34

文章被收录于专栏：码出名企路

sort可谓是排序鼻祖，今天就来挖挖她的亲戚邻居！

1.sort()

默认升序：

 //默认less
    std::vector<int> numbers {99, 77, 33, 66, 22, 88, 44, 88};
    std::sort(std::begin(numbers), std::end(numbers));
    std::copy(std::begin(numbers), std::end(numbers),
            ostream_iterator<int> {std::cout," "}) ;
    cout<<endl;

中间段序列排序：

//可以对中间某段元素排序
    std::sort(++std::begin(numbers),--std::end(numbers));
    std::copy(std::begin(numbers), std::end(numbers),
            ostream_iterator<int> {std::cout," "}) ;
     cout<<endl;

降序排列：

 //降序排列
    std::sort(std::begin(numbers), std::end(numbers), std::greater<int>());
    std::copy(std::begin(numbers), std::end(numbers),
            ostream_iterator<int> {std::cout," "}) ;
    cout<<endl;

labmda表达式自定义函数排序：

   //labmda表达式自定义比较函数
    std::deque<string> words { "one", "two", "nine", "nine", "one", "three", "four", "five", "six" };
    std::sort(std::begin(words), std::end(words),
            [](const string& s1, const string& s2) { return s1.back()> s2.back();});//最后一个字母做比较
    std::copy(std::begin(words), std::end(words),
            std::ostream_iterator<string> {std::cout," "}); // six four two one nine nine one three five
     cout<<endl;

注意：sort排序会打乱相等元素的顺序

2. stable_sort()

调整为：

//sort算法可能会改变相等元素的顺序
    //stable_sort()算法可以对一段元素进行排序并保证维持相等元素的原始顺序
    std::vector<int> numbers1{99, 77, 33, 66, 22, 88, 44, 88};
    std::stable_sort(std::begin(numbers1), std::end(numbers1));
    std::copy(std::begin(numbers1), std::end(numbers1),
            ostream_iterator<int> {std::cout," "}) ;
    cout<<endl;

3.partial_sort()

部分排序：

需要 3 个随机访问迭代器 first、second 和 last，[first，second) 会包含降序序列 [first，last) 中最小的 second-first 个元素。

 //部分排序
    size_t count {5};
    std::vector<int> numbers2{22, 7, 93, 45, 19, 56, 88, 12, 8, 7, 15, 10};
    std::partial_sort(std::begin(numbers2), std::begin(numbers2) + count, std::end(numbers2));
    std::copy(std::begin(numbers2), std::end(numbers2),
            ostream_iterator<int> {std::cout," "}) ;
    cout<<endl;

注意：不能保持未排序元素的原始顺序。元素的顺序是不确定的，这取决于我们的实现。

改为降序：

//前五个改为降序
    std::partial_sort(std::begin(numbers2), std::begin(numbers2) + count, std::end(numbers2) , std::greater<int>());
    std::copy(std::begin(numbers2), std::end(numbers2),
            ostream_iterator<int> {std::cout," "}) ;
    cout<<endl;

4.partial_sort_copy()

复制排序：

将排序元素复制到一个不同的容器中，它的前两个参数是指定部分排序应用范围的迭代器；第 3 个和第 4 个参数是标识结果存放位置的迭代器。

 //把排序后的部分元素重新保存在一个容器中，原来元素顺序不变
    std::vector<int> numbers3{22, 7, 93, 45, 19, 56, 88, 12, 8, 7, 15, 10};
    size_t count3{5};
    std::vector<int> result(count3);
    std::partial_sort_copy(std::begin(numbers), std::end(numbers), std::begin (result) , std::end (result));
    std::copy(std::begin(numbers3), std::end(numbers3), std::ostream_iterator<int>{std::cout," " });
    std::cout << std::endl;
    std::copy(std::begin(result), std::end(result),std::ostream_iterator <int> {std::cout, " "});
    std::cout << std::endl;

倒序：

std::partial_sort_copy(std::begin(numbers), std::end(numbers), std::begin(result), std::end(result),std::greater<int>());

5.nth_element() 在第 n 个元素之前的元素都小于第 n 个元素，而且它后面的每个元素都会比它大。

//找到小于某个数的数字序列
    std::vector<int> numbers4{22, 7, 93, 45, 19, 56, 88, 12, 8, 7, 15, 10};
    size_t count4 {5};
    std::nth_element(std::begin(numbers4), std::begin(numbers4) + count4, std::end(numbers4));
    std::copy(std::begin(numbers4), std::end(numbers4),std::ostream_iterator <int> {std::cout, " "});
    std::cout << std::endl;

第 n 个元素之前的元素都小于它，但不必是有序的。同样，第 n 个元素后的元素都大于它，但也不必是有序的。

自定义比比较函数：

std::nth_element(std::begin(numbers4), std::begin(numbers4) + count4, std::end(numbers4) , std::greater<int>());

6.is_sorted()

测试元素段是否已经排好序可以避免不必要的排序操作。

如果两个迭代器参数所指定范围内的元素是升序排列的，函数模板 is_sorted() 就会返回 true。

   //排序之前测试下是否已经排好序，省去了多余的排序
    std::vector<int> numbers5{22, 7, 93, 45, 19};
    std::vector<double> data{1.5, 2.5, 3.5, 4.5};
    std::cout << "numbers is "<<(std::is_sorted(std::begin(numbers5), std::end(numbers5)) ? "": "not ")
            << "in ascending sequence.\n";
    std::cout << "data is "<< (std::is_sorted(std::begin(data), std::end(data)) ?"":"not ")
             << "in ascending sequence." << std::endl;

自定义输出：

//自定义输出
    std:: cout << "data reversed is "<< (std::is_sorted(std::begin(data),
                    std::end(data), std::greater<double>()) ? "":"not ")<< "in descending sequence." << std::endl;

7.is_sorted_until()

来判断一个元素段是否有序,返回一个指向这段元素中升序序列上边界元素的迭代器。

//判断结果返回其中一个元素
    std::vector<string> pets{"cat", "chicken", "dog", "pig", "llama", "coati", "goat"};
    std::cout << "The pets in ascending sequence are:\n";
    std::copy(std::begin(pets), std::is_sorted_until(std::begin(pets), std::end (pets)) ,  std::ostream_iterator<string>{ std::cout," "});

"llama"是小于其前者的第一个元素，所以”pig”就是升序序列的第一个元素。

自定义:

  
std::vector<string> pets {"dog", "coati", "cat", "chicken", "pig", "llama", "goat"};
    std::cout << "The pets in descending sequence are:\n";
    std::copy(std::begin(pets),std::is_sorted_until(std::begin(pets), std::end (pets) , std::greater<string>()),std::ostream_iterator<string>{ std::cout," "});

8.合并两个有序序列merge()

合并操作会合并两个有相同顺序的序列中的元素，可以是两个升序序列，也可以是两个降序序列。结果会产生一个包含来自这两个输入序列的元素副本的序列，并且排序方式和原始序列相同.

//合并排序序列，并返回一个副本
    std::vector<int> these{2, 15, 4, 11, 6, 7};
    std::vector<int> those {5, 2, 3, 2, 14, 11, 6};
    std::stable_sort(std::begin(these), std::end(these),std::greater<int>());
    std::stable_sort(std::begin(those), std::end(those), std::greater<int>());
    std::vector<int> result6(these.size() + those.size() + 10);
    auto end_iter = std::merge(std::begin(these), std::end(these),std::begin(those), std::end(those),
            std::begin (result6), std::greater<int>());
    std::copy(std::begin (result6), end_iter, std::ostream_iterator<int>{std::cout, " "});

9.inplace_merge()

合并同一个序列中两个连续有序的元素序列。

data 容器有两个序列，并且都是升序序列。inplace_merge() 操作将它们合并为同一容器中的升序序列。

键盘输入，sort排序案例：

.h

 #ifndef NAME_H
    #define NAME_H
    #include <string>                              
    class Name
    {
    private:
        std::string first {};
        std::string second {};
    public:
        Name(const std::string& name1, const std::string& name2) : first(name1), second(name2){}
        Name()=default;
        std::string get_first() const { return first; }
        std::string get_second() const { return second; }
        friend std::istream& operator>>(std::istream& in, Name& name);
        friend std::ostream& operator<<(std::ostream& out, const Name& name);
    };
    
    inline std::istream& operator>>(std::istream& in, Name& name)
    {
        return in >> name.first >> name.second;
    }
  
    inline std::ostream& operator<<(std::ostream& out, const Name& name)
    {
        return out << name.first << " " << name.second;
    }
    #endif

.cpp

 #include <iostream>                            
    #include <string>                              
    #include <vector>                              
    #include <iterator>                            
    #include <algorithm>                            
    #include "s.h"
    int main()
{
        std::vector<Name> names;
        std::cout << "Enter names as first name followed by second name. Enter Ctrl+Z to end:";
        std::copy(std::istream_iterator<Name>(std::cin), std::istream_iterator<Name>(),
                    std::back_insert_iterator<std::vector<Name>>(names));
        std::cout << names.size() << " names read. Sorting in ascending sequence...\n";

        std::sort(std::begin(names), std::end(names),
                     [](const Name& name1, const Name& name2) {return name1.get_second() < name2.get_second(); });
        std::cout << "\nThe names in ascending sequence are:\n";
        
        std::copy(std::begin(names), std::end(names), std::ostream_iterator<Name>(std::cout, "\n"));
    }

结果显示：