> 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/sorting-stability.md).

# 排序算法稳定性

**稳定排序**：相等元素**相对位置不变**；不稳定则会打乱。

### 一、常见排序稳定性总结

#### 稳定排序

1. **冒泡排序** ✅ 稳定
2. **插入排序** ✅ 稳定
3. **归并排序** ✅ 稳定
4. **基数排序** ✅ 稳定
5. **计数排序** ✅ 稳定

#### 不稳定排序

1. **选择排序** ❌ 不稳定
2. **快速排序** ❌ 不稳定
3. **希尔排序** ❌ 不稳定
4. **堆排序** ❌ 不稳定

***

### 二、原因

1. **冒泡/插入** 只在**相邻元素**交换，相等时不移动，所以稳定。
2. **归并** 合并时**先取左区间元素**，相等时保留原顺序，稳定。
3. **选择排序** 每次把最小元素**直接交换到前面**，会跨位置打乱相等元素，不稳定。
4. **快排/堆排** 大范围交换、跳跃式移位，极易打乱相等元素顺序，不稳定。

***

### 三、C++ 标准库 `std::sort` / `stable_sort`

* `std::sort`：**底层快排+堆排** → **不稳定**，速度快
* `std::stable_sort`：**底层归并排序** → **稳定**，速度略慢

#### 示例代码

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<pair<int, int>> v = {{2,1}, {1,2}, {2,3}};
    // 不稳定排序
    sort(v.begin(), v.end());
    // 稳定排序
    // stable_sort(v.begin(), v.end());
    for(auto &p : v) cout << p.first << " " << p.second << endl;
}
```

***

### 四、使用场景

* 只看大小、**不关心原顺序**：用 `sort`（更快）
* 需要**保留相等元素原有先后**（如按成绩排序再保留学号）：用 `stable_sort`


---

# 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/sorting-stability.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.