> For the complete documentation index, see [llms.txt](https://docs.1l.lol/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.1l.lol/sorting/std-sort.md).

# sort 排序

### 一、基础概念

`sort` 是 C++ 标准库中 `<algorithm>` 头文件提供的高效排序函数，底层是**快速排序（QuickSort）+ 插入排序 + 堆排序**的混合实现，时间复杂度稳定为 **O(n log n)**，默认按**升序**排列。

#### 头文件

```cpp
#include <algorithm>
```

***

### 二、基础用法格式

#### 1. 数组版

```cpp
// 格式：sort(数组首地址, 数组尾地址+1, 比较函数);
int arr[100];
int n = 5;

// 升序（默认）
sort(arr, arr + n);

// 降序（两种写法）
// 写法1：使用 greater<int>()
sort(arr, arr + n, greater<int>());

// 写法2：自定义比较函数
bool cmp(int a, int b) {
    return a > b;
}
sort(arr, arr + n, cmp);
```

#### 2. `vector` 版

```cpp
vector<int> v = {3, 1, 4, 2, 5};

// 升序
sort(v.begin(), v.end());

// 降序
sort(v.begin(), v.end(), greater<int>());

// 从第2个元素开始排序（下标从1开始）
sort(&v[1], &v[5]); // 等价于 sort(v.begin()+1, v.end());
```

***

### 三、自定义比较函数（核心）

#### 1. 通用规则

* 函数返回 `true` 时，`a` 会排在 `b` 前面；返回 `false` 时，`b` 排在 `a` 前面。
* 对于基础类型：`return a < b` 是升序，`return a > b` 是降序。

#### 2. 普通数据类型排序

```cpp
// 升序
bool cmpAsc(int a, int b) {
    return a < b;
}

// 降序
bool cmpDesc(int a, int b) {
    return a > b;
}

// 调用
sort(arr, arr + n, cmpAsc);
```

#### 3. 多条件排序（通用模板）

```cpp
// 比如：先按年龄升序，年龄相同按身高降序
struct Person {
    int age;
    int height;
    string name;
};

bool cmp(Person a, Person b) {
    if (a.age != b.age) {
        return a.age < b.age; // 年龄小的在前
    } else {
        return a.height > b.height; // 年龄相同，身高高的在前
    }
}
```

#### 4. `pair` 类型排序

* 默认规则：先按 `first` 升序，再按 `second` 升序。
* 自定义规则示例：

```cpp
vector<pair<int, int>> p;

// 先按 first 降序，再按 second 升序
bool cmpPair(pair<int, int> a, pair<int, int> b) {
    if (a.first != b.first) {
        return a.first > b.first;
    } else {
        return a.second < b.second;
    }
}

sort(p.begin(), p.end(), cmpPair);
```

#### 5. 字符串排序

* 默认按字典序升序：

```cpp
vector<string> strs = {"banana", "apple", "cherry"};
sort(strs.begin(), strs.end()); // 结果：apple, banana, cherry
```

* 按字符串长度排序：

```cpp
bool cmpStrLen(string a, string b) {
    return a.size() < b.size();
}
sort(strs.begin(), strs.end(), cmpStrLen);
```

***

### 四、常用拓展写法

#### 1. 部分区间排序

```cpp
int arr[10] = {1, 5, 3, 7, 9, 2, 4, 6, 8, 10};

// 只排序前5个元素（下标0~4）
sort(arr, arr + 5);

// 排序中间部分（下标2~7）
sort(arr + 2, arr + 8);
```

#### 2. 不写 `cmp` 的降序技巧

```cpp
vector<int> v = {3, 1, 4, 2, 5};
sort(v.begin(), v.end()); // 先升序
reverse(v.begin(), v.end()); // 再反转，等价于降序
```

#### 3. 从下标1开始的排序写法

```cpp
int arr[105];
int n = 5;
// 排序 arr[1] ~ arr[5]
sort(arr + 1, arr + n + 1);

// vector 写法（空出0号）
vector<int> v(n + 1);
sort(&v[1], &v[n + 1]);
```

***

### 五、易错

1. **区间是左闭右开**：`sort(a, a + n)` 表示排序 `a[0]` 到 `a[n-1]`，所以尾地址要写 `a + n`。
2. **`cmp`**\*\* 函数逻辑不能反\*\*：`return a < b` 是升序，`return a > b` 是降序，写反会导致排序完全错误。
3. **结构体排序必须自定义 \*\*\*\*`cmp`**：默认 `sort` 不知道如何比较结构体，必须明确写规则。
4. **`vector`**\*\* 下标越界问题\*\*：`&v[n+1]` 必须在 `vector` 实际大小范围内，否则会报错。

***

### 六、模板

```cpp
// 1. 数组升序
sort(arr, arr + n);

// 2. 数组降序
sort(arr, arr + n, greater<int>());

// 3. vector 升序
sort(v.begin(), v.end());

// 4. vector 降序
sort(v.begin(), v.end(), greater<int>());

// 5. 结构体多条件排序
struct Node { int a, b; };
bool cmp(Node x, Node y) {
    if (x.a != y.a) return x.a < y.a;
    return x.b > y.b;
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation by asking a question.

Perform an HTTP GET request on the following URL with the `ask` and `goal` query parameters:

```
GET https://docs.1l.lol/sorting/std-sort.md?ask=<question>&goal=<user_goal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is what the user is ultimately trying to achieve, the reason they need the answer. Sharing it helps GitBook give you a better, more relevant answer. A goal is most helpful when it describes the outcome the user wants rather than restating the question. For example, with `ask=how do I create an API token`, a goal like `automate deployments from our CI pipeline` lets GitBook tailor the answer to that use case.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.