sort头文件详解

sort头文件是C++标准库中的一个头文件，它包含了各种排序算法的实现。在实际开发中，sort头文件可以帮助我们快速、有效地对数组、向量、链表等数据类型进行排序。

sort头文件的基本使用方法

sort头文件中最常用的函数是sort()函数，它的基本使用方法如下：

#include 
using namespace std;

int arr[] = {5, 2, 4, 3, 1};
int n = sizeof(arr)/sizeof(int);
sort(arr, arr+n);

上述代码中，我们首先包含了头文件，然后定义了一个整型数组arr，并计算了数组的长度n。最后，我们使用sort()函数对数组进行排序。

sort()函数的第一个参数是待排序序列的起始地址，第二个参数是序列的结束地址。注意，这里的结束地址指的是“最后一个元素的下一个位置”，即在C++中通常用end()函数来获取。

sort()函数还可以接受一个可调用对象作为第三个参数，用于自定义排序规则。例如，以下代码可以按照字符串长度对字符串数组进行排序：

bool cmp(string a, string b) {
  return a.size() 

sort头文件中的常见排序算法

冒泡排序

冒泡排序是一种基础的排序算法，其思想是重复地遍历序列，每次比较相邻的两个元素，如果它们的顺序错误就交换它们的位置，直到序列已经排好序。

冒泡排序的时间复杂度为O(n^2)，因此它在处理大规模数据时效率较低。


void bubble_sort(int arr[], int n) {
  for (int i = 0; i  arr[j+1]) {
        swap(arr[j], arr[j+1]);
      }
    }
  }
}


快速排序

快速排序是一种常用的高效排序算法，其基本思想是通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后对这两部分记录分别进行快速排序，重复以上过程，直到整个序列有序为止。

快速排序的时间复杂度为O(nlogn)，但在最坏情况下可能会退化为O(n^2)。

int partition(int arr[], int low, int high) {
  int pivot = arr[high];
  int i = low;
  for (int j = low; j 

归并排序

归并排序是一种采用分治策略的排序算法，其基本思想是将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将有序子序列合并成整体有序序列。

归并排序的时间复杂度为O(nlogn)，但它需要额外的空间来存储中间结果，因此在空间复杂度上略劣于快速排序。

void merge(int arr[], int l, int m, int r) {
  int n1 = m-l+1;
  int n2 = r-m;
  int L[n1], R[n2];
  for (int i = 0; i