排序

排序算法（英语：Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。

稳定性 稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。

拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的纪录 R 和 S，且在原本的列表中 R 出现在 S 之前，在排序过的列表中 R 也将会是在 S 之前。

基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。

选择排序、堆排序、快速排序、希尔排序不是稳定排序。

时间复杂度 主页面：复杂度

时间复杂度用来衡量一个算法的运行时间和输入规模的关系，通常用 O 表示。

简单计算复杂度的方法一般是统计「简单操作」的执行次数，有时候也可以直接数循环的层数来近似估计。

时间复杂度分为最优时间复杂度、平均时间复杂度和最坏时间复杂度。OI 竞赛中要考虑的一般是最坏时间复杂度，因为它代表的是算法运行水平的下界，在评测中不会出现更差的结果了。

基于比较的排序算法的时间复杂度下限是 $O(n\log n)$ 的。

当然也有不是 $O(n\log n)$ 的。例如，计数排序 的时间复杂度是 $O(n+w)$，其中 $w$ 代表输入数据的值域大小。

以下是几种排序算法的比较。

排序算法	平均时间复杂度	最差时间复杂度	空间复杂度	数据对象稳定性
⭐插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
⭐希尔排序	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定
🫧冒泡排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
🫧快速排序	$O(n\log_2n)$	$O(n^2)$	$O(\log_2n)$	不稳定
📌 选择排序	$O(n^2)$	$O(n^2)$	$O(1)$	数组不稳定、链表稳定
📌 堆排序	$O(n\log_2n)$	$O(n\log_2n)$	$O(1)$	不稳定
🧲归并排序	$O(n\log_2n)$	$O(n\log_2n)$	$O(n)$	稳定
基数排序	$O(k \times n)$	$O(n^2)$		稳定
计数排序	$O(n+m)$	$O(n+m)$	$O(n+m)$	稳定
桶排序	$O(n)$	$O(n)$	$O(m)$	稳定

口诀

交插选归基, 只有交插稳.(只有简单交换(冒泡)和简单插入稳定)
交插选平方, 对数快并堆.(交插选的平均时间复杂度是$O(n^2)$,快速排序,归并排序,堆排序的平均时间复杂度是$O(n\log_2n)$)

内部排序

1. 插入排序：在最一趟排序前，没有任何关键字到达最终位置

   1. 直接插入-二分法插入(二分法插入的最好时间复杂度降为$O(n\log_2n)$)
   2. 希尔插入$O(n^{1.3}) \to O(n^2)$：分组排序，由无序变为基本有序最后到有序，跳度从$n$到$1$。希尔插入的组内排序使用的是直接插入。 缩小增量直接插入排序：无序→基本有序→全局有序

2. 交换排序

   1. 冒泡交换： 没有发生交换可以提前宣布结束。
   2. 快速交换：分治法 对每一个子序列的一次划分算一趟排序，每一趟结束之后，有一个关键词到达最终位置。不产生有序子序列，有序不利，平均性能最优的算法,空间复杂度
      时间复杂度为什么是 每一趟都会对n个数进行排序:O(n); 一共要进行O(log_2n)趟.
      空间复杂度是由于快速排序的递归栈生成的.

3. 选择排序

   1. 简单选择$O(n^2)$
   2. 堆选择$O(n\log_2n)$：大顶堆的建立和增删.适合关键字数很多的情况，比如从10000个关键字中选出前十个最小的。

4. 归并排序

   1. 二路归并：$O(n\log_2n)$，但需要转存整个数列。
   2. K路归并：k个车道汇流成1个车道，小者先行。归并次数：$c = \lceil \log_km\rceil$。每一次归并，所有记录都要进行两次IO操作
   3. 败者树LT：用于外部排序中提高效率。 败者树实际上是一棵完全二叉树，可以看做是胜者树的一种变体。用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。多路归并的比较次数，小者胜。叶子节点是段首记录，非叶子节点是段序号。简述时间复杂度$O(k\log_2k)$。选出最值的时间复杂度$O(\log_2k)$

5. 基数排序radix：$O(d(n+r_d))$,其中n是关键词字数，d是关键字的位数，rd是关键字基的个数。

排序特性

5. 稳定：直接插入，冒泡交换

6. 不稳定：希尔插入，快速交换，简单选择，堆选择

$$O(n^2)$$

7. 空间复杂度快排式log。 归并排序是ON。 基数排序是。 Ord。 其他都是。 O1。

8. 交换类的排序排序趟数和原始序列有关。基本有序时，冒泡交换有利，快速交换不利。

9. 简单选择和折半插入的关键字比较次数和原始序列无关。

10. 与初始排列序列无关的是基数排序。

11. 冒泡交换、快速交换、简单选择，堆选择可以使经过一趟排序能够保证一个关键词到达最终位置。

外部排序

12. 置换选择排序：用于生成初始归并段。根据buffer大小初始化归并段。每所有记录都要进行两次I/O操作。

13. 最佳归并树BMT：使用huffman树的构造方法来构造BMT，用于减少归并次数。

冒泡排序法 插入排序法 堆排序法 二叉树排序法

O(n^2) O(n^2) O(nlog2n) 最差 O(n2) 平均 O(nlog2n)

快速排序法 希尔排序法

最差 O(n^2) 平均 O(nlog2n) O(nlog n) 不稳定

排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

选择排序算法的准则

一般而言，需要考虑的因素有以下四点：

设待排序元素的个数为n.

1. 当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
2. 当n较大，内存空间允许，且要求稳定性：归并排序
3. 当n较小，可采用直接插入或直接选择排序。
   1. 直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。
   2. 直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序
4. 一般不使用或不直接使用传统的冒泡排序。
5. 基数排序 它是一种稳定的排序算法，但有一定的局限性：
   1. 关键字可分解。
   2. 记录的关键字位数较少，如果密集更好
   3. 如果是数字时，最好是无符号的

循环和递归

递归和循环两者完全可以互换。不能完全决定性地说循环地效率比递归的效率高。

递归算法

优点：代码简洁、清晰，并且容易验证正确性。

缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。 但是，对于某些问题，如果不使用递归，那将是极端难看的代码。在编译器优化后，对于多次调用的函数处理会有非常好的效率优化，效率未必低于循环。

循环算法

优点：速度快，结构简单。

缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。

选择排序

简单

不稳定 $O(n^2)$

由于 swap（交换两个元素）操作的存在，选择排序是一种不稳定的排序算法。

选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 $O(n^2)$。

void selection_sort(int* a, int n) {
  for (int i = 1; i < n; ++i) {
    int i_current_min = i;
    for (int j = i + 1; j <= n; ++j) {
      if (a[j] < a[i_current_min]) {
        i_current_min = j;
      }
    }
    std::swap(a[i], a[i_current_min]);
  }
}

堆排序

不稳定 $O(n\log n)$

堆排序（英语：Heapsort）是指利用 二叉堆 这种数据结构所设计的一种排序算法。堆排序的适用数据结构为数组。

堆排序的本质是建立在堆上的选择排序。

排序

首先建立大顶堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质；

之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质；

以此类推，在第 n-1 次操作后，整个数组就完成了排序。

在数组上建立二叉堆

从根节点开始，依次将每一层的节点排列在数组里。

于是有数组中下标为 i 的节点，对应的父结点、左子结点和右子结点如下：

iParent(i) = (i - 1) / 2;
iLeftChild(i) = 2 * i + 1;
iRightChild(i) = 2 * i + 2;

void sift_down(int arr[], int start, int end) {
  // 计算父结点和子结点的下标
  int parent = start;
  int child = parent * 2 + 1;
  while (child <= end) {  // 子结点下标在范围内才做比较
    // 先比较两个子结点大小，选择最大的
    if (child + 1 <= end && arr[child] < arr[child + 1]) child++;
    // 如果父结点比子结点大，代表调整完毕，直接跳出函数
    if (arr[parent] >= arr[child])
      return;
    else {  // 否则交换父子内容，子结点再和孙结点比较
      swap(arr[parent], arr[child]);
      parent = child;
      child = parent * 2 + 1;
    }
  }
}

void heap_sort(int arr[], int len) {
  // 从最后一个节点的父节点开始 sift down 以完成堆化 (heapify)
  for (int i = (len - 1 - 1) / 2; i >= 0; i--) sift_down(arr, i, len - 1);
  // 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕
  for (int i = len - 1; i > 0; i--) {
    swap(arr[0], arr[i]);
    sift_down(arr, 0, i - 1);
  }
}

交换排序

冒泡排序

稳定 $O(n^2)$

冒泡排序（英语：Bubble sort）是一种简单的排序算法。由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。

它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。

经过 i 次扫描后，数列的末尾 i 项必然是最大的 i 项，因此冒泡排序最多需要扫描 n-1 遍数组就能完成排序。

// 假设数组的大小是 n + 1，冒泡排序从数组下标 1 开始
void bubble_sort(int *a, int n) {
  bool flag = true;
  while (flag) {
    flag = false;
    for (int i = 1; i < n; ++i) {
      if (a[i] > a[i + 1]) {
        flag = true;
        int t = a[i];
        a[i] = a[i + 1];
        a[i + 1] = t;
      }
    }
  }
}

快速排序(分区交换排序)

稳定 $O(n\log n)$

快速排序（英语：Quicksort），又称分区交换排序（英语：partition-exchange sort），简称「快排」，是一种被广泛运用的排序算法。

快速排序的工作原理是通过 分治 的方式来将一个数组排序。

快速排序分为三个过程：

将数列划分为两部分（要求保证相对大小关系）； 递归到两个子序列中分别进行快速排序； 不用合并，因为此时数列已经完全有序。 和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度，一般是随机选择一个数 m 来当做两个子数列的分界。

之后，维护一前一后两个指针 p 和 q，依次考虑当前的数是否放在了应该放的位置（前还是后）。如果当前的数没放对，比如说如果后面的指针 q 遇到了一个比 m 小的数，那么可以交换 p 和 q 位置上的数，再把 p 向后移一位。当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇。

其实，快速排序没有指定应如何具体实现第一步，不论是选择 m 的过程还是划分的过程，都有不止一种实现方法。

第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了。

struct Range {
  int start, end;

  Range(int s = 0, int e = 0) { start = s, end = e; }
};

template <typename T>
void quick_sort(T arr[], const int len) {
  if (len <= 0) return;
  Range r[len];
  int p = 0;
  r[p++] = Range(0, len - 1);
  while (p) {
    Range range = r[--p];
    if (range.start >= range.end) continue;
    T mid = arr[range.end];
    int left = range.start, right = range.end - 1;
    while (left < right) {
      while (arr[left] < mid && left < right) left++;
      while (arr[right] >= mid && left < right) right--;
      std::swap(arr[left], arr[right]);
    }
    if (arr[left] >= arr[range.end])
      std::swap(arr[left], arr[range.end]);
    else
      left++;
    r[p++] = Range(range.start, left - 1);
    r[p++] = Range(left + 1, range.end);
  }
}

插入排序

稳定 $O(n^2)$

插入排序（英语：Insertion sort）是一种简单直观的排序算法。它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。

一个与插入排序相同的操作是打扑克牌时，从牌桌上抓一张牌，按牌面大小插到手牌后，再抓下一张牌。

void insertion_sort(int arr[], int len) {
  for (int i = 1; i < len; ++i) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

插入排序还可以通过二分算法优化性能，在排序元素数量较多时优化的效果比较明显。

折半插入排序与直接插入排序的基本思想是一致的，折半插入排序仅对插入排序时间复杂度中的常数进行了优化，所以优化后的时间复杂度仍然不变。

折半插入

void insertion_sort(int arr[], int len) {
  if (len < 2) return;
  for (int i = 1; i != len; ++i) {
    int key = arr[i];
    auto index = upper_bound(arr, arr + i, key) - arr;
    // 使用 memmove 移动元素，比使用 for 循环速度更快，时间复杂度仍为 O(n)
    memmove(arr + index + 1, arr + index, (i - index) * sizeof(int));
    arr[index] = key;
  }
}

归并排序

归并排序（merge sort）是高效的基于比较的稳定排序算法。

归并排序基于分治思想将数组分段排序后合并，时间复杂度在最优、最坏与平均情况下均为 $\Theta (n \log n)$，空间复杂度为 $\Theta (n)$。

归并排序可以只使用 $\Theta (1)$ 的辅助空间，但为便捷通常使用与原数组等长的辅助数组。

归并排序最核心的部分是合并（merge）过程：将两个有序的数组 a[i] 和 b[j] 合并为一个有序数组 c[k]。

从左往右枚举 a[i] 和 b[j]，找出最小的值并放入数组 c[k]；重复上述过程直到 a[i] 和 b[j] 有一个为空时，将另一个数组剩下的元素放入 c[k]。

为保证排序的稳定性，前段首元素小于或等于后段首元素时（a[i] <= b[j]）而非小于时（a[i] < b[j]）就要作为最小值放入 c[k]。

数组实现

void merge(const int *a, size_t aLen, const int *b, size_t bLen, int *c) {
  size_t i = 0, j = 0, k = 0;
  while (i < aLen && j < bLen) {
    if (b[j] < a[i]) {  // <!> 先判断 b[j] < a[i]，保证稳定性
      c[k] = b[j];
      ++j;
    } else {
      c[k] = a[i];
      ++i;
    }
    ++k;
  }
  // 此时一个数组已空，另一个数组非空，将非空的数组并入 c 中
  for (; i < aLen; ++i, ++k) c[k] = a[i];
  for (; j < bLen; ++j, ++k) c[k] = b[j];
}

指针实现

void merge(const int *aBegin, const int *aEnd, const int *bBegin,
           const int *bEnd, int *c) {
  while (aBegin != aEnd && bBegin != bEnd) {
    if (*bBegin < *aBegin) {
      *c = *bBegin;
      ++bBegin;
    } else {
      *c = *aBegin;
      ++aBegin;
    }
    ++c;
  }
  for (; aBegin != aEnd; ++aBegin, ++c) *c = *aBegin;
  for (; bBegin != bEnd; ++bBegin, ++c) *c = *bBegin;
}

也可使用<algorithm> 库的 merge 函数，用法与上述指针式写法的相同。

分治法实现归并排序

当数组长度为 1 时，该数组就已经是有序的，不用再分解。

当数组长度大于 1 时，该数组很可能不是有序的。此时将该数组分为两段，再分别检查两个数组是否有序（用第 1 条）。如果有序，则将它们合并为一个有序数组；否则对不有序的数组重复第 2 条，再合并。

用数学归纳法可以证明该流程可以将一个数组转变为有序数组。

为保证排序的复杂度，通常将数组分为尽量等长的两段（ $mid = \left\lfloor \dfrac{l + r}{2} \right\rfloor$）。

void merge_sort(int *a, int l, int r) {
  if (r - l <= 1) return;
  // 分解
  int mid = l + ((r - l) >> 1);
  merge_sort(a, l, mid), merge_sort(a, mid, r);
  // 合并
  int tmp[1024] = {};  // 请结合实际情况设置 tmp 数组的长度（与 a 相同），或使用
                       // vector；先将合并的结果放在 tmp 里，再返回到数组 a
  merge(a + l, a + mid, a + mid, a + r, tmp + l);  // pointer-style merge
  for (int i = l; i < r; ++i) a[i] = tmp[i];
}

倍增法实现归并排序

已知当数组长度为 1 时，该数组就已经是有序的。

将数组全部切成长度为 1 的段。

从左往右依次合并两个长度为 1 的有序段，得到一系列长度 $\le 2$ 的有序段；

从左往右依次合并两个长度 $\le 2$ 的有序段，得到一系列长度 $\le 4$ 的有序段；

从左往右依次合并两个长度 $\le 4$ 的有序段，得到一系列长度 $\le 8$ 的有序段；

……

重复上述过程直至数组只剩一个有序段，该段就是排好序的原数组。

void merge_sort(int *a, size_t n) {
  int tmp[1024] = {};  // 请结合实际情况设置 tmp 数组的长度（与 a 相同），或使用
                       // vector；先将合并的结果放在 tmp 里，再返回到数组 a
  for (size_t seg = 1; seg < n; seg <<= 1) {
    for (size_t left1 = 0; left1 < n - seg;
         left1 += seg + seg) {  // n - seg: 如果最后只有一个段就不用合并
      size_t right1 = left1 + seg;
      size_t left2 = right1;
      size_t right2 = std::min(left2 + seg, n);  // <!> 注意最后一个段的边界
      merge(a + left1, a + right1, a + left2, a + right2,
            tmp + left1);  // pointer-style merge
      for (size_t i = left1; i < right2; ++i) a[i] = tmp[i];
    }
  }
}

逆序对

逆序对是 $i < j$ 且 $a_i > a_j$ 的有序数对 $(i, j)$。

排序后的数组无逆序对，归并排序的合并操作中，每次后段首元素被作为当前最小值取出时，前段剩余元素个数之和即是合并操作减少的逆序对数量；故归并排序计算逆序对数量的额外时间复杂度为 $\Theta (n \log n)$，对于 C/C++ 代码将 merge 过程的 if(b[j] < a[i]) 部分加上 cnt += aLen - i 或 cnt += aEnd - aBegin 即可，对于 Python 代码将 merge 过程的 if(b[j] < a[i]): 部分加上 cnt += len(a) - i 即可。

此外，逆序对计数即是将元素依次加入数组时统计当前大于其的元素数量，将数组离散化后即是区间求和问题，使用树状数组或线段树解决的时间复杂度为 $O(n \log n)$ 且空间复杂度为 $\Theta (n)$。

桶排序

稳定

桶排序的平均时间复杂度为 $O(n + n^2/k + k)$（将值域平均分成 $n$ 块 + 排序 + 重新合并元素），当 $k\approx n$ 时为 $O(n)$

桶排序的最坏时间复杂度为 $O(n^2)$。

如果使用稳定的内层排序，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法。

由于每块元素不多，一般使用插入排序。此时桶排序是一种稳定的排序算法。

桶排序（英文：Bucket sort）是排序算法的一种，适用于待排序数据值域较大但分布比较均匀的情况。

桶排序按下列步骤进行：

1. 设置一个定量的数组当作空桶；
2. 遍历序列，并将元素一个个放到对应的桶中；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把元素再放回原来的序列中。

const int N = 100010;

int n, w, a[N];
vector<int> bucket[N];

void insertion_sort(vector<int>& A) {
  for (int i = 1; i < A.size(); ++i) {
    int key = A[i];
    int j = i - 1;
    while (j >= 0 && A[j] > key) {
      A[j + 1] = A[j];
      --j;
    }
    A[j + 1] = key;
  }
}

void bucket_sort() {
  int bucket_size = w / n + 1;
  for (int i = 0; i < n; ++i) {
    bucket[i].clear();
  }
  for (int i = 1; i <= n; ++i) {
    bucket[a[i] / bucket_size].push_back(a[i]);
  }
  int p = 0;
  for (int i = 0; i < n; ++i) {
    insertion_sort(bucket[i]);
    for (int j = 0; j < bucket[i].size(); ++j) {
      a[++p] = bucket[i][j];
    }
  }
}

排序相关STL

除已说明的函数外，本页所列函数默认定义于头文件<algorithm> 中。

qsort

该函数为 C 标准库实现的 快速排序，定义在 <stdlib.h> 中。在 C++ 标准库里，该函数定义在 <cstdlib> 中。

qsort 与 bsearch 的比较函数

qsort 函数有四个参数：数组名、元素个数、元素大小、比较规则。其中，比较规则通过指定比较函数来实现，指定不同的比较函数可以实现不同的排序规则。

比较函数的参数限定为两个 const void 类型的指针。返回值规定为正数、负数和 0。

比较函数的一种示例写法为：

int compare(const void *p1, const void *p2)  // int 类型数组的比较函数
{
  int *a = (int *)p1;
  int *b = (int *)p2;
  if (*a > *b)
    return 1;  // 返回正数表示 a 大于 b
  else if (*a < *b)
    return -1;  // 返回负数表示 a 小于 b
  else
    return 0;  // 返回 0 表示 a 与 b 等价
}

注意：返回值用两个元素相减代替正负数是一种典型的错误写法，因为这样可能会导致溢出错误。

以下是排序结构体的一个示例：

struct eg  // 示例结构体
{
  int e;
  int g;
};

int compare(const void *p1,
            const void *p2)  // struct eg 类型数组的比较函数：按成员 e 排序
{
  struct eg *a = (struct eg *)p1;
  struct eg *b = (struct eg *)p2;
  if (a->e > b->e)
    return 1;  // 返回正数表示 a 大于 b
  else if (a->e < b->e)
    return -1;  // 返回负数表示 a 小于 b
  else
    return 0;  // 返回 0 表示 a 与 b 等价
}

这里也可以看出，等价不代表相等，只代表在此比较规则下两元素等价。

std::sort

用法：

// a[0] .. a[n - 1] 为需要排序的数列
// 对 a 原地排序，将其按从小到大的顺序排列
std::sort(a, a + n);

// cmp 为自定义的比较函数
std::sort(a, a + n, cmp);

注意：sort 的比较函数的返回值是 true 和 false，用 true 和 false 表示两个元素的大小（先后）关系，这与 qsort 的三值比较函数的语义完全不同。具体内容详见上方给出的 sort 的文档。

如果要将 sort 简单改写为 qsort，维持排序顺序整体上不变（不考虑等价的元素），需要将返回 true 改为 - 1，返回 false 改为 1。

std::sort 函数是更常用的 C++ 库比较函数。该函数的最后一个参数为二元比较函数，未指定 cmp 函数时，默认按从小到大的顺序排序。

旧版 C++ 标准中仅要求它的 平均 时间复杂度达到 $O(n\log n)$。C++11 标准以及后续标准要求它的 最坏 时间复杂度达到 $O(n\log n)$。

C++ 标准并未严格要求此函数的实现算法，具体实现取决于编译器。libstdc++ 和 libc++ 中的实现都使用了 内省排序。

std::nth_element

用法：

std::nth_element(first, nth, last);
std::nth_element(first, nth, last, cmp);

它重排 [first, last) 中的元素，使得 nth 所指向的元素被更改为 [first, last) 排好序后该位置会出现的元素。这个新的 nth 元素前的所有元素小于或等于新的 nth 元素后的所有元素。

实现算法是未完成的内省排序。

对于以上两种用法，C++ 标准要求它的平均时间复杂度为 O(n)，其中 n 为 std::distance(first, last)。

它常用于构建 K-D Tree。

std::stable_sort

用法：

std::stable_sort(first, last);
std::stable_sort(first, last, cmp);

稳定排序，保证相等元素排序后的相对位置与原序列相同。

时间复杂度为 $O(n\log (n)^2)$，当额外内存可用时，复杂度为 $O(n\log n)$。

std::partial_sort

用法：

// mid = first + k
std::partial_sort(first, mid, last);
std::partial_sort(first, mid, last, cmp);

将序列中前 k 元素按 cmp 给定的顺序进行原地排序，后面的元素不保证顺序。未指定 cmp 函数时，默认按从小到大的顺序排序。

复杂度：约 $(\mathit{last}-\mathit{first})\log(\mathit{mid}-\mathit{first})$ 次应用 cmp。

原理：

std::partial_sort 的思想是：对原始容器内区间为 [first, mid) 的元素执行 make_heap() 操作，构造一个大根堆，然后将 [mid, last) 中的每个元素和 first 进行比较，保证 first 内的元素为堆内的最大值。如果小于该最大值，则互换元素位置，并对 [first, mid) 内的元素进行调整，使其保持最大堆序。比较完之后，再对 [first, mid) 内的元素做一次堆排序 sort_heap() 操作，使其按增序排列。注意，堆序和增序是不同的。