【C++】sort

sort

1. 基本功能

• 在 C++ 算法库中，sort函数主要用于对给定范围内的元素进行排序。它是一种高效的排序算法，通常基于快速排序（Quick Sort）的思想实现，并且在某些情况下会自动切换到插入排序（Insertion Sort）以优化性能。
• 头文件需要包含才能使用sort函数。

2. 函数原型

最常用的形式是void sort (RandomAccessIterator first, RandomAccessIterator last);。

其中first是指向要排序范围的起始位置的迭代器，last是指向要排序范围的结束位置（最后一个元素的下一个位置）的迭代器。

例如，对于一个数组int arr[] = {5, 3, 1, 4, 2};，如果要对整个数组进行排序，可以使用sort(arr, arr + 5);，这里arr相当于first，arr + 5相当于last，因为arr + 5指向数组最后一个元素之后的位置。

2. 排序规则

• 默认情况下，sort函数按照元素类型的小于（<）运算符定义的升序规则进行排序。例如，对于整数数组，它会将元素从小到大排列；对于自定义类型的数组，如果自定义类型定义了小于运算符，sort也会按照这个规则进行排序。

• 如果想要按照降序排序或者自定义排序规则，可以使用函数对象或者 Lambda 表达式作为第三个参数传递给sort函数。例如，要对一个整数数组进行降序排序，可以这样写：

  #include <iostream>
  #include <algorithm>
  bool compare(int a, int b) {
      return a > b;
  }
  int main() {
      int arr[] = {1, 3, 2, 5, 4};
      int n = sizeof(arr)/sizeof(arr[0]);
      std::sort(arr, arr + n, compare);
      for(int i = 0; i < n; ++i) 
      {
          std::cout << arr[i] << " ";
      }
      return 0;
  }
  

  这里定义了一个比较函数compare，它返回a > b，这样sort函数就会按照降序排列数组元素。

2. 时间复杂度

平均情况下，sort函数的时间复杂度为$O(nlogn)$，其中n是要排序的元素个数。在最好的情况下（例如数组已经有序），时间复杂度可以接近$O(n)$，这是因为sort函数内部的优化机制可能会切换到插入排序等更适合有序情况的算法。在最坏的情况下，时间复杂度为$O(n^2)$，不过这种情况相对较少出现。

2. 空间复杂度

sort函数的空间复杂度为$O(logn)$，这是因为它在排序过程中可能需要一些额外的栈空间来进行递归操作（基于快速排序的部分实现）。不过，在实际应用中，这个空间开销通常是比较合理的。

2. 适用范围

sort函数适用于各种可以通过随机访问迭代器访问的容器，比如std::vector、std::array等。但对于一些不支持随机访问迭代器的容器，如std::list，就不能直接使用sort函数。对于std::list，可以使用list自身的sort成员函数，它的实现方式更适合链表这种数据结构。

td::list，可以使用list自身的sort成员函数，它的实现方式更适合链表这种数据结构。

原文地址：https://blog.csdn.net/2301_82135086/article/details/144193469

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！