21xrx.com
2025-04-01 15:54:16 Tuesday
文章检索 我的文章 写文章
C++自带的排序算法：了解常用排序函数及使用方法
2023-07-01 16:48:51 深夜i     8     0
C++排序算法 常用排序函数 排序使用方法 STL 内置排序函数

C++作为一门高效的编程语言，提供了多种算法及数据结构，其中的排序算法也是非常强大和实用的。在使用C++进行编程时，我们可以直接调用C++自带的排序算法来对数据进行排序，省去了手动编写算法的繁琐过程，大大提高了工作效率。

C++自带的排序算法基本上是使用快速排序(quicksort)作为主要参考，同时也使用了插入排序(insertion)和堆排序(heap sort)等其它排序方法，因此有很好的时间复杂度和空间复杂度的平衡。而通过选择合适的排序函数，我们可以根据不同的需求，来达到最佳的排序效果。

在C++中，常用的排序函数有sort、stable_sort和partial_sort三种。其中sort函数是C++自带的最常用的排序函数之一，它的使用方法如下：

sort (begin, end)：该函数将区间 [begin, end) 中的元素从小到大排序，其中begin和end分别表示要排序的区间的起始位置和终止位置，具体来说，区间 [begin, end) 包含 begin 和 end 之间的所有元素，但是不包括end所指向的元素。函数执行后，区间 [begin, end) 中的元素就从小到大排序了。

以vector为例，下面给出了具体的排序过程：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
  vector<int> v = 5;
  // 默认排序
  sort(v.begin(), v.end());
  for (auto i : v)
    cout << i << " ";
  
  // 输出为: 1 2 3 4 5
  return 0;
}

除了默认排序外，sort函数还可以用自定义的比较函数来对区间进行排序，因此，我们可以根据自己的实际需求来定义比较函数，以满足不同的排序需求。

stable_sort函数是sort函数的升级版，它不仅可以实现与sort函数相同的排序功能，还可以保证排序过程的稳定性。也就是说，如果某些元素的值相同时，它们之间的相对位置在排序之前和排序之后不会发生变化。stable_sort函数的使用方法与sort函数类似。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
  vector<pair<int, int>> vec = { 2, 4, 1, 2};
  stable_sort(vec.begin(), vec.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
    if (a.first == b.first)
      return a.second > b.second;
    
    return a.first < b.first;
  });
  for (auto p : vec)
    cout << p.first << " " << p.second << endl;
  
  // 输出为：1 2 1 1 2 1 3 4
  return 0;
}

partial_sort函数则可以实现局部排序功能，即针对一个很大的数据集合，我们只需要对其中的前n个或后n个元素进行排序，而不必对整个数据集合进行排序。partial_sort函数的使用方法如下：

partial_sort (begin, middle, end)：将区间 [begin, end) 中的元素按照从小到大排序，然后将排序后的前middle-begin个元素置于区间 [begin, middle) 中，其余元素置于区间 [middle, end) 中。其中begin、middle和end分别表示要排序的区间的起始位置、中间位置和终止位置。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
  vector<int> vec = 9;
  partial_sort(vec.begin(), vec.begin() + 4, vec.end());
  for (int i = 0; i < 4; i++) {
    cout << vec[i] << " ";
  }
  // 输出为：1 2 3 4
  return 0;
}

总的来说，C++自带的排序函数使用简单，效率高，而且能够满足不同的排序需求。在日常编程中，我们可以充分利用这些函数，提高我们的编程效率和工作效益。

  
  

评论区