最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

全球今日报丨C++ 标准库 sort() / stable_sort() / partial_sort() 对比

来源：博客园

C++ STL标准库中提供了多个用于排序的Sort函数，常用的包括有sort() / stable_sort() / partial_sort(),具体的函数用法如下表所示：


(资料图片仅供参考)

函数用法
std::sort(first,last)对容器或数组first~last范围内的元素进行排序，默认升序排序
std::stable_sort(first,last)对容器或数组first~last范围内的元素进行排序，保持原有数组相对顺序，默认升序排序
std::partial_sort(first,middle,last)在容器或数组first~last范围内，查找最小（大）middle-first个元素排序，放入first-middle区间，默认升序

1. std::sort(first,last)

std::sort()是STL标准库提供的模板函数，用于对容器或者数组中指定的范围（first~last）元素进行排序，默认的排序方法是以元素的值的大小做升序排序，同时也可以指定其他的排序规则（如std::greater）,也可以自定义排序规则。

std::sort()函数底层基于快速排序进行实现，时间复杂度为N * log(N)，因此需要容器或者数组注意以下几点：

  • 容器的迭代器必须是随机访问迭代器，如std::array、std::vector、std::deque。
  • 如果采用默认的升序排序方法，则元素必须支持operate<运算符。
  • 自定义类对象容器使用std::sort()排序时，因为需要交换位置，所以必须提供拷贝构造函数和赋值运算符。
  • std::sort()无法保证相同元素的原始位置，这里的相同是指进行比较的结果为相等，而对象本身不相同。如果需要保持相对顺序相同，则应该使用std::stable_sort()

不同库对std::sort()的实现：libstdc++和libc++.

示例代码：

#include#include#include#includeusing namespace std;void Print(std::string message,const std::vector& vec){    cout << message << ": ";    for(const auto c : vec)cout << c << " ";    cout < myVector{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};    // 1. 以默认的排序规则    std::sort(myVector.begin(),myVector.end());    Print("Sorted Default", myVector);    // 2. 以标准库的greater函数进行排序    std::sort(myVector.begin(),myVector.end(),std::greater());    Print("Sorted Standard Compare Function",myVector);    // 3.以自定义的函数定义排序规则    // lamda 表达式    auto cmp1 = [](const int a,const int b)    {        return a < b;    };    std::sort(myVector.begin(),myVector.end(),cmp1);    Print("Sorted Lamda Function",myVector);    // 可调用对象    struct    {        bool operator()(const int a,const int b){return a > b;}    } cmp2;    std::sort(myVector.begin(),myVector.end(),cmp2);    Print("Sorted Function Object",myVector);    return 0;}

输出结果为：

Sorted Default : 0 1 2 3 4 5 6 7 8 9Sorted Standard Compare Function : 9 8 7 6 5 4 3 2 1 0Sorted Lamda Function : 0 1 2 3 4 5 6 7 8 9Sorted Function Object : 9 8 7 6 5 4 3 2 1 0

2. std::stable_sort(first,last)

使用std::sort()的一个问题是在排序时，无法保证值相等时的元素相对位置保持不变，如果程序中对相对顺序有要求，那么就需要使用std::stable_sort(),这是对std::sort()的一个升级版本，调用的方式和std::sort()相同，但是可以保证排序后的结果能够保持原有的相对顺序。

std::stable_sort()底层是基于归并排序，时间复杂度是N * log(N)^2,如果可以使用额外的内存空间，那么时间复杂度可以降低为N * log(N),std::sort()对容器和数组的要求与std::sort()相同。

不同库对std::stable_sort()的实现：libstdc++和libc++.

3. std::partial_sort(first,middle,last)

上述的std::sort()和std::stable_sort()都是对所选的范围内的所有数据进行排序，但是如果对于一个容器或者数组，我们只需要找到其最小的几个元素，那么采用全局排序的方法效率将会很低，尤其是容器中的元素数量非常大时，将会对性能产生很大的影响。因此，C++标准库提供了std::partial_sort()函数，来应用于这种场景。

std::partial_sort()函数的功能从其名字就可以得到，可以理解为部分排序，即从元素区间范围内取出部分元素进行排序。函数参数列表中first，last表示元素范围，middle用于定义需要进行排序的元素个数，具体的，std::partial_sort()会将范围first-last范围内最小（大）的middle-first个元素移动到first~middle范围，并对这些元素进行升（降）序排序。

std::partial_sort()底层采用堆排序，时间复杂度为N * log(M),其中N为last-first,M为middle-first。由于底层实现的限制，std::partial_sort()对容器的要求与std::sort()和std::stable_sort()相同。

不同库对std::stable_sort()的实现：libstdc++和libc++.

示例代码：

#include#include#include#includeusing namespace std;void Print(std::string message,const std::vector& vec){    cout << message << ": ";    for(const auto c : vec)cout << c << " ";    cout < myVector{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};    // 1. 以默认的排序规则    std::partial_sort(myVector.begin(),myVector.begin() + 4,myVector.end());    Print("Sorted Default", myVector);    // 2. 以标准库的greater函数进行排序    std::partial_sort(myVector.begin(),myVector.end(),std::greater());    Print("Sorted Standard Compare Function",myVector);    // 3.以自定义的函数定义排序规则    // lamda 表达式    auto cmp1 = [](const int a,const int b)    {        return a < b;    };    std::sort(myVector.begin(),myVector.end(),cmp1);    Print("Sorted Lamda Function",myVector);    return 0;}

Sorted Default: 0 1 2 3 8 7 6 9 5 4Sorted Standard Compare Function: 9 8 7 6 5 0 1 2 3 4Sorted Lamda Function: 0 1 9 8 7 6 5 2 3 4

* C#中的Array.Sort()

笔者在用C++复刻C#代码的时候发现对相同的数组排序的结果有时候会出现不一致，查了C#的官方文档后才发现，C#中Array.Sort()函数是unstable_sort,也就是说其排序是无法保证相对顺序的，而且Array似乎也没有提供Stable_Sort版本的排序函数，因此如果需要保证相对顺序不变，需要手动给原始的数据添加一个index,这样再其他的key判等都相等时可以采用额外的Index来保持相对的原始序。而且有意思的是，Array.Sort()函数具体使用的排序方法是根据数据规模发生改变的

-如果数据量小于等于16个，则采用插入排序-如果需要排序的数量超过2 * log(N)，其中N为输入的排序范围，则采用堆排序-其余情况均采用快速排序

以上是对常用的标准库排序算法的总结和不同语言的对比，可以根据实际需要和数据量的大小来选择合适的排序算法。

关键词：