---
title: "排序复习"
author: "Perrin Yong"
author_profile: https://www.pystone.net/profile/
published_by: "Perrin Yong"
canonical: https://www.pystone.net/notes/cpp-sorting-review/
type: note
content_role: unspecified
visibility: public
id_stability: rename-stable
source_path: "10-计算机、信息技术与工程/02-编程语言与运行时/C++/排序复习.md"
content_hash: ea4977633697ad0875043177af0359a8764d73e2b5943a90bf7e8a79409a53a0
knowledge_version: 224c990773de.5fa8af6e39fa
site_commit: 224c990773de166d23a886306577dd90379529ce
notes_commit: 5fa8af6e39fa3891d1b9b4832bfa6c4e0ecaaf0a
---
# 排序复习

# 排序复习

> 创建时间：2020/2/5 0:29

### C++STL Sort实现

  1. 数据量大时采用QuickSort快排算法，分段归并排序。
  2. 一旦分段后的数据量小于某个门槛（16），为避免QuickSort快排的递归调用带来过大的额外负荷，就改用Insertion Sort插入排序。
  3. 如果递归层次过深，还会改用HeapSort堆排序。

https://blog.csdn.net/qq_35440678/article/details/80147601

### stable_sort

会对一段元素进行排序并保证 **维持相等元素的原始顺序**
sort是快速排序实现，因此是不稳定的；
stable_sort是归并排序实现，因此是稳定的。

```cpp
string str1 = "test";
string str2 = "test";

```

>   * sort是快速排序实现，因此是不稳定的；stable_sort是归并排序实现，因此是稳定的。
>   * 如果提供了比较函数，sort不要求比较函数的参数被限定为const，而stable_sort则要求参数被限定为const，否则编译不能通过。
>

### 快速排序

给基准数据找其正确索引位置的过程

  1. 先从数列中取出一个数作为基准数
  2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
  3. 再对左右区间重复第二步，直到各区间只有一个数

挖坑填数过程：

  1. i =L; j = R; 将基准数挖出形成第一个坑a[i]。
  2. j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
  3. i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
  4. 再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

```cpp
string str1 = "test";
string str2 = "test";

```